Deklaratív programozás, 2. gyakorlat Erlang programozás 2014. 09. 25. Megjegyzés: néhány feladathoz segítséget talál a feladatsor végén. --------------------------------------------------------------------------- Írjon olyan Erlang-függvényt, amely megfelel az adott fejkommentnek. A feladat megoldásához felhasználhat korábbi sorszámú feladatokban definiált eljárásokat. Néhány feladathoz segítséget talál a feladatsor végén. --------------------------------------------------------------------------- 1. Számlista minden elemének növelése %% @spec lista_noveltje(L0::[number()]) -> L::[number()]. %% Az L egészlista az L0 egészlistának olyan másolata, amelynek %% ugyanannyi eleme van, mint az L0-nak, de minden eleme pontosan %% eggyel nagyobb értékű, mint az L0 megfelelő eleme. lista_noveltje([1,5,2]) =:= [2,6,3]. --------------------------------------------------------------------------- 2. Lista utolsó elemének meghatározása (vö lists:last/1) %% @spec last(Xs::[term()]) -> X::term(). %% X az Xs nemüres lista utolsó eleme. last([5,1,2,8,7]) =:= 7. --------------------------------------------------------------------------- 3. Lista utolsó elemének meghatározása hibakezeléssel %% @spec safe_last(Xs::[term()]) -> {ok, X::term()} | error. %% Ha Xs üres, akkor 'error', különben X az Xs lista utolsó eleme. safe_last([5,1,2,8,7]) =:= {ok,7}. safe_last([]) =:= error. Megjegyzés: az Erlangban gyakori, hogy a helyes eredményt egy kételemű ennesbe csomagolja a függvény, a hibát pedig egy atommal jelzi. Példa: compile:file/1 (fordítás, shellből: c/1). Mutassa be, hogyan használható a safe_last függvény (tipp a végén). --------------------------------------------------------------------------- 4. Lista adott sorszámú eleme (lists:nth/2) %% @spec nth(N::integer(), L::[term()]) -> E::term(). %% Az L lista N-edik eleme E (1-től számozva az elemeket). nth(3, [a,b,c]) =:= c. --------------------------------------------------------------------------- 5. Lista kettévágása (vö lists:split/2) %% @spec split(N::integer(), L::[term()]) -> {P::[term()], S::[term()]}. %% P lista az L lista N hosszú prefixuma, %% S lista az L lista (length(L) - N) hosszú szuffixuma. split(3, [10,20,30,40,50]) =:= {[10,20,30],[40,50]}. --------------------------------------------------------------------------- 6. Lista adott hosszúságú prefixuma (vö lists:sublist/2) %% @spec take(L0::[term()], N::integer()) -> L::[term()]. %% Az L lista az L0 lista N hosszú prefixuma. take([10,20,30,40,50], 3) =:= [10,20,30]. --------------------------------------------------------------------------- 7. Lista szuffixuma (vö lists:nthtail/2) %% @spec drop(L0::[term()], N::integer()) -> L::[term()]. %% Az L0 lista olyan szuffixuma L, amely az L0 első B elemét %% nem tartalmazza. drop([10,20,30,40,50], 3) =:= [40,50]. --------------------------------------------------------------------------- 8. Lista egyre rövidülő szuffixumainak listája %% @spec tails(Xs::[term()]) -> Zss::[[term()]]. %% A Zss lista az Xs listát és egyre rövidülő szuffixumait tartalmazza. tails([1,4,2]) =:= [[1,4,2],[4,2],[2],[]]. tails([a,b,c,d,e]) =:= [[a,b,c,d,e],[b,c,d,e],[c,d,e],[d,e],[e],[]]. --------------------------------------------------------------------------- 9. Lista összes prefixumának listája %% @spec prefixes(Xs::[term()]) -> Zss::[[term()]] prefixes([a,b,c]) =:= [[], [a], [a,b], [a,b,c]]. --------------------------------------------------------------------------- 10. Lista adott hosszúságú összes részlistáját tartalmazó lista %% sublists(N::integer(), Xs::[term()]) -> %% [{B::integer(), Ps::[term()], A::integer()}]. %% Az Xs lista egy olyan (folytonos) részlistája az N hosszúságú Ps lista, %% amely előtt B és amely után A számú elem áll Xs-ben. sublists(1,[a,b,c]) =:= [{0,[a],2}, {1,[b],1}, {2,[c],0}]. sublists(2,[a,b,c]) =:= [{0,[a,b],1}, {1,[b,c],0}]. --------------------------------------------------------------------------- 11. Listában párosával előforduló elemek listája %% @spec parban(Xs::[term()]) -> Zs::[term()]. %% A Zs lista az Xs lista összes olyan elemét tartalmazza, amelyet %% vele azonos értékű elem követ. parban([a,a,a,2,3,3,a,2,b,b,4,4]) =:= [a,a,3,b,4]. --------------------------------------------------------------------------- 12. Az 1. feladat (lista_noveltje/1) újbóli megoldása listanézettel --------------------------------------------------------------------------- 13. A közismert map/2, filter/2 függvények megvalósítása listanézettel Paros = fun(X) -> X rem 2 =:= 0 end. map(Paros, [1,2,3,4]) =:= [false,true,false,true]. filter(Paros, [1,2,3,4]) =:= [2,4]. --------------------------------------------------------------------------- 14. Lista részlistája %% @spec sublist(L0::[term()], S::integer(), N::integer()) -> L::[term()]. %% Az L lista az L0 lista N hosszú részlistája az S. elemmel kezdve. sublist([a,b,c], 2, 1) =:= [b]. sublist([a,b,c], 2, 2) =:= [b,c]. sublist([a,b,c], 2, 3) =:= [b,c]. A megoldást valósítsa meg többféleképpen is: a) take/2 és drop/2 felhasználásával. b) Használja fel listanézetben az nth/2 függvényt. --------------------------------------------------------------------------- 15. Egy lista "értékei": a {v,Ertek} alakú párjainak második tagjai. %% @spec vertekek(Xs::[term()]) -> Ertekek::[term()]. vertekek([alma, {s,3}, {v,1}, 3, {v,2}]) =:= [1,2]. --------------------------------------------------------------------------- 16. Listák összefűzése a lists:foldr/3 függvénnyel %% @spec append(Xs::[term()], Ys::[term()]) -> Zs::[term()]. %% A Zs lista az Xs és Ys összefűzésével áll elő (Zs =:= Xs ++ Ys). append([a,b,c], [1,2,3]) =:= [a,b,c,1,2,3]. --------------------------------------------------------------------------- 17. Egy lista megfordítása egy másik elé fűzve a lists:foldl/3 függvénnyel %% @spec revapp(Xs::[term()], Ys::[term()]) -> Zs::[term()]. %% A Zs lista az Xs megfordítottjának az Ys elé fűzésével áll elő, %% azaz Zs =:= lists:reverse(Xs)++Ys. revapp([a,b,c], [1,2,3]) =:= [c,b,a,1,2,3]. --------------------------------------------------------------------------- 18. A 7. feladat (tails/1) újbóli megoldása a foldr/3 függvénnyel --------------------------------------------------------------------------- 19. A 7. feladat (tails/1) újbóli megoldása listanézettel --------------------------------------------------------------------------- 20. A 9-10. feladatok (sublists/*) újbóli megoldása listanézettel --------------------------------------------------------------------------- 21. A 11. feladat (parban/1) újbóli megoldása listanézettel --------------------------------------------------------------------------- 22. Listában párosával előforduló részlisták listája %% @spec dadogo(Xs::[term()]) -> Zss::[[term()]]. %% A Zss lista az Xs lista összes olyan nemüres (folytonos) részlistáját %% tartalmazza, amelyet vele azonos értékű részlista követ. dadogo([a,a,a,2,3,3,a,b,b,b,b]) =:= [[a],[a],[3],[b],[b,b],[b],[b]]. --------------------------------------------------------------------------- 23. Lista kilapítása (lists:flatten/1) %% @spec flatten(DeepList::list()) -> L::list(). %% A DeepList - tetszőleges mélységű beágyazott listákban tartalmazott - %% elemeit az L listában "kibontva" tartalmazza úgy, hogy az L listában %% már nem szerepel elemként további lista. flatten([1,[2,3],[[[[4]]],[5,[6]]]]) =:= [1,2,3,4,5,6]. Megjegyzés: naív változathoz használható a lists:append/2 (++). * Szorgalmi: append nélkül, flatten/2 segédfüggvény bevezetésével. --------------------------------------------------------------------------- SEGÍTSÉG A MEGOLDÁSHOZ 3. Használat: pl. a case szerkezettel eldönthető, hogy történt-e hiba. 9. Javasolt segédfüggvény: lista legalább N hosszú prefixumainak listája. Hasznos BIF: length(L) az L lista hossza. 16. Érdemes összevetni az előadáson szerepelt append/2 és a foldr/3 függvények kódját. Javasolt segédfüggvény: a Céklából ismert cons/2. 17. Hasonlóan 16. feladathoz. 19. "Ciklus" szervezésére használja a lists:seq/2 függvényt. %% @spec lists:seq(N::integer(), M::integer()) -> S::[integer()]. %% S =:= [N,N+1,...,M], pl. lists:seq(1, length("abc")) =:= [1,2,3]. --------------------------------------------------------------------------- TOVÁBBI GYAKORLÓ FELADATOK OTTHONRA +1. Beszúrás listába adott helyre %% @spec insert_nth(Ls::[term()], E::term(), N::integer()) -> Rs::[term()]. %% Az Rs lista az Ls lista olyan másolata, amelybe az Ls lista N-edik és %% (N+1)-edik eleme közé be van szúrva az E elem (a lista számozása 1-től %% kezdődik). insert_nth([1,8,3,5], 6, 2) =:= [1,8,6,3,5]. insert_nth([1,3,8,5], 3, 3) =:= [1,3,8,3,5]. +2. Beszúrás rendezett listába %% @spec insert_ord(S0s::[term()], E::term()) -> Ss::[term()]. %% Az Ss szigorúan monoton növekvő egészlista az S0s szigorúan monoton %% növekvő egészlistának az E egésszel bővített változata, feltéve hogy %% E nem eleme az S0s listának; egyébként Ss =:= S0s. insert_ord([1,3,5,8], 6) =:= [1,3,5,6,8]. insert_ord([1,3,5,8], 3) =:= [1,3,5,8]. +3. Adott lista sorszámozott elemeiből álló lista (vö lists:zip, lists:seq) %% @spec zipseq(Ls::term()) -> {N::integer(), E::term()}. %% Az Ls lista N-edik eleme E (1-től számozva az elemeket). zipseq([a,b,c]) =:= [{1,a},{2,b},{3,c}]. +4. Lista darabokra szabdalása %% @spec slash(F::fun([term()]) -> {term(),[term()]}, Xs::([term()])) %% -> Zs::([term()]). %% A Zs lista az Xs listából az F ismételt alkalmazásával előálló lista, %% ahol F párban visszaadja a Zs következő elemét és az Xs még nem %% feldolgozott részét. slash(fun(Xs) -> lists:split(3, Xs) end, "jaaaj!!! nem jooo!") =:= ["jaa","aj!","!! ","nem"," jo","oo!"]. +5. Lista monoton növekvő részlistáinak (futamainak) listája %% @spec rampak(Xs::[term()]) -> Xss::[[term()]]. %% Az Xss az Xs monoton növekvő futamainak listája. rampak([1,2,2,3,2,4,5,6,7,6,8,2,3,3,4,5,6,0,6,5,4,3,2,1]) =:= [[1,2,2,3],[2,4,5,6,7],[6,8],[2,3,3,4,5,6],[0,6],[5],[4],[3],[2],[1]]. %% Alternatív megoldás: rampak/1 slash függvénnyel. +6. Lista számtani sorozatot alkotó prefixuma %% @spec dif(Ls::[number()]) -> {Ds::[number()], Zs::[number()]}. %% A Ds lista az Ls lista számtani sorozatot alkotó prefixuma, a Zs az Ls %% maradéka (Zs utáni része). %%%% Segédfüggvény gyûjtőargumentummal. %% @spec dif(Ls::[number()],N::number(),Rs::[number()]) -> %% {Ds::[number()], Zs::[number()]}. %% A Ds lista az Ls lista N különbségû számtani sorozatot alkotó prefixuma %% az Rs lista fordítottja mögé fûzve, a Zs az Ls maradéka (Zs utáni része). dif([1,2,3,4,8,16,32,33,34]) =:= {[1,2,3,4],[8,16,32,33,34]}. dif([1,2,3,4,8,16,24,32,33,34]) =:= {[1,2,3,4],[8,16,24,32,33,34]}. %% Alternatív megoldás: dif/1 feltétel helyett mintaillesztéssel. +7. Lista számtani sorozatot alkotó részlistáinak listája %% @spec difek(Xs::[number()]) -> Dss::[[number()]]. %% A Dss lista az Xs lista számtani sorozatot alkotó részlistáinak listája. difek([1,2,3,4,8,16,32,33,34]) =:= [[1,2,3,4],[8,16],[32,33,34]]. difek([1,2,3,4,8,16,24,32,33,34]) =:= [[1,2,3,4],[8,16,24,32],[33,34]]. %% Alternatív megoldás: difek/1 slash függvénnyel. %% Feladat: úgy módosítani dif/1-et, hogy ha egy szám az egyik %% számtani sorozat utolsó és egyben a következő első eleme is %% lehet, akkor mindkettőben vegyük figyelembe %% NB. Ilyenkor egy sorozat záróeleme mindenképpen egy következő %% sorozat kezdőeleme is lesz egyben, hiszen már két elem is %% számtani sorozatot alkot. slash(fun dif1/1,[1,2,3,4,5,6,7,8,16,24,32,33,34]) =:= [[1,2,3,4,5,6,7,8],[8,16,24,32],[32,33,34]]. slash(fun dif1/1,[1,2,3,4,5,6,7,16,24,32,33,34]) =:= [[1,2,3,4,5,6,7],[7,16],[16,24,32],[32,33,34]]. +8. Listák összefűzése (vö laposítás, lists:flatten/1) %% @spec flatten(Xss::[[term()]]) -> Xs::[term()]. %% Xs lista elemei az Xss-ben lévő listák elemei egymás után fűzve. +9. Mátrix részmátrixa, valósítsa meg többféleképpen is %% @spec kozepe(M::[[term()]]) -> M1::[[term()]]. %% M1 az M n*n-es négyzetes mátrix olyan (n/2)*(n/2) méretű részmátrixa, %% mely az n/4+1. sor n/4+1. oszlopának elemétől kezdődik. M=[[a,b,e,f], [c,d,g,h], [i,j,m,n], [k,l,o,p]], kozepe(M) =:= [[d,g],[j,m]]. a) Használja fel listanézetben a lists:sublist/3 függvényt: %% @spec sublist(L1::list(), S::int(), L::int()) -> L2::list(). b) Használja fel listanézetben az lists:nth/2 függvényt: %% @spec nth(N::int(), List::list()) -> Elem::term(). +10. Mátrix középső elemei, valósítsa meg többféleképpen is %% @spec laposkozepe((M::[[term()]]) -> L::[term()]. %% L lista az M mátrix közepe elemeinek listája. laposkozepe(M) =:= [d,g,j,m]. a) flatten/1 és kozepe/1 felhasználásával. b) Használja fel listanézetben az lists:nth/2 függvényt. +11. Részmátrix sor és oszlop elhagyásával %% @spec pivot((M::[[term()]], R::int(), C::int()) -> M1::[[term()]]. %% M1 az M mátrix R. sorának és C. oszlopának elhagyásával keletkezik. pivot(M,2,3) =:= [[a,b,f],[i,j,n],[k,l,p]]. A megoldáshoz használja fel listanézetben az lists:nth/2 függvényt. +12. Lista összes nemüres részlistáját tartalmazó lista %% sublists(Xs::[term()]) -> [{B::integer(), Ps::[term()], A::integer()}]. %% Az Xs lista egy olyan (folytonos), nemüres részlistája a %% Ps lista, amely előtt B és amely után A számú elem áll Xs-ben. sublists([a,b]) =:= [{0,[a],1}, {1,[b],0}, {0,[a,b],0}]. ------ $LastChangedDate: 2014-11-02 15:37:36 +0100 (Sun, 02 Nov 2014) $ --------