1

I want to write a treeFold function that takes: A function f of type 'a -> b -> a, A value x of type a, A Tree b named t, and returns a value of type a. The return value is computed by performing an in-order traversal of the Tree, passing along the partial results via x. HERE IS MY CODE:

import Control.Exception
import Control.Monad
import Control.DeepSeq
import qualified Data.List as List
import Test.HUnit

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



insertTree :: ( Ord a, Show a ) => Tree a -> a -> Tree a
insertTree Empty x  =  Node x Empty Empty
insertTree ( Node v tLeft tRight ) x
    | x == v = Node v tLeft tRight
    | x < v = Node v (insertTree tLeft x) tRight
    | x > v = Node v tLeft (insertTree tRight x)


createTree :: ( Ord a, Show a ) => [ a ] -> Tree a
createTree = foldl insertTree Empty

intTree = createTree [ 9, 7, 2, 8, 6, 0, 5, 3, 1 ]

listTree = createTree ( List.permutations [ 0 .. 3 ] )

strTree = createTree [ "hello"
                     , "world"
                     , "lorem"
                     , "ipsum"
                     , "dolor"
                     , "sit"
                     , "amet"
                     ]
treeFold :: (a -> b -> b -> b) -> b -> Tree a -> b
treeFold f z Empty = z
treeFold f z (Node v l r) = f v (subfold l) (subfold r)
    where subfold = foldTree f z

But when I run the code, I got a "Couldn't match type error". I was wondering how can I fix this problem? for exmaple: Main> treeFold (+) 10 intTree, instead of getting Main> 51, i got could't match type error. Any help is greatly appreciated.

4

1 回答 1

1

在你的功能

treeFold :: (a -> b -> b -> b) -> b -> Tree a -> b
treeFold f z Empty = z
treeFold f z (Node v l r) = f v (subfold l) (subfold r)
    where subfold = foldTree f z

您f在三个值上使用v：(subfold l)和(subfold r)。这就是您的类型签名需要f采用三个参数的原因。

在我看来，您最好f两次应用两个参数，一次将 and 结合起来v，(subfold l)另一个将其与 结合起来(subfold r)：

treeFold f z Empty = z
treeFold f z (Node v l r) = f (f v (subfold l)) (subfold r)
    where subfold = treeFold f z

这确实意味着如果我们假设f :: a -> b -> c，那么subfold l :: b因为f v (subfold l)，而且subfold l :: c因为它是从treeFold. 因此c和b是相同的类型 ( c ~ b) 和f v (subfold l) :: b。这也被用作 first 的第一个f参数a ~ b。因此对于这个新的 use-f-twice 版本，

treeFold :: (b -> b -> b) -> b -> Tree b -> b
于 2013-05-07T02:47:14.370 回答