Select Haskell 中的配对函数

Question

在我的 class 中，我们的教授使用这个 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)

Answer 1

select returns 对于给定的 2 元组列表，其中每个项目的第一个项目是项目 selected，第二个项目是所有元素的列表，除了select编辑了一个。

所以这意味着：

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

对于空列表，我们因此 return 一个空列表（2 元组），因为我们不能 select 单个元素。

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

我们select第一个元素，我们使用尾部作为剩余元素的列表；和
我们select另一个元素。我们可以在尾部递归，因此 select 从尾部开始一个元素，但尾部当然不包含元素列表的头部剩余元素。我们稍后需要将 x 添加到所有项目。

我们可以通过在每个剩余元素列表前添加 x 的映射来做到这一点。

例如，如果我们执行 select [1, 4] 那么我们就得到第一个元素：

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

select [4] 将 return:

select [4] = (4, []) : map (\(y, ys) -&gt; (y, x : ys)) (select [])

select 对于空列表 return 是一个空列表，所以这意味着：

select [4] = (4, []) : map (\(y, ys) -&gt; (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 表达式，它将二元组 (y, ys) 映射到二元组 (y, x : ys)，因此在 2 元组的第二项中添加列表。

Select Pair Function in Haskell