Deklaratív programozás

A feladat

Legyen adott egy Mx mátrix és egy f függvény, amely a mátrix minden eleméhez egy számértéket rendel. Jelölje min(f, Mx) az f függvény által az Mx mátrix elemein felvett minimális értéket. Az Mx mátrix azon elemeit nevezzük f-minimálisoknak, amelyekhez az f függvény a min(f, Mx) értéket rendeli.

A feladat egyrészt a min(f, Mx) érték előállítása, másrészt az Mx mátrix f-minimális elemeinek a meghatározása. A mátrix ezen elemeit egy hármassal jellemezzük, amelynek a tagjai: az x koordináta (az oszlop száma, 1-től számozva), az y koordináta (a sor száma, 1-től számozva), a mátrix adott eleme. A feladatot megoldó függvénynek, illetve eljárásnak az f-minimális elemeket leíró hármasok listáját kell előállítania, mégpedig a mátrix sorfolytonos ábrázolásának megfelelő sorrendben.

Erlang-specifikációk

Írjon Erlang-függvényt matrix_min/2 néven, amelynek bemenete egy listák listájaként megadott mátrix és egy F függvény. A függvény eredménye egy olyan pár legyen, amelynek első tagja a függvény által a mátrix elemein felvett minimális érték, második tagja pedig az F-minimális elemeket jellemző hármasok listája!

%% @type xcoord() = integer().
%% @type ycoord() = integer().
%% @type value() = any().
%% @type triple() = {xcoord(),ycoord(),value()}.
%% @type fmin() = value() -> integer().
%% @spec khf1:matrix_min(Mx::[[value()]], F::fmin()) -> {MinMx::integer(), FMinElems::[triple()]}.
%% ahol Mx egy tetszőleges mátrix;
%%      F egy kétargumentumú függvény;
%%      MinMx egy számérték, az F függvény által a mátrix elemein felvett minimális érték;
%%      FMinElems az F-minimális mátrixelemeket jellemző hármasok listája, a mátrix
%%        sorfolytonos ábrázolásának megfelelő sorrendben.

-module(khf1).
-export([matrix_min/2]).

Prolog-specifikációk

Írjon Prolog-eljárást matrix_min/4 néven, amelynek bemenete egy listák listájaként megadott mátrix és egy F függvény. Az eljárás állítsa elő egyrészt a függvény által a mátrix elemein felvett minimális értéket, másrészt az F-minimális elemeket jellemző hármasok listáját!

% :- type xcoord == int.
% :- type ycoord == int.
% :- type value == any.
% :- type triple ---> t(xcoord,ycoord,value).
% :- pred matrix_min(list(list(any))::in, atom::in, number::out, list(triple)::out).
% matrix_min(Mx, F, MinMx, FMinElems), ahol
%   Mx egy tetszőleges mátrix;
%   F egy függvényt megvalósító kétargumentumú eljárás neve;
%   MinMx egy számérték, az F függvény által a mátrix elemein felvett
%     minimális érték;
%   FMinElems az F-minimális mátrixelemeket jellemző hármasok listája, a
%     mátrix sorfolytonos ábrázolásának megfelelő sorrendben.

A megírandó eljárás a függvény-argumentumot egy F atom formájában kapja meg, amely egy kétargumentumú eljárás neve. Az F/2 eljárás meghívásakor az Mx mátrix egy tetszőleges elemét adhatjuk meg első argumentumként, másodikként pedig egy változót. Az F/2 eljárás ez esetben sikeresen lefut, és a második argumentumban visszadja az adott elemhez rendelt függvényértéket.

Egy F nevű, kétargumentumú eljárás A1 és A2 argumentumokkal való meghívására az alább definiált eljárás használható:

call2(F, A1, A2) :-
        Goal =.. [F,A1,A2],
	call(Goal).

| ?- call2(length, [a,b,c], Len).
Len = 3 ? ;
no
| ?- call2(atom_length, abrakadabra, Len).
Len = 11 ? ;
no

Egyes Prolog rendszerekben a fenti funkcionalitás beépített eljárás formájában is rendelkezésre áll (általában call/3 néven). Mivel a SICStus Prolog jelen kurzus során használt 3.12 változatában nem ez a helyzet, kérjük, hogy a a fenti call2/3 eljárásdefiniciót írja be a beadandó programjába.

Példák

Prolog

| ?- matrix_min([[abba,baba,aba,c],[a,ba,b,bab]], atom_length, Min, L).
L = [t(4,1,c),t(1,2,a),t(3,2,b)],
Min = 1 ? ;
no

| ?- [user].
% consulting user...
| neg(X, Y) :- Y is -X.
| 
% consulted user in module user, 10 msec 224 bytes
yes
| ?- matrix_min([[1,3,12],[12, 9, 10]], neg, Min, L).
L = [t(3,1,12),t(1,2,12)],
Min = -12 ? ;
no

| ?- matrix_min([[[3,1],[1,2]],[[9], [10]]], length, Min, L).
L = [t(1,2,[9]),t(2,2,[10])],
Min = 1 ? ;
no

Erlang

2> khf1:matrix_min([[abba,baba,aba,c],[a,ba,b,bab]], fun(A) -> length(atom_to_list(A)) end).
{1,[{4,1,c},{1,2,a},{3,2,b}]}

3> khf1:matrix_min([[1,3,12],[12, 9, 10]], fun(X) -> -X end).
{-12,[{3,1,12},{1,2,12}]}

4> khf1:matrix_min([[[3,1],[1,2]],[[9], [10]]], fun erlang:length/1).
{1,[{1,2,"\t"},{2,2,"\n"}]}

Tudnivalók a beadásról

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.

Gyakorló feladatok

1. Egy L számlista minimumának meghatározása.
2. Egy L számlista minimumának és a minimális elemek indexeinek előállítása.
3. Egy tetszőleges lista adott számfüggvény szerinti minimumának meghatározása.
4. Egy tetszőleges lista adott számfüggvény szerinti minimális elemeinek előállítása (indexeikkel együtt).