Can Strictness Guide récursion?

Question

Disons que nous avons un algorithme simple arbre dans la création de Haskell:

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq) 

makeTree :: Tree Int -> Tree Int 
makeTree (Node 0 l r) = Node 0 EmptyTree EmptyTree 
makeTree (Node n l r) = Node n (makeTree $ newTree (n - 1)) 
           (makeTree $ newTree (n - 1)) 
    where 
    newTree n = Node n EmptyTree EmptyTree 

Pour un très grand nombre, nous nous attendons à cet algorithme pour échouer avec une erreur « dépassement de la taille de la pile ». Ce serait parce que l'algorithme est récursif binaire, pas récursif de la queue. Puis-je utiliser des patterns bang (sur la sous-arborescence gauche résultante "! (MakeTree $ newTree (n-1))") pour guider la récursion binaire en récursion de queue, car la récursivité devrait maintenant être dirigée en raison de la rigueur?

EDIT:

Il se trouve que la vraie question est pas la création de l'arbre, mais les fonctions qui consomment de l'arbre. Il y a une autre fonction utilisée pour aplatir l'arbre, où l'instance est la suivante:

import qualified Data.Foldable as F 

instance F.Foldable Tree where 
    foldMap f EmptyTree = mempty 
    foldMap f (Node x l r) = F.foldMap f l `mappend` 
          f x   `mappend` 
          F.foldMap f r 

flatten = F.foldMap (:[]) 

L'aplanissement de l'arbre est donc appelé et il est probablement ici où le débordement se produit. Si oui, la solution est-elle aussi simple qu'hypothétiquement la conversion de foldl en foldl '? Ou est-ce que le pliage binaire va ajouter des problèmes supplémentaires?

Answer 1

Je suppose que vous vouliez créer un arbre très profond, comme

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq) 

makeTree :: Int -> Tree Int 
makeTree 0 = EmptyTree 
makeTree n = Node n (makeTree (n - 1)) (makeTree (n - 1)) 

La clé est que Haskell est paresseux. Ainsi, après avoir appelé la fonction, rien n'est réellement créé, sauf un thunk qui est évalué en cas de besoin. Rien n'est alloué sur la pile, car l'appel à makeTree n'implique pas d'appel récursif. Après l'examen du nœud racine, les appels récursifs sont invoqués, mais toujours un seul niveau. Cela signifie que l'examen de chaque nœud ne coûte que du temps fini et de la mémoire (dans ce cas constant), et non en fonction de la profondeur de l'arbre. La propriété importante est que chaque appel récursif est à l'intérieur d'un constructeur. Ceci est parfois appelé corecursion ou une récursion gardée.

Il est possible qu'un débordement de pile se produise dans une fonction qui consomme l'arbre, mais c'est une question différente.