Notesclub

created by hec & contributors

terms privacy

DP26a - 2. FP-gyakorlat

gyak-02/fel2.livemd

@gutbrot

dekla-26

Share to X

Share to Bluesky

More notebooks

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(n,3)
  end
  defp upto_by_3(n,i) when i <= n do
    IO.puts(i)
    upto_by_3(n,i+3)
  end
  defp upto_by_3(n,i) when i > n, do: :ok
end
UptoBy3TailR.upto_by_3(20)

Mint már tudjuk, jobbrekurziónak (terminális, ritkábban farokrekurziónak - angolul: tail recursion) nevezzük a rekurzív hívást, ha egy klóz utolsó és egyetlen rekurzív hívása, melynek az eredményével már nem végzünk semmilyen műveletet (a visszaadáson kívül). A jobbrekurzív kódot a modern értelmező- és fordítóprogramok nagyon hatékonyan, iteratív processzként valósítják meg.

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
  def upto_by_3(n) when n <= 0, do: :ok

  def upto_by_3(n) do
    upto_by_3(n - 1)
    if rem(n, 3) == 0 do
      IO.puts(n)
    end
    :ok
  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([x]), do: [x]

  def maxOsszegIndul([x | xr]) do
    [y | _] = ys = maxOsszegIndul(xr)
    [max(x, x + y) | ys]
  end
end

IO.inspect(MaxOsszeg.maxOsszeg([]) == 0)
IO.inspect(MaxOsszeg.maxOsszeg([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6)

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]))

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

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")

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])

Súgó Ha nem ír segédfüggvényt és nincs más ötlete, használhatja a 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([]) === [[]])

Súgó A 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.puts

L6. 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 az Enum.zip/1 fü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([]) === [])

Other notebooks:

Mika Kalathil
@MikaAK

request_cache_test

Benchmarking Request Cache Plug

benchmarking.livemd

tutorial advanced benchee kino_vega_lite

2022-8-18
Ramón Pin
@ramonpin

fastavro

FastAvro Samples

fastavro_samples.livemd

tutorial advanced fastavro vega_lite kino benchee benchee_html

2023-8-27
Axl Mattheus
@axler8r

MachineLearningInElixir

Chapter Two

Chapter02.livemd

tutorial advanced data-science nx exla benchee

2023-9-19
@andyl

livebooks

MLIE Chapter 2

chapter2.livemd

tutorial advanced data-science nx exla benchee

2023-12-4
Ammar Massoud
@ammar-mohamed-massoud

Dockyard-Academy

Rollable Expressions

rollable_expressions.livemd

tutorial intermediate jason kino youtube hidden_cell

2026-7-11
Ammar Massoud
@ammar-mohamed-massoud

Elixir-DockYard

Pascal's Triangle

pascals_triangle.livemd

tutorial intermediate jason kino youtube hidden_cell

2026-7-7
Ammar Massoud
@ammar-mohamed-massoud

Dockyard-Academy

Home Page

home_page.livemd

tutorial beginner jason kino youtube hidden_cell

2026-7-7

Back