在 Haskell 中选择配对函数

Question

在我的课堂上，我们的教授使用了这个select函数来实现排列函数。

select :: [a] -> [(a,[a])]
select [] = []
select (x:xs) = (x,xs) : map(\(y,ys) ->(y,x:ys))(select xs)

在这段代码中，这部分让我感到困惑。

map(\(y,ys) ->(y,x:ys))(select xs)

我实际上不明白这部分的作用是什么

\(y,ys) ->(y,x:ys)

- bsknblc

---

那段代码可以有效地重写为 fmap (x:) 或 second (x:)，它作用于元组的第二个组件。 - Iceland_jack

Answer 1

select 根据给定的 2 元组列表返回结果，其中每个元素的第一项为选中的元素，第二项为除所选元素之外的所有元素列表。

这意味着：

Prelude> select [1,4,2,5]
[(1,[4,2,5]),(4,[1,2,5]),(2,[1,4,5]),(5,[1,4,2])]

对于一个空列表，我们返回一个空的（2元组）列表，因为我们不能选择单个元素。

对于至少包含一个元素的列表，有两种情况：

1. 我们选择第一个元素，并将剩余元素作为列表的尾部; 和
2. 我们选择另一个元素。我们可以在剩余元素上递归，从而选择尾部的元素，但是尾部当然不包含剩余元素列表的头元素。稍后，我们需要将 x 添加到所有项目中。

我们可以通过映射来实现，其中我们将 x 添加到每个剩余元素的列表前面。

例如，如果我们执行 select [1, 4]，则我们使用以下方法获取第一个元素：

select [1, 4] = (1, [4]) : map (\(y, ys) -> (y, x : ys)) (select [4])

选择 [4] 将返回：

select [4] = (4, []) : map (\(y, ys) -> (y, x : ys)) (select [])

如果选择一个空列表，则返回一个空列表，这意味着：

select [4] = (4, []) : map (\(y, ys) -> (y, x : ys)) []

因此：

select [4] = (4, []) : []

这相当于：

select [4] = [(4, [])]

对于select [1,4]，我们因此得到：

select [1, 4] = (1, [4]) : map (\(y, ys) -> (y, x : ys)) [(4, [])]

因此，我们需要向空列表中添加1，我们使用映射完成此操作，从而获得：

select [1, 4] = (1, [4]) : [(4, [1])]

这等同于：

select [1, 4] = [(1, [4]), (4, [1])]

\(y,ys) ->(y,x:ys)是一个lambda表达式，它将2元组(y, ys)映射为另一个2元组(y, x : ys)，因此将第二项中的列表插入到元组中。

- Willem Van Onsem

---

我尝试写出 [1,3] 的输出。在 select [3] part select [3] = (3,[]) : map (\(y,ys)->( ,3:[])) select [] 中，据我理解它返回的是 select [3] = (3,[]) :(_,[3])，但实际上它是 select [3] = (3,[]) :[]。我不明白为什么会这样。 - bsknblc

@BaşakBalcı：不，注意 [3] 是 (3:[]) 的简写，所以 x 是 3，xs 是 []。这意味着你要使用 map (...) (select [])，而 select [] 总是 []。 - Willem Van Onsem

我可以再问你一个问题吗？如果 xs 是 []，那么 y 和 ys 会是什么？ - bsknblc

@BaşakBalcı：对于一个空列表的 map f []，由于没有元素需要转换，因此永远不会调用映射函数 f。 - Willem Van Onsem