Deklaratív programozás

1. kis házi feladat

1.2 változat
Utolsó módosítás: 2010-09-23
Kiadás: 2010-09-24
Beadási határidő: Prolog 2010-10-18, 24:00; Erlang 2010-10-25, 24:00

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

khf1:lista_zsak([]).
[]

khf1:lista_zsak([a,b,a,b,b]).
[{a,2},{b,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 programot az Elektronikus Tanársegéddel kell beadni (l. HF beadás menüpont).

A vizsgaosztályzat megállapításakor a határidőre beadott, helyesen megoldott kis házi feladatokért plusz 1-1 pont jár.

dp@inf.bme.hu