如何在 Haskell 中将两个列表与列表理解结合起来？

Question

我想像运算符 ++ 一样合并两个列表。 [1,2,3] ++ [4,5,6] = [1,2,3,4,5,6]

所以我尝试了这个：

combine2 :: [a] -> [a] -> [a]
combine2 xs ys = [x : ys | x <- xs]

但这给了我：

a.hs:10:19: error:
    • Occurs check: cannot construct the infinite type: a ~ [a]
    • In the expression: x : ys
      In the expression: [x : ys | x <- xs]
      In an equation for ‘combine2’: combine2 xs ys = [x : ys | x <- xs]
    • Relevant bindings include
        x :: a (bound at a.hs:10:28)
        ys :: [a] (bound at a.hs:10:13)
        xs :: [a] (bound at a.hs:10:10)
        combine2 :: [a] -> [a] -> [a] (bound at a.hs:10:1)
   |
10 | combine2 xs ys = [x : ys | x <- xs]

如何解决？

Answer 1

您在这里生成了一个列表列表，其中您每次在 ys 前加上值 x。因此，这意味着如果 xs 是 xs = [1,3,0,2] 并且 ys 是 [1,4,2,5]，您构建了一个包含 [[1, 1, 4, 2, 5], [3, 1, 4, 2, 5], [0, 1, 4, 2, 5], [2, 1, 4, 2, 5]].

的列表列表

您可以在这里使用递归。这里的基本情况是第一个列表已用完。在那种情况下，我们 return 第二个列表，所以：

combine2 [] ys = ys

递归情况是第一个列表不为空，并且 x 作为第一个元素，xs 作为（可能为空的）尾巴。在那种情况下，我们产生 x 并在尾部递归 xs:

combine2 (x:xs) ys = x : combine xs ys

如果我们把这些放在一起，我们得到：

combine2 :: [a] -> [a] -> [a]
combine2 [] ys = ys
combine2 (x:xs) ys = x : combine2 xs ys

我们这里在递归的情况下每次都传ys。除了这样做，我们还可以使用辅助函数：

combine2 :: [a] -> [a] -> [a]
combine2 zs ys = go zs
    where go [] = ys
          go (x:xs) = x : go xs

Answer 2

修复它的方法是让它更通用。代替 combine2，写 combineN 并使用它来解决 combine2 问题。

combine2 :: [b] -> [b] -> [b]
combine2 xs ys = combineN [xs,ys]

combineN :: [[b]] -> [b]
combineN ls = [a | l <- ls, a <- l]

我们只是从列表的参数列表中绘制每个列表，然后从每个列表中绘制并生成每个元素，就好像在两个嵌套循环的内部循环中一样。在伪代码中：

  for l in ls:
     for a in l:
         produce a

测试：

> combine2 [1..3] [11..15]
[1,2,3,11,12,13,14,15]

--   l1:      l2:
-- [ [1,2,3], [11,12,13,14,15] ]    -- outer "loop"
-- [  1,2,3 ,  11,12,13,14,15  ]    -- inner "loop"

或者我们可以将其视为将我们的列表一个一个地放在另一个参差不齐的“矩阵”中，然后逐行、逐个元素地读取它：

-- [ [1,2,3] ,         -l1-    [  1,2,3 ,
--   [11,12,13,14,15]  -l2-       11,12,13,14,15
-- ]                           ]

“行”是ls = [xs,ys]中l的连续值，每一行中的元素是每个l中元素a的连续值.

嵌套循环本质上是列表解析。

Answer 3

查看您的代码的推断类型：

> combine2 xs ys = [x : ys | x <- xs]
> :type combine2
combine2 :: [a] -> [a] -> [[a]]

所以当你想要 return “a 的列表”时，你 return 正在输入“a 的列表”。编译器看到这两个都是列表，并尝试匹配元素类型，但发现一个包含“list of a”，而另一个只是“a”。由于类型变量 a 出现在类型“list of a”中，如果它们相等，这将是一种无限循环：a = [a] = [[a]] = [[[a]]] = …，这几乎不是你想要做的，所以类型检查器不允许它。

您的代码执行此操作：

combine2 [1, 2, 3] [4, 5, 6]
=
[ 1 : [4, 5, 6]
, 2 : [4, 5, 6]
, 3 : [4, 5, 6]
]
=
[ [1, 4, 5, 6]
, [2, 4, 5, 6]
, [3, 4, 5, 6]
]

当您希望它执行此操作时：

combine2 [1, 2, 3] [4, 5, 6]
=
[1, 2, 3, 4, 5, 6]

列表理解的解决方案是迭代每个列表，然后迭代这些列表中的每个项目：

combine2' xs ys = [z | zs <- [xs, ys], z <- zs]

在combine2' [1, 2, 3] [4, 5, 6]中，首先zs设置为[1, 2, 3]，所以z设置为1，然后2，然后3;然后 zs 设置为 [4, 5, 6]，因此 z 设置为 4，然后 5，然后 6。

你也可以从等式的角度来考虑这个问题，即使用 concatMap:

的列表推导式的去糖化

[z | zs <- [xs, ys], z <- zs]
=
concatMap (\ zs -> concatMap (\ z -> [z]) zs) [xs, ys]
=
concatMap (\ zs -> concatMap pure zs) [xs, ys]
=
concatMap (\ zs -> concat (map pure zs)) [xs, ys]
=
concatMap (\ zs -> zs) [xs, ys]
=
concatMap id [xs, ys]
=
concat (map id [xs, ys])
=
concat [xs, ys]
=
foldr (++) [] [xs, ys]
=
xs ++ ys ++ []
=
xs ++ ys

本质上，您是在连接 all 个输入列表，在这种情况下，“all”恰好只有 2 个。

如何在 Haskell 中将两个列表与列表理解结合起来？

How to combine two lists with list comprehension in Haskell?

haskell

list-comprehension