Functional Programming 2023/24 fall

Kõrgemat järku funktsioon

... on funktsioon, mis võtab argumendiks või tagastab funktsiooni.

Kõrgemat järku funktsioon: map

  map : (a -> b) -> List a -> List b
  map f []     = []
  map f (x::xs) = f x :: map f xs

Funktsiooni map illustreerib järgmine võrdus:
{$\texttt{map}\;f\;[x_1, x_2, \ldots, x_n] = [f\;x_1, f\;x_2, \ldots, f\;x_n]$}

Näide:

  inverses : List Double -> List Double
  inverses xs = map inverse xs
      where inverse : Double -> Double
            inverse x = 1 / x 

  Main> inverses [1,2,4,8]
  [1.0, 0.5, 0.25, 0.125]

Kõrgemat järku funktsioon: foldr

  foldr : (a -> b -> b) -> b -> List a -> b
  foldr f b []     = b
  foldr f b (x::xs) = f x (foldr f b xs)

Funktsiooni foldr illustreerib järgmine võrdus:
{$\texttt{foldr}\;(+)\;b\;[x_1, x_2, \ldots, x_n] = x_1 + (x_2 + (\ldots + (x_n + b)))$}

Funktsiooni map saab defineerida läbi foldr-i

  map : (a -> b) -> List a -> List b
  map f xs = foldr g [] xs
      where g : a -> List b -> List b
            g x y = (f x) :: y

{$\texttt{foldr}\;g\;[]\;[x_1, x_2, \ldots, x_n] = x_1 `g` (x_2 `g` (\ldots `g` (x_n `g` []))) = f\;x_1 :: f\; x_2 :: \ldots :: f\; x_n :: [] $}

Kõrgemat järku funktsioon: foldl

  foldl : (b -> a -> b) -> b -> List a -> b
  foldl f b []     = b
  foldl f b (x::xs) = foldl f (f b x) xs

Funktsiooni foldl illustreerib järgmine võrdus:
{$\texttt{foldl}\;(+)\;b\;[x_1, x_2, \ldots, x_n] = (((b + x_1) + x_2) + \ldots) + x_n$}

Funktsiooni reverse saab defineerida läbi foldl-i

  reverse : List a -> List a
  reverse xs = foldl g [] xs
     where g : List a -> a -> List a
          g x y = y :: x

ehk
{$\texttt{foldl}\;g\;[]\;[x_1, x_2, \ldots, x_n] = ((([] \;`g`\; x_1) \;`g`\; x_2) \;`g`\; \ldots) \;`g`\; x_n = x_n :: \ldots :: x_2 :: x_1 :: []$}

Curry stiil ja funktsioonide osaline rakendamine

Selle asemel, et kirjutada

  uusFunktsioon x y z = olemasolevFunktsioon (x+1) y z

oleks Idrises parem stiil kirjuldada

  uusFunktsioon x = olemasolevFunktsioon (x+1)

NB! Funktsioon olemasolevFunktsioon on osaliselt rakendatud.
Mõlemad funktsioonid võtavad (vähemalt!) kolm argumenti.

Realistlikum näide:

  f xs = sum (takeWhile (/=0) xs)

asemel

  f = sum . takeWhile (/=0)

Soovitus: Kirjuta funktsioone nii, et neid oleks võimalik ka osaliselt rakendada.

Funktsiooni (a,b) -> c karritud kuju on a -> b -> c. See võimaldab osalist rakendamist