haskell二叉树签名热代数计算大小

Question

我需要在 haskell 中编写一个函数来计算二叉树的大小。我尝试过，但不明白错误消息告诉我什么或出了什么问题。

我的尝试:

sizeBintree :: Bintree a -> Int 
sizeBintree  = foldBin $ BinSig {empty_ = 0, 
                              fork = \a left right -> a+sizeBintree left+sizeBintree right}

相关定义:

data Bintree a = Empty | Fork a (Bintree a) (Bintree a)

data BinSig a val = BinSig {empty_ :: val,
                            fork :: a -> val -> val -> val}
foldBin:: BinSig a val -> Bintree a -> val
foldBin alg Empty = empty_ alg
foldBin alg (Fork a left right) = fork alg a (foldBin alg left)
                                             (foldBin alg right)

错误信息:

Couldn't match expected type 'Bintree a0' with actual type 'Int' 
In the expression: a+sizeBintree left+sizeBintree right 
In the 'fork'    field of a record 
In the second argument of '($)', namely 'BinSig {empty_ = 0,fork = \a left right -> a+sizeBintree left+sizeBintree right}' 
relevant bindings include 
right::Bintree a0 
left:: Bintree a0

Answer 1

您希望您的fork是这样的:

fork = \a left right -> 1 + left + right

您的版本存在两个问题。首先，您计算大小，而不是将树的元素相加。所以你不想添加那个a，它甚至可能根本不是你可以添加的东西。

 fork = \a left right -> a+sizeBintree left+sizeBintree right
                         ^

其次看fork的类型，

 fork :: a -> val -> val -> val

它采用树的一个元素，然后是两个值(不是树!)并返回另一个值。这两个值将是左右子树折叠的结果。

 fork = \a left right -> a+sizeBintree left+sizeBintree right
                           ^^^^^^^^^^^^^^^    ^^^^^^^^^^^^^

注意 fork 不应该执行任何递归。递归方案由foldBin定义。