Binary Tree Fold Fonctions

Question

I ont la définition d'un arbre binaire dans Haskell comme suit:

data BTree x = Nil | BNode x (BTree x) (BTree x) 

J'ai alors une définition fois pour ce type de données:

foldB :: (x -> u -> u -> u) -> u -> BTree x -> u 
foldB f a Nil = a 
foldB f a (BNode x l r) = f x (foldB f a l)(foldB f a r) 

J'espère que Je pourrais simplement faire de cette fonction à la somme de toutes les valeurs:

sumBFold :: (Num a) => BTree a -> a 
sumBFold x = foldB (+) 0 x 

Mais cela ne fonctionne pas, et je ne peux pas pour la vie de moi comprendre pourquoi. La partie utile du message d'erreur que je reçois est:

Couldn't match type `a` with `a -> a' 
`a' is a rigid type variable bound by the type signature for: 
sumBFold :: forall a. Num a => BTree a -> a 
Expected type: (a -> a) -> a -> a -> a 
Actual type: (a -> a) -> (a -> a) -> a -> a 
In the first argument of folB namely `(+)` 

Answer 1

L'erreur vient au sujet d'essayer d'utiliser

(+) :: (Num a) => a -> a -> a 

comme paramètre de type

(x -> u -> u -> u) 

Si vous commencer à essayer de l'adapter, en se souvenant que (x -> u -> u -> u) est la même que (x -> (u -> (u -> u))),

x == a 
u == a 
u -> u == a -> a == a 

ce qui est impossible, et d'où provient l'erreur.

Envisagez l'une des solutions suivantes.

sumBFold :: (Num a) => BTree a -> a 
sumBFold = foldB add3 where add3 x y z = x + y + z 
sumBFold = foldB $ \x y z -> x + y + z 
sumBFold = foldB ((.) (+) . (+))