projprog/HSK21.md

Haskell 21

Exercice 1

1. Une récursion terminales est une récursion telle que l'appel récursif est le dernier appel de la fonction.
2. La première fonction va calculer 10*(factorielle (10-1)) puis 10*9*(factorielle (10-2)) jusqu'à obtenir le gros produit de n termes 10*9*8*7*6*5*4*3*2*1. La seconde va appeler go 10 1 puis go (10-1) 10 puis go (10-2) 90 ..., et à la fin, le résultat sera déjà calculé. C'est bien sûr la seconde qui est récursive terminale.

Exercice 2

minimum' :: [Float] -> Float
minimum' [e] = e
minimum' (e:s) = min e (minimum' s)

minimum'' :: [Float] -> Float
minimum'' (u:l) = go l u
    where go [] x = x
          go (e:s) x
              | e>x = go s x
              | otherwise = go s e

and' :: [Bool] -> Bool
and' [] = True
and' (e:s) = e && (and' s)

and'' :: [Bool] -> Bool
and'' l = go l True
    where go [] x = x
          go (e:s) x = go s (e && x)

reduce :: (t->t->t) -> [t] -> t
reduce f [e] = e
reduce f (e:s) = f e (reduce f s)

reduce' :: (t->t->t) -> [t] -> t
reduce' f (e:s) = go s e
    where go [] x = x
          go (h:t) x = go t (f h x)

Attentiton, si on met des fonctions non symmétriques dans reduce et reduce', elle ne fonctionneront pas pareil !

Exercice 3

1. Si on passe la liste vide en paramètre de reduce, Haskell se plaint que la définition n'est pas complète.
2. Une fonction est dite totale losque sa définition existe et est calculable pour tout objet du type spécifié par la fonction. Exemples de foncitons totales: (+), length. Exemple de fonctions non totales: reduce, head.

reduceTotal :: (t->t->t) -> t -> [t] -> t
reduceTotal f x0 [] = x0
reduceTotal f x0 (e:s) = f e (reduceTotal f x0 s)

reduceTotal' :: (t->t->t) -> t -> [t] -> t
reduceTotal' f x0 l = go l x0
    where go [] x = x
          go (h:t) x = go t (f h x)

Exercice 4

1. Dans le Prélude, et même dans le module Data.List, on trouve les fonctions suivantes:

• foldl1 qui fonctionne comme reduce
• foldr1 qui fonctionne comme reduce'
• foldl ou foldl' qui fonctionne comme reduceTotal
• foldr qui fonctionne comme reduceTotal'

2. Dans les trois cas, foldr profite de l'évaluation terminale, qui accélere le processus. L'évaluation paresseuse ne fonctionne pour aucun des deux. Pour foldr, l'évaluation ira de toute façon au bout, et pour foldl, Haskell crée l'expression de l'évaluer.
3. POur éviter ce problème, il est possible d'utiliser foldl' qui évalue l'expression à chaque boucle de récursion. Par exemple, dans notre premier exemple de factoriel, Haskell ferait le processus suivant: 10*(factorielle (10-1)) puis 10*9*(factorielle (10-2)) puis simplification en 90*(factorielle (10-2)) puis 8*90*(factorielle (10-3)) puis 720*(factorielle (10-3)) et cætera. Alors le calcul ne prendra pas trop de place en mémoire.