list - 在 Haskell 中展平列表

Question

我试图在 Haskell 的列表中展平任意数量的列表。我知道这个问题之前已经在 Stack 上发布过，但是那里的答案对我来说太复杂了(我是 Haskell 的新手)，或者不是满足我需求的答案(例如 concat 对我不起作用，因为我必须自己实际编写这个 flatten 函数作为考试学习指南)。我还在 Haskell 中编写自己的 flatten 函数，以了解为什么顶级解决方案使用模块。

这是我目前所拥有的。

flatten :: [[a]] -> [a]
flatten [] = []
flatten (x:xs) = flatten x:flatten xs

但是，我得到一个错误:

Inferred type is not general enough
*** Expression    : flatten
*** Expected type : [[a]] -> [a]
*** Inferred type : [[[a]]] -> [[a]]

编辑:抱歉!我误解了我的考试学习问题。列表的所有元素实际上都必须是列表。例如，[[[1,2,3], [4,5,6]], [7,8,9]] 而不是 [1, [2,3,4]] 。

Answer 1

第 1 步:定义您的数据。您需要一种支持任意嵌套的数据类型。 [a] 没有，所以您将无法通过这种方式解决问题。

那么数据会是什么样子呢？一些 Lisp 符号怎么样:

a
()
(a b c)
((a b) c d)
(a (b c) d (e (f)))

看起来一个元素可以是一个原子，也可以是一个列表。那么让我们说一下 Haskell 中的前一句话:

data Element t = -- "an element is either ..."
    = Atom t     -- "an atom ..."
    | List [Element t]  -- "or a list of elements"
  deriving (Show)       -- "and please print things for me too, okay?"

第 2 步:遍历数据。现在您需要编写一个函数，将 Element t 展平到列表中。类型签名会是什么样子？

我建议 flatten::Element t -> [t]。要实现它，需要两种情况——一种用于 Atom，另一种用于 List:

flatten :: Element t -> [t]
flatten (Atom x) = ....
flatten (List xs) = .....

请记住，每个方程的计算结果都必须是 [t]。祝你好运!