Haskell中picks函数的实现逻辑与运行原理是什么？

函数定义与功能 #

picks 函数的作用是遍历输入列表的每一个元素，返回「被取出的元素 + 取出该元素后剩余元素组成的列表」配对的元组集合，定义如下：

picks :: [a] -> [(a, [a])]
picks [] = []
picks (x:xs) = (x,xs) : [(y,x:ys)| (y,ys) <- picks xs]

代码逻辑拆解：

• 边界条件：输入为空列表时直接返回空列表
• 递归分支：将输入列表拆分为头元素x和剩余子列表xs
  1. 先生成第一个元组：直接配对当前头元素x和未处理的子列表xs
  2. 递归调用picks处理子列表xs，遍历递归返回的所有(y, ys)元组，将当前头元素x插入到剩余列表ys的头部，生成新的元组(y, x:ys)
  3. 将第一步的元组和第二步生成的所有元组拼接，作为当前层的返回结果

递归展开过程（以 picks [1..4] 为例） #

我们从最短的子列表开始逐层向上计算，就能清晰看到所有元组的生成逻辑：

1. 计算 picks [4]
   输入拆分后x=4，xs=[]
   第一层元组为(4, [])，递归调用picks []返回空，列表推导式无结果
   最终结果：picks [4] = [(4, [])]
2. 计算 picks [3,4]
   输入拆分后x=3，xs=[4]
   第一层元组为(3, [4])，递归调用picks [4]得到[(4, [])]
   遍历递归结果生成新元组：(4, 3:[]) = (4, [3])
   最终结果：picks [3,4] = [(3,[4]), (4,[3])]
3. 计算 picks [2,3,4]
   输入拆分后x=2，xs=[3,4]
   第一层元组为(2, [3,4])，递归调用picks [3,4]得到[(3,[4]), (4,[3])]
   遍历递归结果生成新元组：
   • (3, 2:[4]) = (3, [2,4])
   • (4, 2:[3]) = (4, [2,3])
     最终结果：picks [2,3,4] = [(2,[3,4]), (3,[2,4]), (4,[2,3])]
4. 计算 picks [1,2,3,4]
   输入拆分后x=1，xs=[2,3,4]
   第一层元组为(1, [2,3,4])，递归调用picks [2,3,4]得到上一步的三个元组
   遍历递归结果生成新元组：
   • (2, 1:[3,4]) = (2, [1,3,4])
   • (3, 1:[2,4]) = (3, [1,2,4])
   • (4, 1:[2,3]) = (4, [1,2,3])
     最终结果：[(1,[2,3,4]),(2,[1,3,4]),(3,[1,2,4]),(4,[1,2,3])]，和示例输出完全一致。

核心逻辑总结 #

递归的每一层都在处理当前的头元素x：除了第一个元组是直接取出x的场景之外，后面的所有元组对应「取出子列表xs中的元素」的场景——此时当前层的x属于剩余未被取出的元素，所以要插回剩余列表的头部。

内容的提问来源于stack exchange，提问作者Lau Sandt