DP26a - 2. FP-gyakorlat
Mix.install([
{:benchee, "~> 1.3"}
])Bal-, jobb- és törzsrekurzió
A jobb- és a törzsrekurzióra több példát láttunk már. Most olyan egyszerű feladatok következnek, amelyek a jobb- és a balrekurzió különbségére mutatnak rá.
Mivel a megírandó függvények két vagy több klózból fognak állni, nézzük meg, mit tudunk tenni, ha a hívásra illeszkedő klózt nem lehet csupán mintaillesztéssel kiválasztani.
Ha nem megy mintaillesztéssel...
Már tudjuk, hogy mintában csak tömör, azaz kiértékelhető kifejezés lehet, változót tartalmazó nem. Ilyesmit tehát nem írhatunk le:
...
def fac(n >= 0), do: ...A hasonló esetek elég gyakoriak, ezért a mintát ún. őrrel egészíthetjük ki.
Az őrt a függvényfejben a paraméter(eke)t követő when kulcsszó vezeti be, ami után őrkifejezésnek kell állnia. Az őrkifejezésre vissza fogunk térni, elöljáróban annyit, hogy csak őrként (guard) definiált, garantáltan mellékhatás nélküli könyvtári függvényeket hívhatunk meg benne, más függvényeket nem, így saját függvényeket sem.
...
def fac(n) when n >= 0, do: ...
...Kiírás rekurzív hívás előtt és után
Írjon lineárisan rekurzív függvényeket az alábbi feladatok megoldására direkt rekurzióval. Törekedjen elegáns, tömör, érthető és hatékony függvények írására.
Kiírás a rekurzív hívás előtt
Írjon olyan rekurzív függvényt upto_by_3 néven, amelyik növekvő sorrendben kiírja az $1$ és $n$ közé eső, $n$-nél nem nagyobb, 3-mal osztható természetes számokat! Az $n$-et paraméterként adja át a függvénynek. A rekurzív hívás az adott klóz utolsó hívása, eredménye az adott klóz eredménye legyen, azaz a rekurzív hívás eredményével már ne végezzen semmilyen műveletet: a soron következő számot tehát a rekurzív hívás előtt írja ki. Segédfüggvényt definiálhat. Használjon őrt a minta szerinti feltétel kiegészítésére.
defmodule UptoBy3TailR do
@spec upto_by_3(n :: integer()) :: :ok
def upto_by_3(n) do
IO.puts(i)
...
end
end
UptoBy3TailR.upto_by_3(20)defmodule UptoBy3TailR do
@spec upto_by_3(n :: integer()) :: :ok
def upto_by_3(n), do: upto_by_3(3, n)
defp upto_by_3(i, n) when i <= n do
IO.puts(i)
upto_by_3(i+3, n)
end
defp upto_by_3(i, n) when i > n, do: :ok
end
UptoBy3TailR.upto_by_3(20)Kiírás a rekurzív hívás után
Írja át előző megoldását úgy, hogy a rekurzív hívás az adott klóz első hívása legyen, azaz a rekurzív hívás előtt ne végezzen semmilyen műveletet: a soron következő számot tehát a rekurzív hívás után írja ki. Az eredményt továbbra is növekvő sorrendben írja ki. Segédfüggvényt definiálhat.
defmodule UptoBy3HeadR do
@spec upto_by_3(n :: integer()) :: :ok
def upto_by_3(n) do
...
IO.puts(i)
end
end
UptoBy3HeadR.upto_by_3(20)defmodule UptoBy3HeadR do
@spec upto_by_3(n :: integer()) :: :ok
#when n > 0, mert ha n < 0, akkor vegtelen ciklus
def upto_by_3(n) when n>0, do: downto_by_3(n - rem(n, 3))
defp downto_by_3(0), do: :ok
defp downto_by_3(i) do
downto_by_3(i - 3)
IO.puts(i)
end
end
UptoBy3HeadR.upto_by_3(20)Vesse össze a két függvényalkalmazás által kiírt számsorozatot! Miben különbözik a kétféle megoldás veremhasználata?
A második változatban alkalmazott rekurzív hívást balrekurziónak (fejrekurziónak - angolul: head recursion) nevezzük: a balrekurzív hívás egy klóz első és egyetlen rekurzív hívása. SúgóElőfordulhat, hogy a második változata nem teljesíti a specifikációt, hogy ti. növekvő sorrendben kell kiírni a számokat. Ezen úgy segíthet, hogy nem 1-től felfelé halad a generáláskor, hanem $n$-től lefelé.
Az $n$-tő lefelé való haladásnak az a járulékos előnye itt és hasonló esetekben, hogy a végállomás a 0 (esetleg más előre tudható konstans) lesz, így lehet csak mintaillesztést használni, ami hatékonyabb, mintha őrt is használnánk.
Ha tehát őrt használt volna most is, cserélje le pusztán mintaillesztésre. Használjon segédfüggvényt.
Maximális összegű intervallum
Legyen $\mathit{xs}$ egy $n$ elemű, egész (de nem feltétlenül pozitív) számokból álló lista. Jelölje $\mathit{xs}[i]$ az $\mathit{xs}$ $i$. elemét és $\mathit{xs}[i\ldots{}j]$ az $\mathit{xs}$ $i$. elemétől $j$. eleméig tartó összefüggő részlistáját. Határozza meg az $$ r = \max_{0 \le i \le j < n} \sum_{i \le k \le j} \mathit{xs}[k] $$ értékét, azaz az $\mathit{xs}$ legnagyob összegű egybefüggő $\mathit{xs}[i\ldots{}j]$ részlistájának az összegét.
Ez a feladat szerepelt az Algoritmuselmélet tárgy Dinamikus programozás diasorában.
Ebben a feladatban egy $\mathit{ys}$ segédlistát állítunk elő dinamikus programozással, ahol $$ ys[i] = \max_{i \le j < n} \sum_{i \le k \le j} \mathit{xs}[k] \text. $$
Valósítsa meg a segédlistát előállító maxOsszegIndul függvényt! A megoldásnak nem feltétlenül szükséges jobbrekurzívnak lennie.
defmodule MaxOsszeg do
@spec maxOsszeg(xs :: [number()]) :: r :: number()
# Az r szám az xs összefüggő részlistái közül a legnagyobb összegű elemeinek az összege.
def maxOsszeg(xs) do
# A maxOsszegIndul lista elemeit az >=/2 segítségével hasonlítjuk össze,
# üres lista esetén a visszatérési érték legyen 0.
maxOsszegIndul(xs) |> Enum.max(&>=/2, fn -> 0 end)
end
@spec maxOsszegIndul(xs:: [number()]) :: ys :: [number()]
# Az ys lista i. eleme az xs i. elemétől induló összefüggő részlistái közül
# a legnagyobb összegű elemeinek az összege.
def maxOsszegIndul(...) do
...
end
end
IO.inspect(MaxOsszeg.maxOsszeg([]) == 0)
IO.inspect(MaxOsszeg.maxOsszeg([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6)
IO.inspect(MaxOsszeg.maxOsszegIndul([-2, 1, -3, 4, -1, 2, 1, -5, 4]))defmodule MaxOsszeg do
@spec maxOsszeg(xs :: [number()]) :: r :: number()
# Az r szám az xs összefüggő részlistái közül a legnagyobb összegű elemeinek az összege.
def maxOsszeg(xs) do
# A maxOsszegIndul lista elemeit az >=/2 segítségével hasonlítjuk össze,
# üres lista esetén a visszatérési érték legyen 0.
maxOsszegIndul(xs) |> Enum.max(&>=/2, fn -> 0 end)
end
@spec maxOsszegIndul(xs:: [number()]) :: ys :: [number()]
# Az ys lista i. eleme az xs i. elemétől induló összefüggő részlistái közül
# a legnagyobb összegű elemeinek az összege.
def maxOsszegIndul([]), do: []
def maxOsszegIndul([h|t]) do
ys2 = maxOsszegIndul(t)
case ys2 do
[y2|_] when y2 > 0 -> [h + y2 | ys2]
_ -> [h | ys2]
end
end
end
IO.inspect(MaxOsszeg.maxOsszeg([]) == 0)
IO.inspect(MaxOsszeg.maxOsszeg([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6)
IO.inspect(MaxOsszeg.maxOsszegIndul([-2, 1, -3, 4, -1, 2, 1, -5, 4]))Legyen most $\mathit{zs}$ az $\mathit{xs}$ adott indexű elemeinél végződő összefüggő listák összege, azaz
$$
zs[j] = \max_{0 \le i \le j} \sum_{i \le k \le j} \mathit{xs}[k] \text.
$$
Valósítsa meg a segéd adatstruktúrát előállító maxOsszegVege jobbrekurzív függvényt! A megoldásban az Elixir Map adatszerkezetét használjuk.
defmodule MaxOsszeg2 do
@spec maxOsszeg2(xs :: [number()]) :: r :: number()
# Az r szám az xs összefüggő részlistái közül a legnagyobb összegű elemeinek az összege.
def maxOsszeg(xs) do
# A maxOsszegVege Map elemeit az >=/2 segítségével hasonlítjuk össze,
# üres Map esetén a visszatérési érték legyen 0.
maxOsszegVege(xs) |> Map.values() |> Enum.max(&>=/2, fn -> 0 end)
end
@spec maxOsszegVege(xs:: [number()]) :: zs :: %{ number() => number() }
# Az zs j-hez tartozó eleme az xs j. eleménél végződő összefüggő részlistái közül
# a legnagyobb összegű elemeinek az összege.
def maxOsszegVege(...), do: ...
end
IO.inspect(MaxOsszeg2.maxOsszeg([]) == 0)
IO.inspect(MaxOsszeg2.maxOsszeg([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6)
IO.inspect(MaxOsszeg2.maxOsszegVege([-2, 1, -3, 4, -1, 2, 1, -5, 4]))defmodule MaxOsszeg2 do
@spec maxOsszeg(xs :: [number()]) :: r :: number()
# Az r szám az xs összefüggő részlistái közül a legnagyobb összegű elemeinek az összege.
def maxOsszeg(xs) do
# A maxOsszegVege Map elemeit az >=/2 segítségével hasonlítjuk össze,
# üres Map esetén a visszatérési érték legyen 0.
maxOsszegVege(xs) |> Map.values() |> Enum.max(&>=/2, fn -> 0 end)
end
@spec maxOsszegVege(xs:: [number()]) :: zs :: %{ number() => number() }
# Az zs j-hez tartozó eleme az xs j. eleménél végződő összefüggő részlistái közül
# a legnagyobb összegű elemeinek az összege.
def maxOsszegVege(xs), do: maxOsszegVege(xs, 0, %{})
defp maxOsszegVege([], _, zs), do: zs
defp maxOsszegVege([h|t], j, zs) do
z1 = case Map.fetch(zs, j - 1) do
{:ok, z} when z > 0 -> h + z
_ -> h
end
zs1 = Map.put(zs, j, z1)
maxOsszegVege(t, j + 1, zs1)
end
end
IO.inspect(MaxOsszeg2.maxOsszeg([]) == 0)
IO.inspect(MaxOsszeg2.maxOsszeg([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6)
IO.inspect(MaxOsszeg2.maxOsszegVege([-2, 1, -3, 4, -1, 2, 1, -5, 4]))Műveletek listákon
Írjon többféle megoldást a feladatokra: saját rekurzív függvényekkel, különféle könyvtári függvények felhasználásával, for-komprehenzióval.
Hasonlítsa össze a megoldások futási idejét a benchee-vel, próbáljon hatékonyabb kódot írni pl. jobbrekurzióval.
L1. Lista kettévágása
Írjon függvényt egy lista kettévágására! Írhat segédfüggvényt, használhat akkumulátort és jobbrekurziót, használhatja a for-jelölést.
Ne használja az Enum.split*, Enum.take* és Enum.drop* függvények semelyik változatát a split/2 függvény megvalósítására! (De bármilyen könyvtári függvényt használhat az eredmény ellenőrzésére.)
defmodule Split do
@spec split(xs :: [any()], n :: integer()) :: {ps :: [any()], ss :: [any()]}
# Az xs lista n hosszú prefixuma (első n eleme) ps, length(xs)-n
# hosszú szuffixuma (első n eleme utáni része) pedig ss
def split(xs, n) do
...
end
end
IO.puts(Split.split([10, 20, 30, 40, 50], 3) === {[10, 20, 30], [40, 50]})
IO.puts(IO.inspect(Split.split(~c"egyedem-begyedem", 8)) === Enum.split(~c"egyedem-begyedem", 8))
IO.puts(IO.inspect(Split.split(~c"papás-mamás", 6)) === Enum.split(~c"papás-mamás", 6))
IO.puts(Split.split(~c"nem_vágom", 0) === Enum.split(~c"nem_vágom", 0))
IO.puts(Split.split(~c"", 10) === Enum.split(~c"", 10))
IO.puts(Split.split(~c"", 0) === Enum.split(~c"", 0))defmodule Split1 do
@spec split(xs :: [any()], n :: integer()) :: {ps :: [any()], ss :: [any()]}
# Az xs lista n hosszú prefixuma (első n eleme) ps, length(xs)-n
# hosszú szuffixuma (első n eleme utáni része) pedig ss
def split(xs, 0), do: { [], xs }
def split([x|xs], n) do
{ ps, ss } = split(xs, n-1)
{ [x|ps], ss }
end
def split([], _), do: { [], [] }
end
IO.puts(Split1.split([10, 20, 30, 40, 50], 3) === {[10, 20, 30], [40, 50]})
IO.puts(IO.inspect(Split1.split(~c"egyedem-begyedem", 8)) === Enum.split(~c"egyedem-begyedem", 8))
IO.puts(IO.inspect(Split1.split(~c"papás-mamás", 6)) === Enum.split(~c"papás-mamás", 6))
IO.puts(Split1.split(~c"nem_vágom", 0) === Enum.split(~c"nem_vágom", 0))
IO.puts(Split1.split(~c"", 10) === Enum.split(~c"", 10))
IO.puts(Split1.split(~c"", 0) === Enum.split(~c"", 0))defmodule Split2 do
@spec split(xs :: [any()], n :: integer()) :: {ps :: [any()], ss :: [any()]}
# Az xs lista n hosszú prefixuma (első n eleme) ps, length(xs)-n
# hosszú szuffixuma (első n eleme utáni része) pedig ss
def split(xs, n), do: split(xs, n, [])
defp split([x|xs], n, ps) when n > 0, do: split(xs, n-1, [x|ps])
defp split(xs, 0, ps), do: { Enum.reverse(ps), xs }
defp split([], _, ps), do: { Enum.reverse(ps), [] }
end
IO.puts(Split2.split([10, 20, 30, 40, 50], 3) === {[10, 20, 30], [40, 50]})
IO.puts(IO.inspect(Split2.split(~c"egyedem-begyedem", 8)) === Enum.split(~c"egyedem-begyedem", 8))
IO.puts(IO.inspect(Split2.split(~c"papás-mamás", 6)) === Enum.split(~c"papás-mamás", 6))
IO.puts(Split2.split(~c"nem_vágom", 0) === Enum.split(~c"nem_vágom", 0))
IO.puts(Split2.split(~c"", 10) === Enum.split(~c"", 10))
IO.puts(Split2.split(~c"", 0) === Enum.split(~c"", 0))ls = Range.to_list(0..100_000)
n = 70_000
Benchee.run(%{
"split1" => fn -> Split1.split(ls, n) end,
"split2" => fn -> Split2.split(ls, n) end,
"enumSplit" => fn -> Enum.split(ls, n) end
})L2. Lista adott feltételt kielégítő elemeiből álló prefixuma
Írjon függvényt egy lista adott feltételt kielégítő prefixumának előállítására. Írhat segédfüggvényt, használhat akkumulátort és jobbrekurziót, használhatja a for-jelölést.
Ne használja az Enum.split*, Enum.take* és Enum.drop* függvények semelyik változatát a takewhile/2 függvény megvalósítására! (De bármilyen könyvtári függvényt használhat az eredmény ellenőrzésére.)
defmodule Take do
@spec takewhile(xs :: [any()], f :: (any() -> boolean())) :: rs :: [any()]
def takewhile(xs, f) do
...
end
end
IO.puts(Take.takewhile(~c"álom12" ++ [:a] ++ ~c"34brigád", &is_integer/1) === ~c"álom12")
IO.puts(Take.takewhile(~c"abcdefghijkl", fn x -> x < ?f end) === ~c"abcde")defmodule Take1 do
@spec takewhile(xs :: [any()], f :: (any() -> boolean())) :: rs :: [any()]
def takewhile([x|xs], f) do
if f.(x) do
[x|takewhile(xs, f)]
else
[]
end
end
def takewhile([], _f), do: []
end
IO.puts(Take1.takewhile(~c"álom12" ++ [:a] ++ ~c"34brigád", &is_integer/1) === ~c"álom12")
IO.puts(Take1.takewhile(~c"abcdefghijkl", fn x -> x < ?f end) === ~c"abcde")defmodule Take2 do
@spec takewhile(xs :: [any()], f :: (any() -> boolean())) :: rs :: [any()]
def takewhile(xs, f), do: takewhile(xs, f, [])
defp takewhile([x|xs], f, acc) do
if f.(x) do
takewhile(xs, f, [x|acc])
else
Enum.reverse(acc)
end
end
defp takewhile([], _f, acc), do: Enum.reverse(acc)
end
IO.puts(Take2.takewhile(~c"álom12" ++ [:a] ++ ~c"34brigád", &is_integer/1) === ~c"álom12")
IO.puts(Take2.takewhile(~c"abcdefghijkl", fn x -> x < ?f end) === ~c"abcde")ls = Range.to_list(0..100_000)
f = fn x -> x < 70_000 end
Benchee.run(%{
"take1" => fn -> Take1.takewhile(ls, f) end,
"take2" => fn -> Take2.takewhile(ls, f) end,
"enumTake" => fn -> Enum.take_while(ls, f) end
})L3. Lista minden n-edik elemének kihagyásával létrejövő lista
Írjon függvényt egy olyan lista létrehozására, amelyikből a paraméterként átadott lista minden n-edik eleme, a nulladiktól kezdve, ki van hagyva. (A listák indexelése, mint tudjuk, a 0-val kezdődik.)
Ne használja az Enum.split*, Enum.take* és Enum.drop* függvények semelyik változatát a dropevery/2 függvény megvalósítására! (De bármilyen könyvtári függvényt használhat az eredmény ellenőrzésére.)
defmodule Drop do
@spec dropevery(xs :: [any()], n :: integer()) :: rs :: [any()]
def dropevery(xs, n) do
...
end
end
ls = ~c"álom" ++ [:a] ++ ~c"egybrigád"
IO.inspect(Drop.dropevery(ls, 4) === ~c"lomegyrigd")
ls = ~c"abcdefghijkl"
IO.inspect(Drop.dropevery(ls, 5) === ~c"bcdeghijl")
ls = ~c"1234567"
IO.inspect(Drop.dropevery(ls, 2) === ~c"246")
ls = []
IO.inspect(Drop.dropevery(ls, 3) === [])
ls = [:a, :b, :c, :d, :e, :f, :g, :h, :i, :j, :k, :l, :m]
IO.inspect(Drop.dropevery(ls, 3) === [:b, :c, :e, :f, :h, :i, :k, :l])for-jelölést, generátoraként a ../2, szűrőjeként a rem/2 függvényeket, a listaelemek elérésére pedig a Enum.at/2 függvényt.
L4. Lista egyre rövidülő szuffixumainak listája
defmodule Tails do
@spec tails(xs :: [any()]) :: zss :: [[any()]]
# Az xs lista egyre rövidülő szuffixumainak listája zss
def tails(xs) do
...
end
end
IO.puts(Tails.tails([1, 4, 2]) === [[1, 4, 2], [4, 2], [2], []])
IO.puts(Tails.tails([:a, :b, :c, :d]) === [[:a, :b, :c, :d], [:b, :c, :d], [:c, :d], [:d], []])
IO.puts(Tails.tails([:z]) === [[:z], []])
IO.puts(Tails.tails([]) === [[]])tails függvénynek listák listája az eredménye, így ha üres listára alkalmazzuk, akkor olyan lista lesz a visszatérési értéke, melynek egyetlen eleme van, az üres lista.
L5. Lista egymást követő két-két eleméből képzett párok listája
Írjon olyan rekurzív függvényt, amelyik egy lista 1. és 2., 3. és 4., 5. és 6. s.í.t. elemeiből képzett párok listáját adja eredményül. Ha a listának kettőnél kevesebb eleme van, az eredmény az üres lista legyen. Ha a listának páratlan számú eleme van, az utolsót dobja el.
defmodule Pairs do
@spec pairs(xs::[any()]) :: zs :: [any()]
def pairs(xs), do: ...
end
zs = [{1,2}, {3,4}, {5,6}, {7,8}, {9,10}, {11,12}, {13,14}, {15,16}, {17,18}, {19,20}]
(1..20 |> Range.to_list() |> Pairs.pairs() == zs) |> IO.puts
zs = [{1,2}, {3,4}, {5,6}, {7,8}, {9,10}]
(1..11 |> Range.to_list() |> Pairs.pairs() == zs) |> IO.puts
([1] |> Pairs.pairs() == []) |> IO.puts
([1] |> Pairs.pairs() == []) |> IO.putsL6. Listában párosával előforduló elemek listája
Írjon olyan rekurzív függvényt, amelyik egy lista elemei közül az összes olyat visszaadja az eredménylistában, amelyet vele azonos értékű elem követ, azaz például két egymást követő, azonos értékű elemből egyet, három egymást követőből kettőt stb. Írhat
- segédfüggvényt és akkumulátort nem használó, valamint
- akkumulátoros segédfüggvényt használó változatot.
Próbáljon meg egyéb változatokat is írni, pl.
- a
for-jelöléssel és azEnum.zip/1függvény alkalmazásával.
defmodule Parosan do
@spec parosan(xs :: [any()]) :: rs :: [any()]
# Az xs lista összes olyan elemének listája rs, amely
# után vele azonos értékű elem áll
def parosan xs do
...
end
end
IO.puts(Parosan.parosan([:a, :a, :a, 2, 3, 3, :a, 2, :b, :b, 4, 4]) === [:a, :a, 3, :b, 4])
IO.puts(Parosan.parosan([:a, 2, 3, :a, 2, :b, 4]) === [])
IO.puts(Parosan.parosan([:a]) === [])
IO.puts(Parosan.parosan([]) === [])
