1)
L'équivalent de la liste [1, 8, 9, 3] dans notre type est Cons 1 (Cons 8 (Cons 9 (Cons 3 Nil))).
2)
Le type de Nil est List a, le type de Cons est a -> List a -> List a, le type de head_ est List a -> a et le type de tail_ est List a -> List a.
3)
toList :: [a] -> List a
toList [] = Nil
toList (x:xs) = Cons x (toList xs)
fromList :: List a -> [a]
fromList Nil = []
fromList (Cons x xs) = x : fromList xs
La fonction toList prend une liste [a] du prélude et la convertit en une List a. Si la liste est vide, elle renvoie Nil. Sinon, elle crée une nouvelle cellule Cons avec la tête de la liste x et la queue xs, qui est le reste de la liste converti en List a.
La fonction fromList fait l'inverse : elle prend une List a et la convertit en une liste du prélude [a]. Si la List a est Nil, elle renvoie une liste vide. Sinon, elle ajoute la tête de la liste x à la liste résultante et continue à convertir la queue xs.
4)
reverse_ :: List a -> List a
reverse_ Nil = Nil
reverse_ (Cons x xs) = append_ (reverse_ xs) (Cons x Nil)
length_ :: List a -> Int
length_ Nil = 0
length_ (Cons _ xs) = 1 + length_ xs
null_ :: List a -> Bool
null_ Nil = True
null_ _ = False
take_ :: Int -> List a -> List a
take_ _ Nil = Nil
take_ n _ | n <= 0 = Nil
take_ n (Cons x xs) = Cons x (take_ (n-1) xs)
drop_ :: Int -> List a -> List a
drop_ _ Nil = Nil
drop_ n xs | n <= 0 = xs
drop_ n (Cons _ xs) = drop_ (n-1) xs
last_ :: List a -> Maybe a
last_ Nil = Nothing
last_ (Cons x Nil) = Just x
last_ (Cons _ xs) = last_ xs
elem_ :: Eq a => a -> List a -> Bool
elem_ _ Nil = False
elem_ y (Cons x xs) = (x == y) || elem_ y xs
(!!_) :: List a -> Int -> Maybe a
Nil !!_ _ = Nothing
(Cons x _) !!_ 0 = Just x
(Cons _ xs) !!_ n = xs !!_ (n-1)
(++_) :: List a -> List a -> List a
Nil ++_ ys = ys
(Cons x xs) ++_ ys = Cons x (xs ++_ ys)
or_ :: List Bool -> Bool
or_ Nil = False
or_ (Cons x xs) = x || or_ xs
and_ :: List Bool -> Bool
and_ Nil = True
and_ (Cons x xs) = x && and_ xs
zip_ :: List a -> List b -> List (a,b)
zip_ Nil _ = Nil
zip_ _ Nil = Nil
zip_ (Cons x xs) (Cons y ys) = Cons (x,y) (zip_ xs ys)
zipWith_ :: (a -> b -> c) -> List a -> List b -> List c
zipWith_ _ Nil _ = Nil
zipWith_ _ _ Nil = Nil
zipWith_ f (Cons x xs) (Cons y ys) = Cons (f x y) (zipWith_ f xs ys)
unzip_ :: List (a,b) -> (List a, List b)
unzip_ Nil = (Nil, Nil)
unzip_ (Cons (x,y) xys) = (Cons x xs, Cons y ys)
where (xs, ys) = unzip_ xys
map_ :: (a -> b) -> List a -> List b
map_ _ Nil = Nil
map_ f (Cons x xs) = Cons (f x) (map_ f xs)
filter_ :: (a -> Bool) -> List a -> List a
filter_ _ Nil = Nil
filter_ p (Cons x xs) = if p x then Cons x (filter_ p xs) else filter_ p xs
Explication :
reverse_ : Cette fonction utilise la récursion pour renverser la liste, en concaténant récursivement la queue inversée avec la tête. La base de la récursion est la liste vide, qui renvoie également la liste vide.
length_ : Cette fonction utilise la récursion pour parcourir la liste et incrémenter un compteur à chaque élément. La base de la récursion est la liste vide, qui renvoie 0.
null_ : Cette fonction renvoie True si la liste est vide et False sinon. Cela peut être vérifié en regardant simplement si la liste est égale à Nil.
take_ : Cette fonction utilise la récursion pour prendre les n premiers éléments de la liste. La base de la récursion est lorsque n est 0 ou lorsque la liste est vide, dans les deux cas, la fonction renvoie la liste vide. Sinon, la tête de la liste est ajoutée au début de la liste résultante et la fonction est appelée récursivement avec n-1 et la queue de la liste.
drop_ : Cette fonction utilise la récursion pour supprimer les n premiers éléments de la liste. La base de la récursion est lorsque n est 0 ou lorsque la liste est vide, dans les deux cas, la fonction renvoie la liste. Sinon, la fonction est appelée récursivement avec n-1 et la queue de la liste.
last_ : Cette fonction utilise la récursion pour parcourir la liste jusqu'au dernier élément. La base de la récursion est lorsque la queue de la liste est vide, dans ce cas, la tête de la liste est renvoyée. Sinon, la fonction est appelée récursivement avec la queue de la liste.
elem_ : Cette fonction utilise la récursion pour rechercher un élément dans la liste. La base de la récursion est lorsque la liste est vide, dans ce cas, la fonction renvoie False. Sinon, si la tête de la liste est égale à l'élément recherché, la fonction renvoie True. Sinon, la fonction est appelée récursivement avec la queue de la liste.
(!!_) : Cette fonction utilise la récursion pour accéder à l'élément à l'index donné. La base de la récursion est lorsque l'index est 0 ou lorsque la liste est vide, dans les deux cas, la fonction renvoie une erreur. Sinon, si l'index est 1, la fonction renvoie la tête de la liste. Sinon, la fonction est appelée récursivement avec l'index-1 et la queue de la liste.
(++_) : Cette fonction utilise la récursion pour concaténer deux listes. La base de la récursion est lorsque la première liste est vide, dans ce cas, la fonction renvoie la deuxième liste. Sinon, la fonction est appelée récursivement avec la queue de la première liste et la deuxième liste, et la tête de la première liste est ajoutée à la liste résultante.
or_ : Cette fonction utilise la récursion pour vérifier si au moins un élément de la liste est True. La base de la récursion est lorsque la liste est vide, dans ce cas, la fonction renvoie False. Sinon, si la tête de la liste est True, la fonction renvoie True. Sinon, la fonction est appelée récursiverment ah...
or_ : cette fonction prend une liste de valeurs booléennes en entrée et renvoie True si au moins une de ces valeurs est True, False sinon. Elle utilise une fonction auxiliaire récursive pour parcourir la liste et retourner True si elle trouve une valeur True. Si la liste est vide, la fonction renvoie False.
and_ : cette fonction prend une liste de valeurs booléennes en entrée et renvoie True si toutes les valeurs sont True, False sinon. Elle utilise une fonction auxiliaire récursive pour parcourir la liste et retourner False si elle trouve une valeur False. Si la liste est vide, la fonction renvoie True.
zip_ : cette fonction prend deux listes en entrée et renvoie une liste de paires formées par les éléments correspondants des deux listes. Elle utilise une fonction auxiliaire récursive qui appelle la fonction zip_ récursivement jusqu'à ce que l'une des listes soit vide.
zipWith_ : cette fonction prend une fonction binaire et deux listes en entrée, applique la fonction aux éléments correspondants des deux listes et renvoie une liste de résultats. Elle utilise une fonction auxiliaire récursive qui appelle la fonction zipWith_ récursivement jusqu'à ce que l'une des listes soit vide.
unzip_ : cette fonction prend une liste de paires en entrée et renvoie un couple de listes, contenant respectivement les premiers éléments et les seconds éléments de chaque paire. Elle utilise une fonction auxiliaire récursive pour parcourir la liste de paires et ajouter chaque élément aux listes correspondantes.
map_ : cette fonction prend une fonction et une liste en entrée, applique la fonction à chaque élément de la liste et renvoie une nouvelle liste de résultats. Elle utilise une fonction auxiliaire récursive pour parcourir la liste et appliquer la fonction à chaque élément.
filter_ : cette fonction prend une fonction prédicat et une liste en entrée, renvoie une liste contenant uniquement les éléments de la liste d'origine qui vérifient le prédicat. Elle utilise une fonction auxiliaire récursive pour parcourir la liste et ajouter chaque élément qui vérifie le prédicat à la nouvelle liste.
5)
Le type de la fonction aList est List (List Double), car elle crée une liste de deux éléments, le premier étant une liste Cons 8 (Cons 2 Nil) et le deuxième étant une liste créée à partir de la liste [4, 5.3, 2] en utilisant la fonction toList que nous avons définie précédemment.
Le type de la fonction applyMap est List (List Double) -> List (List Double). Elle prend une liste de listes de nombres en entrée et retourne une liste de listes de nombres, où chaque élément de chaque liste a été divisé par 2.
6)
Une fonction applyMap_ équivalente à applyMap sans utiliser une liste en compréhension serait :
applyMap_ :: List (List Double) -> List (List Double)
applyMap_ Nil = Nil
applyMap_ (Cons xs xss) = Cons (map_ (/2) xs) (applyMap_ xss)
Ici, nous utilisons la récursion pour parcourir la liste d'entrée xss et appliquer la fonction map_ à chaque élément xs de la liste. Nous retournons ensuite une nouvelle liste en consommant la nouvelle liste créée et en récursant avec le reste de la liste d'entrée xss.
