Deklaratív programozás

1. kis házi feladat: Lista zsák-alakra hozása

1.0 változat
Utolsó módosítás: 2015-09-20
Kiadás: 2015-09-22
Beadási határidő: Erlang 2015-10-05, 23:59; Prolog 2015-10-09, 23:59

A feladat

A feladat az ún. zsák (angolul bag) fogalmához kapcsolódik, amelyet multihalmaznak (multiset) is hívnak. A zsák a halmaz egy olyan általánosítása, amelyben egy elem többszörösen is előfordulhat. Egy adott zsák adott a elemének a multiplicitásán az a elem előfordulásainak számát értjük.

Egy zsákot legegyszerűbben egy listával ábrázolhatunk, ahol természetesen a listaelemek sorrendje érdektelen ([a,b,a] és [a,a,b] ugyanazt a zsákot jelöli). Egy ennél tömörebb ábrázolás az, amikor felsoroljuk a zsák különböző elemeit és mindegyik elem mellett megadjuk a multiplicitását. Nevezzük ez utóbbi ábrázolást zsák-alaknak. Az előbbi példa zsák-alakja Prologban [a-2,b-1], Erlangban [{a,2},{b,1}]. (A Prolog nyelv konvenciói közé tartozik, hogy a párokat Első-Második alakban írják, azaz a -/2 struktúrával ábrázolják, lásd pl. a keysort/2 beépített eljárást.)

A zsák-alakban is érdektelen a listaelemek sorrendje, tehát ha a fenti példában a két listaelemet megcseréljük, akkor is ugyanazt a zsákot kapjuk. A zsák-alak további fontos tulajdonságai: a párok első tagja nem ismétlődik, és a multiplicitások pozitív egészek.

Írjon olyan Prolog eljárást, illetve Erlang függvényt, amely egy listát zsák-alakra hoz!

Prolog-specifikációk

Írjon Prolog-eljárást lista_zsak/2 néven egy tetszőleges lista zsák-alakjának az előállítására. Feltételezheti, hogy a listaelemek tömör Prolog kifejezések, azaz nem tartalmaznak változót.

% :- type zsak_alak == list(zsak_elem).
% :- type zsak_elem ---> any - int.
% :- pred lista_zsak(list(any)::in, zsak_alak::out).
% lista_zsak(L, Zsak): Az L lista zsák-alakja Zsak.

Erlang-specifikációk

Írjon Erlang-függvényt khf1:lista_zsak/1 néven egy tetszőleges lista zsák-alakjának az előállítására.

%% @type zsak_alak() = [zsak_elem()].
%% @type zsak_elem() = {any(),integer()}.
%% @spec khf1:lista_zsak(L::[any()]) -> Zsak::zsak_alak().
%% Az L lista zsák-alakja Zsak.

A programot tartalmazó modul attribútumai ezek legyenek:

-module(khf1).
-author('email@unit.org.hu').
-vsn('year-mm-dd').
-export([lista_zsak/1]).
%-compile(export_all).

Példák

Prolog

| ?- lista_zsak([], ZS).
ZS = [] ? ;
no

| ?- lista_zsak([a,b,a,b,b], ZS).
ZS = [a-2,b-3] ? ;
no

| ?- lista_zsak([korte,alma,dio,alma,dio,dio,tok], ZS).
ZS = [korte-1,alma-2,dio-3,tok-1] ? ;
no

Erlang

1> khf1:lista_zsak([]).
[]

2> khf1:lista_zsak([a,b,a,b,b]).
[{a,2},{b,3}]

3> khf1:lista_zsak([korte,alma,dio,alma,dio,dio,tok]).
[{korte,1},{alma,2},{dio,3},{tok,1}]

Természetesen mindkét nyelv esetén elfogadjuk azokat a programokat is, amelyek eredményei a fentiektől csak a listaelemek sorrendjében térnek el.

Tudnivalók a beadásról

A programok készülhetnek MS Windows alatt is, de Linux alatt is működniük kell. A beadott programokat Linux környezetben a SICStus Prolog 4.2.x, ill. az Erlang/OTP R14A rendszerekkel teszteljük.

Ennek a kis házi feladatnak a beadása ugyan nem kötelező, azonban a félévközi követelmények teljesítéséhez a félév során legalább három kisházifeladat-megoldást – közülük legalább egyet Prolog és legalább egyet Erlang nyelven – sikeresen be kell adni. Sikeres az a megoldás, amelyik az összes tesztesetre helyes választ ad. Ha ezt a kis házi feladatot mindkét nyelven sikeresen beadja, az természetesen két megoldásnak számit.

A programot az Elektronikus Tanársegéd (ETS) segítségével weben keresztül lehet beadni, a HF beadás menüpont alatt. Ez az egyes számú kis házi feladat, ennek megfelelően az ETS a beküldött megoldást khf1.pl, ill. khf1.erl néven tárolja el és hivatkozik rá. (A feltöltendő állomány neve tetszőleges lehet, az ETS átnevezi.)

Az osztályzat megállapításakor a határidőre beadott, minden tesztesetre helyesen működő feladatmegoldásért plusz 1-1 pont jár.