理解奇数和偶数索引列表背后的 Haskell 逻辑

Question

我在 haskell 中遇到了一个问题，要求一个函数将一个列表分为两个不同的列表，以便偶数索引填充一个列表，奇数索引填充另一个列表。 示例：

func :: [Int] -> ([Int], [Int])

然后，如果我们输入 [44,8,11,23]，我们期望收到 [44,11] 和 [8,23]。 在互联网上查找时，我发现了一个很棒且天才的解决方案，但无法理解其背后的逻辑：

func :: [Int] -> ([Int], [Int])
func [] = ([], [])
func [x] = ([x], [])
func (x:y:xs) = (x:odds, y:evens)
    where
    (odds, evens) = func xs

我知道haskell中有“奇数”和“偶数”函数，但是“奇数s”和“偶数s”是什么意思。 这些值如何正确地到达特定列表？ 我因此陷入了怀疑。

我正在寻找几个论坛和教程来尝试理解这段代码的逻辑，但到目前为止我还处于零水平。

Answer 1

一点一点：

func (x:y:xs) = ...

当输入的长度 >=2 时，从

x

和

y

开始，然后继续列表 xs ...

          ... = (x:odds, y:evens)

...结果是一对，其第一个分量是

x : odds

，第二个分量是

y : evens

。变量

odds

和

evens

定义为 ...

    where
    (odds, evens) = func xs

...递归调用产生的那些（列表）值

func xs

。

---

举个例子：

func [1,2,3,4] =
func (1:2:xs) =   -- with xs = [3,4]
(1:odds, 2:evens) 
where (odds, evens) = func xs = func [3,4]

为了完成计算，我们然后计算递归调用：

func [3,4] =
func (3:4:xs2) =  -- with xs2 = []
(3:odds2, 4:odds2)
where (odds2, evens2) = func xs2 = func []

又一个递归调用来计算，但这是立即的：

func [] = ([], [])

。

所以，我们有

(odds2, evens2) = func [] = ([],[])
-- hence
odds2 = evens2 = []

发现这一点后，我们从前面的方程得到：

func [3,4] = (3:[], 4:[]) = ([3], [4])

所以，我们有

(odds, even) = ([3], [4])
-- hence
odds = [3]
evens = [4]

所以我们从更古老的方程中得到：

func [1,2,3,4] = (1:odds, 2:evens) = (1:[3], 2:[4]) = ([1,3], [2,4])