2

我试图在 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]]。

4

5 回答 5

11

第 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?"

第二步：遍历数据。 现在您需要编写一个将 an 展平Element t为列表的函数。类型签名会是什么样子？

我建议flatten :: Element t -> [t]。为了实现它，它需要两种情况——一种用于Atoms，另一种用于Lists：

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

请记住，每个方程都必须计算为 a [t]。祝你好运！

于 2013-03-21T23:39:31.723 回答
6

让我们计算出你的函数的类型：如果你有一个列表列表，这就是[[a]]. 你想把它展平为一个列表，[a]所以展平的类型应该是[[a]] -> [a]。您也可以作弊并查找 的类型concat，因为您知道您正在重新实现它。

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

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

顺便说一句，如果您先声明函数的类型，您通常会得到更清晰或更精确的类型错误消息。这是因为编译器一旦发现与您声明的内容相矛盾，就会立即停止。如果省略签名，编译器只会检查定义是否与自身一致。当我声明类型 GHC 告诉我：

    无法将类型“a”与“[a0]”匹配
      `a' 是一个刚性类型变量，由
          flatten :: [[a]] -> [a] at x.hs:20:1 的类型签名
    预期类型：[[a0]]
      实际类型：[a]
    在`flatten'的第一个参数中，即`x'
    在 `(:)' 的第一个参数中，即 `flatten x'

这正是我们发现自己手动检查类型的结果。我们传递给的参数flatten应该有类型[[a]]，但我们实际上传递了一个类型的值[a]。

于 2013-03-21T23:24:59.380 回答
3

好吧，在 Haskell 中，所有嵌套列表对所有元素都有统一的嵌套深度。这是类型系统的结果，它要求列表的所有元素都属于同一类型。

类似以下定义的东西永远无法进行类型检查：

example = [1, [2, 3, 4], [[5, 6], [7]]]

第一个元素是1 :: Integer，第二个元素是 ，[2, 3, 4] :: [Integer]依此类推。

同样的问题适用于您编辑的示例：

[[[1,2,3], [4,5,6]], [7,8,9]]

该列表的第一个元素将具有类似的类型[[Integer]]，而第二个元素将具有类似的类型[Integer]。但这是不允许的。

第二件事：不仅列表不能有不均匀的深度，也不存在可以“查看”不同深度的不同嵌套列表的函数。like 类型的函数[[a]] -> [a]会从其输入列表中“剥离”一层嵌套，但会被a视为不透明类型——它不知道类型a是什么，所以如果你传递一个[[[Integer]]]参数，就不能利用flatten这个事实你给它的那个参数——<code>a 可以是任何东西！a[Integer]

因此，在 Haskell 中唯一可以完成的列表展平是在函数类型固定的某个深度移除嵌套。因此，例如，flatten只剥离一层嵌套，使用函数组合我们可以剥离两个或更多：flatten . flatten :: [[[a]]] -> [a]、、flatten . flatten . flatten :: [[[[a]]]] -> [a]等等。

于 2013-03-22T07:08:05.337 回答
2

[[[1,2,3], [4,5,6]], [7,8,9]]也不是有效的 Haskell 列表。它包含两个元素；第一个是[[1,2,3], [4,5,6]]which is a [[Int]]，第二个是 just [7,8,9]，which is just [Int]。

Haskell 中的列表始终是 type [a]，对于某些列表中的所有元素a必须相同。这意味着如果您正在处理嵌套列表，则每个元素都必须具有相同的嵌套程度。

基本的 Haskell 考试似乎不太可能要求您展平任意级别的嵌套。它几乎肯定只是想让你实现flatten :: [[a]] -> [a]，你可以从类型中看出它只删除了一个“级别”的列表。您可以在列表上调用它，例如[[[1], [[2]], [[3]]]，它是类型[[[Int]]，但类型清楚地表明结果将是[[Int]]，即它会返回[[1], [2], [3]]，而不是[1, 2, 3]。

您尝试做的问题是，当您flatten收到其 type 参数[[a]]并将其拆分为(x:xs)（除非它为空）时， thex将成为该[[a]]列表的一个元素，因此它将具有 type [a]。然后你试图调用flatten它，这样你就可以“一直向下”变平，但flatten需要一个 type 的参数[[a]]并且x是 type [a]。

思考为什么这不起作用的另一种方法是，如果它确实起作用，您最终会到达列表的最后一个“级别”，x甚至根本不是列表类型。但是你会再次将它传递给它flatten，它会尝试将它与任何一个模式匹配，[]或者(x:xs)，并且必须失败。你得到的类型错误是阻止这种情况发生的原因。

于 2013-03-22T07:05:31.590 回答
2

您可以编写一个可以展平任意深度嵌套列表的函数，但嵌套级别必须一致（至少如果您想保留列表）：

{-# LANGUAGE FlexibleInstances
  , OverlappingInstances
  , IncoherentInstances  #-}

class Nested a where
  flatten :: [a] -> [Int]

instance Nested Int where
  flatten = id

instance (Nested a) => Nested [a] where
  flatten xss = concatMap flatten xss

-- e.g. now this works ...
flatten [[1 :: Int,2,3],[2,3,4]]   
-- ... and this too ...
flatten [[[1 :: Int,2,3],[2,3,4]],[[25]]]   
-- ... but this won't work
-- flatten [[[1 :: Int,2,3],[2,3,4]],25]

如果你想允许任意嵌套，你必须包装你的类型：

{-# LANGUAGE ExistentialQuantification }

class Foo a

instance Foo Int

instance Foo [a]

data F = forall a. Foo a => F a

test = F [F (1 :: Int), F [F (2 :: Int), F [F (3 :: Int), F [F (4 :: Int)]]]]

现在你可以flatten为这种类型写一个。

但是，我不建议作为初学者来探索这个。首先，您需要更好地了解类型实际上应该如何工作。这些东西并不是微不足道的，它违背了 Haskell 类型系统的本质，所以每一个解释都会让你感到困惑。尝试以它们打算使用的方式使用这些类型，并在您真正熟悉常见用例时再回到这些问题。

于 2013-03-22T14:28:48.330 回答