Haskell 99问题#7:Prepend vs Append to List

Question

这通过:

data Nested List a = Elem a | List [NestedList a]
flatten :: NestedList a -> [a]
flatten (Elem a) = [a]
flatten (List (x:xs)) = flatten x ++ flatten (List xs)
flatten (List []) = []

这失败了:

data NestedList a = Elem a | List [NestedList a]
flatten :: NestedList a -> [a]
flatten (Elem a) = [a]
flatten (List (x:xs)) = flatten x : flatten (List xs)
flatten (List []) = []

错误是:

Couldn't match expected type `a' with actual type `[a]'
  `a' is a rigid type variable bound by
      the type signature for flatten :: NestedList a -> [a]
      at 007.hs:2:12
Relevant bindings include
  xs :: [NestedList a] (bound at 007.hs:4:18)
  x :: NestedList a (bound at 007.hs:4:16)
  flatten :: NestedList a -> [a] (bound at 007.hs:3:1)
In the first argument of `(:)', namely `flatten x'
In the expression: flatten x : flatten (List xs)

所不同的是++代替:.我知道前者附加,后者预先,但为什么:在这种情况下不起作用？我不明白这个错误.

Answer 1

实际上++是连接运算符,它希望运算符在这种特殊情况下都是一个列表.因为flatten返回一个列表,++所以快乐地连接它们.

但是,:只需将一个项目添加到列表中.由于flatten x在flatten x : flatten (List xs)返回列表时,:抛出此错误.