在Haskell中展平列表

Question

我试图在Haskell中列出列表中的任意数量的列表.我知道这个问题之前已经发布在Stack上了,但那里的答案对我来说太复杂了(我是Haskell的新手),或者没有满足我需求的答案(例如,concat对我不起作用,因为我我必须自己为考试学习指南写这个扁平化的功能.我也在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].要实现它,它需要两个案例 - 一个用于Atoms,一个用于Lists:

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

请记住,每个等式都必须评估为a [t].祝好运!

Answer 2

让我们计算出你的函数类型:如果你有一个列表列表,那就写完了[[a]].你想把它变成一个列表[a],所以flatten的类型应该是[[a]] -> [a].你也可以欺骗和查找类型concat,因为你知道你正在重新实现它.

现在让我们来看看实现.第一种情况匹配[]并返回[].这符合[[a]] -> [a]吗？是的,因为参数[]是一个类型的空列表,[something]其中某些东西可以具有该类型[a].返回值也符合我们的类型,因为它是一个空的类型列表,[whatever]其中任何类型都可以a.

现在让我们看看第二种情况,它是否与类型匹配[[a]] -> [a]？与(x:xs)手段匹配的模式x具有类型[a]和xs类型[[a]],这很好.问题是你的递归调用:第一个调用flatten用x其类型[a].但我们知道flatten的参数必须是类型[[a]].

顺便说一下,如果首先声明函数的类型,通常会得到更清晰或更精确的类型错误消息.这是因为一旦发现与您声明的内容发生矛盾,编译器就可以立即停止.如果您忽略签名,则编译器仅检查定义是否与其自身一致.当我宣布类型GHC告诉我:

    Couldn't match type `a' with `[a0]'
      `a' is a rigid type variable bound by
          the type signature for flatten :: [[a]] -> [a] at x.hs:20:1
    Expected type: [[a0]]
      Actual type: [a]
    In the first argument of `flatten', namely `x'
    In the first argument of `(:)', namely `flatten x'

这正是我们自己手动检查类型的原因.我们传递给的参数flatten应该有类型,[[a]]但实际上我们传递的是一个类型的值[a].