Pourquoi ce code n'est-il pas à espace constant ?

Question

J'apprends actuellement Haskell (je suis programmeur de métier, mais c'est ma première tentative dans un langage fonctionnel).

Je veux écrire une fonction qui parcourt une liste et renvoie l'élément minimum et maximum de cette liste. C'est un peu ce que font les fonctions Prelude minimum et maximum faire, mais les deux en même temps. J'ai trouvé le code suivant :

import Data.List

-- Declaration of rand

minMax :: [Int] -> Maybe (Int, Int)
minMax []   = Nothing
minMax (x:xs) = Just (foldl' f (x, x) xs)
                where
                  f (a, b) c = (if c < a then c else a, if c > b then c else b)

rand est une fonction qui génère une liste infinie de nombres. Le problème est que lorsque j'ajoute ce qui suit main fonction :

main = print $ minMax $ take 1000000 $ rand 7666532

compiler et exécuter tout cela avec profilage, il me montre que cela utilise plus de 200 Mo de mémoire, donc ce n'est certainement pas une fonction à espace constant (ce que j'aimerais qu'elle soit).

La question est de savoir pourquoi et ce que je dois changer pour y remédier. D'après ce que je comprends foldl' plie la liste de gauche à droite (de la même façon qu'elle est générée) et n'est pas paresseux, donc je ne vois pas pourquoi l'utilisation de la mémoire est si élevée. Je suis presque sûr que c'est le minMax qui est incorrecte, car le simple fait d'imprimer ladite liste, en utilisant la fonction

main = print $ take 1000000 $ rand 7666532

me donne 1MB d'utilisation, ce que je comprends et attends.

Answer 1

Notez que foldl' force l'accumulateur à faible forme normale de tête. Puisque l'accumulateur est un tuple, il n'a pas besoin de pas force l'évaluation des deux éléments du tuple.

Si vous forcez explicitement les deux éléments, vous obtenez une fonction à espace constant :

f (a, b) c = a `seq` b `seq` (if c < a then c else a, if c > b then c else b)

Dans votre programme original, vous construisez un tuple du type : (<thunk>, <thunk>) et à chaque fois f est appliquée, vous construisez simplement un tuple avec des thunks de plus en plus grands. . Lorsque finalement ce dernier est consommé par print l'appel à show force l'évaluation complète du tuple et toutes les comparaisons sont faites à ce moment-là.

Utilisation de seq vous forcez plutôt f pour évaluer la comparaison à ce moment-là, et donc les thunks contenus dans l'accumulateur sont évalués avant d'effectuer la comparaison. Le résultat est donc que les thunks stockés dans l'accumulateur ont une taille constante.

Quoi foldl' ne fait qu'éviter de construire le thunk : f (f (f ...) y) x .

Une autre solution, suggérée par Jubobs, consiste à éviter d'utiliser explicitement l'option seq est d'utiliser un type de données qui a des champs stricts :

data Pair a b = Pair !a !b
    deriving Show

Et ainsi le code deviendrait :

minMax :: [Int] -> Maybe (Pair Int Int)
minMax []   = Nothing
minMax (x:xs) = Just (foldl' f (Pair x x) xs)
                where
                  f (Pair a b) c = Pair (if c < a then c else a) (if c > b then c else b)

Cela permet d'éviter complètement les thunks.

Answer 2

Le site seq qui est utilisée dans foldl' force essentiellement son premier argument à être évalué jusqu'au WHNF (Weak Head Normal Form).

Comme expliqué ici l'évaluation du WHNF s'arrête une fois que vous avez appliqué chaque application d'un Constructeur . (a, b) est donc toujours en WHNF, même si a et b sont des thunks puisque vous utilisez le constructeur de Tuple. (,) avant d'arriver à a et b .

Par conséquent, cet espace présente des fuites malgré l'utilisation de foldl' :

foldl' (\ (a, b) x -> (a + x, b + x)) (0, 1) [1..1000000]

mais ce n'est pas le cas :

foldl' (\ (a, b) x -> a `seq` b `seq` (a + x, b + x)) (0, 1) [1..10000000]

Il est aussi parfois pratique d'utiliser l'option -XBangPatterns extension pour écrire ceci :

foldl' (\ (!a, !b) x -> (a + x, b + x)) (0, 1) [1..10000000]