Zajímavé příklady

Zde uvádím některé zajímavé příklady jako motivaci toho, co se (mimo jiné) můžete dozvědět na přednášce.

Následující funkce by fungovala jen při líném vyhodnocování. Jelikož má Scala call-by-value vyhodnocování, nebude fungovat, zacyklí se.

  def y[A](f: A => A): A =
    f(y(f))

Svojí funkcí odpovídá λ-termu klasického kombinátoru: Y = λf.(λx.f(xx))(λx.f(xx)).

V λ-kalkulu získáme z Y kombinátoru jeho variantu použitelnou pro striktní vyhodnocování tak, že na term xx (zachycující rekurzivní volání) aplikujeme η-expanzi: Y' = λf.(λx.f(λz.xxz))(λx.f(λz.xxz)).

Rekurzivnímu volání v našem případě odpovídá výraz y(f). Můžeme definici ve Scale upravit analogickým způsobem:

  def y[A](f: (A => A) => (A => A)): (A => A) =
    f((z : A) => y(f)(z));

Zde již rekurze bude fungovat, protože výraz (x : A) ⇒ y(f)(x) nelze vyhodnotit, takže ta se dosadí do f tak, jak je. Vyhodnotí až tehdy, když jej f aplikuje na nějaký argument typu A. Povšimněte si, že díky změně je typ argumentu f méně obecný (což ovšem pro použití kombinátoru nevadí).

Jiné řešení můžeme dostat tak, že η-expanzi provedeme na celou definici funkce:

  def y1[A](f: (A => A) => (A => A)): (A => A) =
    (u : A) => f(y(f))(u);
  // to samé zapsáno jiným způsobem:
  def y2[A](f: (A => A) => (A => A))(u: A): A =
    f(y(f))(u);

Efekt je stejný - výraz y(f) nelze vyhodnotit, dokud jej f neaplikuje na nějakou hodnotu typu A.

Rekurzi lze kompletně implementovat pouze zavedením jednoho vhodného datového typu.

-- Zadefinujeme "zákeřný" datový typ:
data Bad a = C (Bad a -> a)
 
-- Sestrojíme funkci, která aplikuje "x" na "x":
xx :: Bad a -> a
xx (x@(C x')) = x' x
 
-- Pomocí ní sestrojíme Y kombinátor:
yc :: (a -> a) -> a
yc f =  let fxx = f . xx
        in fxx (C fxx)
 
-- Poznámka: Pomocí Y kombinátoru lze každý typ obydlet
-- nekonečnou rekurzí:
loop :: a
loop = yc id
 
-- Příklad použití rekurze:
gcd' :: Int -> Int -> Int
gcd' = yc gcd0 where
    gcd0  :: (Int -> Int -> Int) -> (Int -> Int -> Int)
    gcd0 rec a b  | c == 0     = b
                  | otherwise  = rec b c
      where c = a `mod` b