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

Question

问题 7 来自 99 个 Haskell 问题

展平嵌套列表结构

这是我的解决方案:

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，不是as，因此您应该在整个列表上使用 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