Haskell Hero

Krabičkové znázornění této funkce naleznete v lekci Užitečné funkce. Pro zopakování: Co je to typ funkce? Je to zápis typů hodnot, které do funkce vstupují a typ hodnoty, na kterou se funkce vyhodnotí. To vše odděleno šipkami ->.

Typem složené funkce je tedy to, co do funkce na začátku vstupuje a co z ní na konci vystupuje. Nezajímá nás, jaký je typ hodnoty v mezivýsledku.

Jak je vidět z obrázku, do funkce (odd . snd) vstupuje dvojice, která je tvořená čímkoli a celým číslem. Výstupem funkce je pak pravdivostní hodnota. Typ naší funkce je tedy:

odd . snd :: (a, Integer) -> Bool

Jednoduchý příklad 2

Jaký je typ funkce head . head?

Funkce head si bere seznam a vrací jeho první prvek. Například takto:

head [3,4,5]  ~>  3

Pokud ale na ten samý seznam aplikujeme funkci head . head, výpočet skončí chybou:

   (head . head) [3,4,5]
~> head (head [3,4,5])
~> head 3
~/>

Potřebovali bychom, aby první aplikace funkce head vrátila seznam, aby z něj následně druhá aplikace funkce head vytáhla první prvek. Jak to uděláme? Do funkce head . head vložíme seznam seznamů.

   (head . head) [[3,10,14], [8,4,13,15], []]
~> head (head [[3,10,14], [8,4,13,15], []])
~> head [3,10,14]
~> 3

Jelikož funkci head nezáleží na typu seznamu, který do ní vstupuje, můžeme jí na vstup dát seznam čehokoli. Výsledný typ je potom následující:

head . head :: [[a]] -> a

Převádíme do pointwise

Pointwise je opačný zápis pointfree. V pointfree výrazu je lambda nahrazená operátory (.), v pointwise jsou tečky nahrazeny lambdou.

Pro převod z pointfree do pointwise nám budou stačit tři pravidla:

definice funkce (.) ve směru zleva doprava:
```
(f . g) x = f (g x)
```
Způsob zapsání aplikace binární funkce na argumenty. Jinými slovy, že následující výrazy jsou zaměnitelné:
```
5 + 3
(+) 5 3
(5+) 3
(+3) 5
```
přidání argumentu na pravou stranu výrazu
```
[výraz] = \x -> ([výraz]) x
```

Pomocí těchto tří pravidel jsme schopní převést libovolný výraz v pointfree do pointwise tvaru.

Složitější příklad

Napište nejobecnější typ funkce (.(,)) . (.) . (,).

Možností jak tuto úlohu řešit je mnoho. Zde si ukážeme převod do pointwise tvaru a jeho následné otypování.

Jako první musíme rozhodnout, zda máme výraz ozávorkovat

((.(,)) . (.)) . (,)

nebo

(.(,)) . ((.) . (,))

Podle tabulky priorit a sdružování zjistíme, že (.) sdružuje zprava, to znamená, že správné ozávorkování je následující:

(.(,)) . ((.) . (,))

A nyní již můžeme přistoupit k samotnému převodu do pointwise. Jak jsme při převodu do pointfree argumenty odebírali, zde je budeme přidávat. Aplikujeme tedy naši funkci na argument x.

\x -> ((.(,)) . ((.) . (,))) x

Výraz upravíme podle definice (.) klasickým způsobem zleva doprava: (poznámka: značka ===>, která je zde dále použitá je námi definovaná značka pro zkrácení zápisu, která znamená toto převedeme na toto, není to haskellovský operátor)

\x -> ((.(,)) . ((.) . (,))) x
      (--f--- . -----g-----) x

===>

\x -> (.(,)) (((.) . (,)) x)
      -- f - (---- g ---- x)

Nyní můžeme využít znalosti toho, že (+5) 3 můžeme napsat jako 3 + 5.

\x -> (.(,)) (((.) . (,)) x)
      (+ 5 ) (----- 3 -----)

===>

\x -> (((.) . (,)) x) . (,) 
      (----- 3 -----) +  5

Teď převedeme ((.) . (,)) x podle definice tečky.

\x -> (((.) . (,)) x) . (,) 
       ( f  .  g ) x

===>

\x -> ((.) ((,) x)) . (,)
        f  ( g  x)

Nyní jsme vyčerpali všechny možnosti a funkce stále není v pointwise tvaru. Přidáme tedy do aplikace nový obecný argument, například y.

\x y -> (((.) ((,) x)) . (,)) y

A opět můžeme použít definici tečky.

\x y -> (((.) ((,) x)) . (,)) y
        (----- f ----- .  g ) y

===>

\x y -> ((.) ((,) x)) ((,) y)
        ----- f ----- ( g  x)

V tomto momentě máme výraz ve tvaru ((+) 3) 5, který přepíšeme na 3 + 5

\x y -> ((.) ((,) x)) ((,) y)
        ((+) -- 3 --) -- 5 --

===>

\x y -> ((,) x) . ((,) y)
        -- 3 -- + -- 5 --

Nyní jsme v situaci, kdy již zápis nemůžeme nijak upravit, ale stále to ještě není plně vyhodnotitelný výraz. Proto celý výraz aplikujeme na nový argument, který pojmenujeme například z.

\x y z -> (((,) x) . ((,) y)) z

Dále odstraníme tečku standardním způsobem.

\x y z -> (((,) x) . ((,) y)) z
          (-- f -- . -- g --) x

===>

\x y z -> ((,) x) (((,) y) z)
          -- f -- (-- g -- x)

Všechny tečky jsou odstraněny, nyní už jen převedeme zápis do infixu, aby byl přehlednější. Nejdříve do infixu převedeme podvýraz ((,) y) z.

\x y z -> ((,) x) (((,) y) z)
                   ((+) 3) 5

===>

\x y z -> ((,) x) (y,z)
                   3+5

A následně i celý výraz.

\x y z -> ((,) x) (y,z)
          ((+) 3) - 5 -

===>

\x y z -> (x,(y,z))
           3+ -5-

Co jsme získali?

O funkci v pointfree tvaru (.(,)) . (.) . (,) jsme nedokázali říct vůbec nic. Zato o funkci \x y z -> (x,(y,z)) již můžeme říci mnohé. Například, že je ternární a že ze tří argumentů udělá uspořádanou dvojici, kde její první složka je její první argument a druhá složka je tvořena dvojicí druhého a třetího argumentu.

Jaký je tedy typ funkce (.(,)) . (.) . (,)? Naprosto stejný, jako typ funkce \x y z -> (x,(y,z)). Operátor (,) nemá žádná typová omezení. Můžeme mu dát dvakrát (klidně různé) cokoli a on nám z nich udělá dvojici. Typ naší funkce tedy bude:

(.(,)) . (.) . (,) :: a -> b -> c -> (a,(b,c))

Kdyby bylo cokoli nejasné, pište do diskuze.

<= Eta redukce předchozí lekce následující lekce foldr, foldl =>