Faire un dans l'ordre traversal sur un arbre binaire en Haskell utilisant un pli

Question

Je suis en train de mettre en œuvre un ordre en fonction traversal en utilisant une version modifiée de fois en Haskell:

foldT :: (u -> u -> u) -> (a -> u) -> Tree a -> u 
foldT f g (Tip a) = g a 
foldT f g (Node l r) = f (foldT f g l) (foldT f g r) 

Mais je suis se coincer avec la façon de mettre en œuvre la fonction, ma tentative est:

inorderT :: Ord a => Tree a -> [a] 
inorderT = foldT (\x l r -> l ++ x ++ r) [] 

Toute aide est grandement appréciée!

Messages d'erreur:

Couldn't match expected type ‘[a]’ with actual type ‘[a] -> [a]’ 
• In the first argument of ‘foldT’, namely 
    ‘(\ x l r -> l ++ x ++ r)’ 
    In the expression: foldT (\ x l r -> l ++ x ++ r) [] 
    In an equation for ‘inorderT’: 
     inorderT = foldT (\ x l r -> l ++ x ++ r) [] 
• Relevant bindings include 
    inorderT :: Tree a -> [a] 

Answer 1

Je reconstruis le type de données d'arbre de la définition foldT. Vérifiez qu'il n'est pas dans le formulaire Node a (Tree a) (Tree a) couramment utilisé, de sorte que votre (\x l r -> l ++ x ++ r) est erroné.

Vérifiez votre code, et voir plus loin si c'est ce dont vous avez besoin:

data Tree a = Tip a | Node (Tree a) (Tree a) 

foldT :: (u -> u -> u) -> (a -> u) -> Tree a -> u 
foldT f g (Tip a) = g a 
foldT f g (Node l r) = f (foldT f g l) (foldT f g r) 

inorderT :: Tree a -> [a] 
inorderT = foldT (\l r -> l ++ r) (\x -> [x])