Deklaratív programozás

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

% :- 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

-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.

-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.4.x, ill. az Erlang/OTP R16B rendszerekkel teszteljük.

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.