你好,我目前正在准备考试,遇到了一个问题,如标题所述,我的目标是使用列表解析创建一个非递归的 concat
函数。看一下解决方案:
concat3 :: [[a]] -> [a]
concat3 xss = [x | xs <- xss, x <-xs]
然而我不理解为什么那样能够起作用,希望能得到帮助。
你好,我目前正在准备考试,遇到了一个问题,如标题所述,我的目标是使用列表解析创建一个非递归的 concat
函数。看一下解决方案:
concat3 :: [[a]] -> [a]
concat3 xss = [x | xs <- xss, x <-xs]
然而我不理解为什么那样能够起作用,希望能得到帮助。
(<-)
可以读作 "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
,具体取决于您想如何思考列表推导式。伟大的部分是这些都是等效的,并且可以相互建立起来,形成列表及其单子实例的基础含义。
[ z | x <- list1, y <- list2 ]
[ (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
是一个列表,这将帮助您阅读这些密集的表达式。