Haskell互递归实现：获取列表奇偶位置元素的原理疑问

哈哈，这个互递归的写法刚接触Haskell的时候确实容易懵，我当初第一次看的时候也绕了好一会儿！别担心，咱们一步步拆开来理清楚～

首先先把你提到的代码贴出来方便对照：

evens (x:xs) = x:odds xs
evens _ = []
odds (_:xs) = evens xs
odds _ = []

先搞懂每个函数的模式匹配逻辑 #

Haskell的函数是靠模式匹配来分支处理不同情况的，咱们逐个看：

• evens (x:xs)：当输入是一个非空列表时（x是列表的第一个元素，xs是剩下的元素组成的子列表），我们把x放到结果里，然后调用odds去处理剩下的xs。
• evens _：如果输入是空列表或者其他任何不匹配上面模式的情况，直接返回空列表[]。
• odds (_:xs)：当输入是非空列表时，我们用_忽略掉第一个元素（因为我们不需要它），然后调用evens去处理剩下的xs。
• odds _：同样，空列表或其他情况返回空列表。

用具体例子走一遍运行流程 #

咱们拿evens [1,2,3,4,5]来一步步模拟，你就能看清楚遍历和位置判断的过程了：

1. 调用evens [1,2,3,4,5]：匹配到evens (x:xs)，这里x=1，xs=[2,3,4,5]，所以结果是1 : odds [2,3,4,5]。
2. 接下来执行odds [2,3,4,5]：匹配到odds (_:xs)，忽略第一个元素2，xs=[3,4,5]，所以调用evens [3,4,5]。
3. 调用evens [3,4,5]：匹配到evens (x:xs)，x=3，xs=[4,5]，结果是3 : odds [4,5]。
4. 执行odds [4,5]：匹配到odds (_:xs)，忽略4，xs=[5]，调用evens [5]。
5. 调用evens [5]：匹配到evens (x:xs)，x=5，xs=[]，结果是5 : odds []。
6. 执行odds []：匹配到odds _，返回[]。

现在把所有结果串起来：1 : 3 : 5 : []，也就是[1,3,5]——正好是原列表的奇数位置元素（第1、3、5位）。

如果我们调用odds [1,2,3,4,5]，流程类似：

1. odds [1,2,3,4,5] → 忽略1，调用evens [2,3,4,5]
2. evens [2,3,4,5] → 取2，调用odds [3,4,5]
3. odds [3,4,5] → 忽略3，调用evens [4,5]
4. evens [4,5] → 取4，调用odds [5]
5. odds [5] → 忽略5，调用evens []
6. evens [] → 返回[]

最终结果是2 : 4 : []，也就是[2,4]——原列表的偶数位置元素。

为什么不需要显式索引？ #

这就是Haskell这种函数式语言的巧妙之处：互递归的调用链本身就隐含了“当前该取奇数位置还是偶数位置”的信息。

• 当evens被调用时，意味着我们当前要处理的是“奇数位置”的元素（相对于初始调用的位置），所以直接取当前列表的第一个元素。
• 当odds被调用时，意味着我们当前要跳过“偶数位置”的元素，所以忽略掉第一个元素，把后续的列表交还给evens，让它继续处理下一个奇数位置。

整个过程没有用到任何索引变量，完全靠函数调用的切换和模式匹配来完成遍历和位置判断，非常简洁优雅～

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