理解Haskell中非递归列表推导的连接问题

Question

你好，我目前正在准备考试，遇到了一个问题，如标题所述，我的目标是使用列表解析创建一个非递归的 concat 函数。看一下解决方案：

concat3 :: [[a]] -> [a]
concat3 xss = [x | xs <- xss, x <-xs]

然而我不理解为什么那样能够起作用，希望能得到帮助。

- azthec

---

列表推导式是基于其他结构定义的。请在 Haskell98 报告中查找翻译并翻译您的函数。 - n. m.

换句话说，阅读：理解单子（列表） - Julien Langlois

Answer 1

(<-) 可以读作 "in"，如 [x | xs <- xss, x <- xs] 读作 "x for xs in xss and x in xs"，表示我们正在将列表中的每个元素解包到其组成部分-这有点像concat。

当然，有很多种方式来看待这个问题。

---

机械地说，列表推导式可以转换为do记法。

do xs <- xss
   x  <- xs
   return x

而 do 表示为 (>>=) 和 (>>)

xss >>= \xs -> xs >>= \x -> return x

然后(>>=)本身变成了concatMap，而return变成了(\x -> [x])，当我们在列表上实例化它们时。

concatMap (\xs -> concatMap (\x -> [x]) xs) xxs

如果你思考一下concatMap (\x -> [x])，你可能会认为它是在遍历一个列表，将每个元素转换为一个单元素的列表，然后将它们连接起来...这只是一种复杂而毫无意义的做法。

concatMap id xss

从 concatMap 的定义中我们得到：

concat (map id xss)

最后根据函子定律或常识得出：

concat xss

因此，函数的工作方式类似于 concat，这一点并不奇怪。

---

如果我们在“列表单子”中按语义方式倾向于解释 do 符号，会发生什么？

do xs <- xss
   x  <- xs
   return x

本质上，这可以理解为“从我们的列表中非确定性地选择一个部分列表，然后从该列表中非确定性地选择一个元素 - 从此过程中收集所有可能性”，再次表明我们只是在连接。

---

我们还可以从Control.Monad函数join中取得幸运的对应关系。

join              :: (Monad m) => m (m a) -> m a  -- this looks `concat`-like!
join x            =  x >>= id

如果我们考虑内部的 xs >>= \x -> return x，然后使用 eta-conversion，我们有xs >>= return，这就是"right identity"单子律，帮助我们看到

xss >>= \xs -> xs >>= \x -> return x
===
xss >>= \xs -> xs >>= return
===
xss >>= \xs -> xs
===
xss >>= id
===
join xss

然后，我们可以查找如何在列表单子中实例化 join 并看到 join = concat。

---

因此，有许多方法可以通过列表推导式来实现 concat，具体取决于您想如何思考列表推导式。伟大的部分是这些都是等效的，并且可以相互建立起来，形成列表及其单子实例的基础含义。

- J. Abrahamson

---

回答很好，但我认为它过于高级，对OP没有帮助。 - luqui

谢谢，我有点担心它难以理解，但希望直觉和计算的平衡能为答案打下基础。我认为你提供的重要直觉是我忽略了的，所以很高兴你加入了进来。 - J. Abrahamson

两个答案都做得非常好，luqui 帮助我理解如何使用列表推导式创建它们，而 tels 则帮助我理解为什么它有效。感谢您的时间。 - azthec

Answer 2

你可以将列表推导式想象成一个嵌套的循环。因此，

[ z | x <- list1, y <- list2 ]

对于列表1中的每个x，对于列表2中的每个y，产生一个z，并将所有产生的值按顺序组成的列表作为结果。请注意，要产生的值在符号中首先出现。因此，如果我们有：

[ (x,y) | x <- [1,2], y <- [3,4,5] ]

这句话的意思是：对于[1,2]中的每个x，对于[3,4,5]中的每个y，生成(x,y)。因此我们得到：

[ (1,3), (1,4), (1,5),   -- when x = 1
  (2,3), (2,4), (2,5) ]  -- when x = 2

带有列表推导式记忆技巧，我们可以阅读你的 concat3 定义。

concat3 xss = [ x | xs <- xss, x <- xs ]

我将重命名变量，以使其更易于阅读：

concat3 listOfLists = [ x | list <- listOfLists, x <- list ]

我们现在可以将其理解为：对于listOfLists中的每个list，对于list中的每个x，产生x。也就是说，先产生第一个列表中的所有元素，然后产生第二个列表中的所有元素，以此类推，这相当于连接所有列表。

我使用的命名方式不太可能在实际中见到。惯例上，用以表示列表的变量通常使用以s结尾的“复数”名称。将xs发音为“exes”。按照语言类比的惯例（虽然这仍然是常规做法），我们会对列表的列表进行“双复数化”，即xss。我通常不会发音，因为“exeses”听起来太傻了。所以通过名称，您可以看出xss是一个列表的列表，而xs是一个列表，这将帮助您阅读这些密集的表达式。

- luqui

---

自从几十年前我的函数式编程讲师这样称呼它以来，我一直将xss的发音与excesses相同！ - AndrewC