哈希克尔的树大小

Question

我有一个这样的树的实现：

数据树a =空|节点a [Tree a]导出显示

我需要获取大小。

我觉得这个代码可以解决这个问题，但我有一个错误：

size :: Tree a -> Int 
size Empty  = 0 
size (Node a ts) = 1 + [size t | t<-ts] 

Answer 1

提示：

> 1 + [2,3,4] 
<interactive>:8:1: error: 
    • Non type-variable argument in the constraint: Num [t] 
     (Use FlexibleContexts to permit this) 
    • When checking the inferred type 
     it :: forall t. (Num [t], Num t) => [t] 

> 1 + sum [2,3,4] 
10 

Answer 2

你明明在你的代码输入错误。

Couldn't match expected type ‘Int’ with actual type ‘[Int]’ 
• In the expression: 1 + [size t | t <- ts] 
    In an equation for ‘size’: 
     size (Node a ts) = 1 + [size t | t <- ts] 

既然你想要一个Int，你必须找到一种方法，你的Int列表转换为Int。

换句话说，你可以引入这样的孔：

size :: Tree a -> Int 
size Empty   = 0 
size (Node a ts) = 1 + _g [size t | t<-ts] 

导致错误消息：

• Found hole: _g :: [Int] -> Int 
    Or perhaps ‘_g’ is mis-spelled, or not in scope 
• In the expression: _g 
    In the second argument of ‘(+)’, namely ‘_g [size t | t <- ts]’ 
    In the expression: 1 + _g [size t | t <- ts] 
• Relevant bindings include 
    ts :: [Tree a] 
     (bound at /Users/jeeb/incubator/scratch/app/Main.hs:10:14) 
    a :: a (bound at /Users/jeeb/incubator/scratch/app/Main.hs:10:12) 
    size :: Tree a -> Int 
     (bound at /Users/jeeb/incubator/scratch/app/Main.hs:9:1) 

根据你所说的“大小”什么，你应该能够用正确的功能替换g。

Answer 3

size:: Tree a -> Int 
size Empty = 0 
size (Node a ts) = 1 + maximum[size t | t <- ts] 

可能你想要的最大尺寸的子树，所以我会使用函数预定义的最大值来获得它后，将每个分支转换成他的大小。