使用 concatMap 展平嵌套列表结构会出错

Question

问题 7来自 99Haskell 问题

展平嵌套列表结构

这是我的解决方案：

data NestedList a = Elem a | List [NestedList a]

myFlatten :: NestedList a -> [a]
myFlatten (Elem x) = [x]
myFlatten (List (x:xs)) = x : concatMap myFlatten xs

但是，我想明白...为什么编译器会说：

Occurs check: cannot construct the infinite type: a ~ NestedList a

Expected type: [NestedList a] Actual type: [a]

Answer 1

对于List (x:xs)，x和xs都是NestedList a，而不是a，因此您应该使用concatMap整个列表，其中：

myFlatten :: NestedList a -> [a]
myFlatten (Elem x) = [x]
myFlatten (List <strong>xs</strong>) = concatMap myFlatten <strong>xs</strong>

为了避免在单例列表中包装和展开，您可以使用递归传递给列表的尾部，其中：

myFlatten :: NestedList a -> [a]
myFlatten = (`go` [])
    where go (Elem x) = (x :)
          go (List xs) = flip (foldr go) xs

Answer 2

让我们检查这部分代码，仅：

myFlatten :: NestedList a -> [a]
myFlatten (List (x:xs)) = x : ...

在 List 中我们有 x:xs，根据 List 的定义我们找到 (x:xs) :: [NestedList a]。因此：

x :: NestedList a
xs :: [NestedList a]

returned 值为x : ...，即x类型的列表，即NestedList a。因此，return 类型是 [NestedList a].

但是myFlatten的签名说return类型是[a]。这仅在 [a] = [NestedList a] 时才有可能，即仅在 a = NestedList a 时才有可能，但这是不可能的，因此会出现类型错误。

使用 concatMap 展平嵌套列表结构会出错

Flatten a nested list structure using concatMap gives error

haskell