在 Haskell 中浏览列表拆分函数

Question

这是我之前的跟进。

我试图从 here 中理解 Haskell 中的列表拆分示例：

foldr (\a ~(x,y) -> (a:y,x)) ([],[])

我可以阅读 Haskell 并知道 foldr 是什么，但不理解这段代码。你能带我看一下这段代码并详细解释一下吗？

Answer 1

让我们在示例输入列表上尝试运行这个函数，比如 [1,2,3,4,5]:

我们从 foldr (\a ~(x,y) -> (a:y,x)) ([],[]) [1,2,3,4,5] 开始。这里 a 是列表的第一个元素，(x,y) 从 ([],[]) 开始，所以 (a:y,x) returns ([1],[]).
输入列表的下一个元素是 a = 2 和 (x,y) = ([1],[])，所以 (a:y,x) = ([2],[1])。请注意，列表的顺序已交换。每次迭代都会再次交换列表；但是，输入列表的下一个元素将始终添加到第一个列表，这就是拆分的方式。
输入列表的下一个元素是a = 3和(x,y) = ([2],[1])，所以(a:y,x) = ([3,1],[2])。
输入列表的下一个元素是a = 4和(x,y) = ([3,1],[2])，所以(a:y,x) = ([4,2],[3,1])。
输入列表的下一个元素是a = 4和(x,y) = ([4,2],[3,1])，所以(a:y,x) = ([5,3,1],[4,2])。
没有剩余的元素，所以 return 值为 ([5,3,1],[4,2])。

如演练所示，split 函数的工作原理是维护两个列表，在每次迭代时交换它们，并将输入的每个元素附加到不同的列表。

Answer 2

我们可以看一个例子。例如，如果我们有一个列表 [1, 4, 2, 5]。如果我们这样处理列表，那么我们会看到 foldr 将被计算为：

foldr (\a ~(x,y) -> (a:y,x)) ([],[]) [1,4,2,5]

所以这里 a 首先是列表的第一项，然后它会变成 return 类似的东西：

(1:<b>y</b>, <b>x</b>)
    where (<b>x</b>, <b>y</b>) = foldr (\a ~(x,y) -> (a:y,x)) ([],[]) [4,2,5]

注意这里 (x, y) 元组是 交换的 当我们将 a 添加到 2 元组的第一项时。

(1:y, x)
    where (x, y) = (4:<b>y'</b>, <b>x'</b>)
          (<b>x'</b>, <b>y'</b>) = foldr (\a ~(x,y) -> (a:y,x)) ([],[]) [2,5]

如果我们继续这样做，我们将获得：

(1:y, x)
    where (x, y) = (4:y', x')
          (x', y') = (2:<b>y''</b>, <b>x''</b>)
          (x'', y'') = (5:<b>y'''</b>, <b>x'''</b>)
          (x''', y''') = foldr (\a ~(x,y) -> (a:y,x)) ([],[]) []

由于我们到达了列表的末尾，因此我们获得了 foldr … ([], []) [] 的二元组 ([], []):

(1:y, x)
    where (x, y) = (4:y', x')
          (x', y') = (2:y'', x'')
          (x'', y'') = (5:y''', x''')
          (x''', y''') = ([],[])

所以x''' = []和y''' = []，所以这就解决了：

(1:y, x)
    where (x, y) = (4:y', x')
          (x', y') = (2:y'', x'')
          (x'', y'') = (5:[], [])
          (x''', y''') = ([],[])

所以 x'' = [5] 和 y'' = []:

(1:y, x)
    where (x, y) = (4:y', x')
          (x', y') = (2:[], [5])
          (x'', y'') = (5:[], [])
          (x''', y''') = ([],[])

所以 x' = [5] 和 y' = [2]:

(1:y, x)
    where (x, y) = (4:[5], [2])
          (x', y') = (2:[], [5])
          (x'', y'') = (5:[], [])
          (x''', y''') = ([],[])

所以x = [4, 5]和y = [2]所以最终我们得到：

(1:[2], [4,5])
    where (x, y) = (4:[5], [2])
          (x', y') = (2:[], [5])
          (x'', y'') = (5:[], [])
          (x''', y''') = ([],[])

所以结果是预期的 ([1,2], [4,5])。

Answer 3

所以一切都发生在 \a ~(x,y) -> (a:y,x) 函数中，首先 a 是所提供列表的最后一项，而 (x,y) 是以 [= 开头的交替元组累加器15=]。 a:y 将当前元素添加到 y 之前，但元组中的 x 和 y 列表会被交换。

但是值得一提的是，所有新的附加项都在元组的第一侧返回，这保证了第一侧最终从列表的第一项开始，因为它被附加到最后一个。

因此对于 [1,2,3,4,5,6] 的列表，步骤如下

a          (x   ,   y)      return
----------------------------------
6       ([]     , []     ) (6:y, x)
5       ([6]    , []     ) (5:y, x)
4       ([5]    , [6]    ) (4:y, x)
3       ([4,6]  , [5]    ) (3:y, x)
2       ([3,5]  , [4,6]  ) (2:y, x)
1       ([2,4,6], [3,5]  ) (1:y, x)
[]      ([1,3,5], [2,4,6]) no return

关于波浪号 ~ 运算符，最好在 Haskell 指南的 Haskell/Laziness 主题中进行如下描述

Prepending a pattern with a tilde sign delays the evaluation of the value until the component parts are actually used. But you run the risk that the value might not match the pattern — you're telling the compiler 'Trust me, I know it'll work out'. (If it turns out it doesn't match the pattern, you get a runtime error.) To illustrate the difference:

Prelude> let f (x,y) = 1
Prelude> f undefined
*** Exception: Prelude.undefined

Prelude> let f ~(x,y) = 1
Prelude> f undefined
1

In the first example, the value is evaluated because it has to match the tuple pattern. You evaluate undefined and get undefined, which stops the proceedings. In the latter example, you don't bother evaluating the parameter until it's needed, which turns out to be never, so it doesn't matter you passed it undefined.

Answer 4

大约

foldr (\a ~(x,y) -> (a:y,x)) ([],[]) [a,b,c,d,e]
=
let g a ~(x,y) = (a:y,x) in
g a $ g b $ g c $ g d $ g e ([],[])
=
g a $ g b $ g c $ g d $ ([e],[])
=
g a $ g b $ g c $ ([d],[e])
=
g a $ g b $ ([c,e],[d])
=
g a $ ([b,d],[c,e])
=
([a,c,e],[b,d])

但说真的，

foldr (\a ~(x,y) -> (a:y,x)) ([],[]) [a,b,c,d,e]
=
let g a ~(x,y) = (a:y,x) in
g a $ foldr g ([],[]) [b,c,d,e]
=
(a:y,x) where 
    (x,y) = foldr g ([],[]) [b,c,d,e]
=
(a:y,x) where 
    (x,y) = (b:y2,x2) where
                 (x2,y2) = foldr g ([],[]) [c,d,e]
=
(a:y,x) where 
    (x,y) = (b:y2,x2) where
                 (x2,y2) = (c:y3,x3) where
                                (x3,y3) = (d:y4,x4) where
                                               (x4,y4) = (e:y5,x5) where
                                                              (x5,y5) = ([],[])

这是通过访问（如果和何时）以自上而下方式强制执行的，逐渐充实为，例如，

=
(a:x2,b:y2) where 
                 (x2,y2) = (c:y3,x3) where
                                (x3,y3) = (d:y4,x4) where
                                               (x4,y4) = (e:y5,x5) where
                                                              (x5,y5) = ([],[])
=
(a:c:y3,b:x3) where 
                                (x3,y3) = (d:y4,x4) where
                                               (x4,y4) = (e:y5,x5) where
                                                              (x5,y5) = ([],[])
=
(a:c:x4,b:d:y4) where 
                                               (x4,y4) = (e:y5,x5) where
                                                              (x5,y5) = ([],[])
=
(a:c:e:y5,b:d:x5) where 
                                                              (x5,y5) = ([],[])
=
(a:c:e:[],b:d:[])

但可能会以不同的顺序执行强制，具体取决于它的调用方式，例如

print . (!!1) . snd $ foldr (\a ~(x,y) -> (a:y,x)) ([],[]) [a,b,c,d,e]
print . (!!2) . fst $ foldr (\a ~(x,y) -> (a:y,x)) ([],[]) [a,b,c,d,e]

等

编辑： 解决关于惰性模式的问题，这样做是为了使结果函数具有适当的惰性：

foldr 在其第二个参数中使用 strict 的组合函数，编码递归，即自底向上。先构造列表其余部分递归处理的结果，然后将结果的头部分与其结合。
foldr 在其第二个参数中使用 lazy 组合函数，编码 corecursion，即自上而下。结果值的头部先构建，其余部分稍后填充。这让人想起 Prolog 和其他地方的 tail recursion modulo cons。惰性求值作为一个概念来自“CONS 不应该求值它的参数”； TRMC 直到稍后才评估构造函数的 second 参数，这才是真正重要的。

Answer 5

实际上，折叠函数会交替添加输入列表中的下一个项目。 Python 等语言中的类似函数是

def split(xs):
    a0 = a = []
    b0 = b = []
    for x in xs:
        a.append(x)
        a, b = b, a
    return a0, b0

使用惰性模式有两个原因：

允许立即使用结果列表，无需等待 foldr 使用所有输入
允许拆分无限列表。

考虑这个例子：

let (odds, evens) = foldr (\a ~(x,y) -> (a:y,x)) ([],[]) $ [1..]
in take 5 odds

结果是[1,3,5,7,9].

如果您放弃惰性模式并使用

let (odds, evens) = foldr (\a (x,y) -> (a:y,x)) ([],[]) $ [1..]
in take 10 odds

代码永远不会终止，因为 take 如果不首先计算整个奇数值列表就无法获取第一个元素（更不用说前五个元素了）。

这是为什么？考虑 Data.List.foldr:

的定义

foldr k z = go
  where
    go [] = z
    go (y:ys) = y `k` go ys

如果 k = \a (x,y) -> (a:y, x) 在两个参数中都是严格的，那么 y `k` go ys 的计算不会终止，直到达到 go 的基本情况。

使用惰性模式，功能相当于

\a p -> (a:snd p, fst p)

意味着我们永远不必在 p 上匹配，直到 fst 或 snd 这样做；该函数现在在其第二个参数中是惰性的。也就是说

go (y:ys) = y `k` go ys
          = (\a p -> (a:snd p, fst p)) y (go ys)
          = let p = go ys in (y:snd p, fst p)

立即

returns，无需进一步计算 go。只有当我们尝试获取任一列表的第二个元素时，我们才需要再次调用 go，但是我们再次只需要前进一步。

Answer 6

让我们翻译折叠。

splatter :: [a] -> ([a], [a])
splatter = foldr (\a ~(x,y) -> (a:y,x)) ([],[])

这是什么意思？ foldr 列表已定义

foldr :: (a -> r -> r) -> r -> [a] -> r
foldr k z = go
  where
    go [] = z
    go (p : ps) = p `k` go ps

让我们将其内联并简化：

splatter = go
  where
    go [] = ([], [])
    go (p : ps) =
      (\a ~(x,y) -> (a:y,x)) p (go ps)

splatter = go
  where
    go [] = ([], [])
    go (p : ps) =
      (\ ~(x,y) -> (p:y,x)) (go ps)

splatter = go
  where
    go [] = ([], [])
    go (p : ps) =
      let (x, y) = go ps
      in (p : y, x)

let 中的默认惰性模式匹配意味着我们实际上不会真正进行递归调用，直到有人强制 x 或 y.

要注意的关键是 x 和 y 在每次递归调用时交换位置。这导致交替模式。

在 Haskell 中浏览列表拆分函数

Walk through a list split function in Haskell

haskell

split

list

fold