我最近开始学习 Haskell。
我在网上找到了这段代码，它返回列表中所有偶数/奇数位置的元素。
它利用了相互递归，但我似乎无法理解它在内部是如何工作的。
evens (x:xs) = x:odds xs
evens _ = []
odds (_:xs) = evens xs
odds _ = []
特别是，我不明白列表是如何向前推进和评估所有元素的。即使没有明确的索引检查，它如何检查偶数位置
有人可以提供见解吗？
问问题
5503 次
4 回答
6
首先，让我们达成一致意见：我们大部分时间都使用从 0 开始的索引，对吗？所以，如果我要问你列表中位置 2 的元素是什么
a : b : c : d : []
你会回答c。编辑：如果您不熟悉 Haskell 表示法，:则它是列表构造函数，a : b表示通过a在 list 前面添加的列表b。
移动到偶数位置的元素，aandc将是显而易见的答案，而bandd将处于奇数位置。我们来看看 的定义even。
evens (x:xs) = x:odds xs
evens [] = []
基本情况很简单：空列表中的偶数位置没有元素
归纳案例表明位置 0(
x) 中的元素位于偶数位置 - 确实如此 - 它还表明列表中偶数位置的所有其他元素都位于列表(x:xs)中的奇数位置xs。实际上， list 中第 2 位的元素在 list(x:xs)中的第 1 位xs，第 4 位的元素在第 3 位，依此类推；那有意义吗？
使用同样的推理，列表中奇数位置的(x:xs)元素是列表中偶数位置的元素xs，这正是odds上面的定义。
于 2018-04-15T16:07:26.683 回答
1
用于Debug.Trace查看索引如何随每个递归调用而变化。该trace函数在返回其第二个参数之前将其第一个参数打印到标准错误。
import Debug.Trace
evens (x:xs) = x : odds (trace (show (zip [0..] xs)) xs)
evens [] = []
odds (_:xs) = evens (trace (show (zip [0..] xs)) xs)
odds [] = []
main = print (evens "abcdefg")
标准错误将显示
[(0,'b'),(1,'c'),(2,'d'),(3,'e'),(4,'f'),(5,'g')]
[(0,'c'),(1,'d'),(2,'e'),(3,'f'),(4,'g')]
[(0,'d'),(1,'e'),(2,'f'),(3,'g')]
[(0,'e'),(1,'f'),(2,'g')]
[(0,'f'),(1,'g')]
[(0,'g')]
[]
每次进行递归调用时，每个原始项目的位置都会“移动”一个位置。g，例如，在原始列表中的偶数位置，但在每个递归调用中从偶数位置交替到奇数位置。
于 2018-04-15T21:47:52.827 回答
0
evens让我们看一下输入列表上的示例评估。我将使用"abcde"--recall ，它String是字符列表的别名[Char]，所以这等效于['a', 'b', 'c', 'd', 'e']or 'a' : 'b' : 'c' : 'd' : 'e' : []。
我们从初始输入开始：
evens "abcde"
匹配 的第一个模式evens，添加'a'到结果的开头并继续处理列表的其余部分：
evens "abcde"
-------------
-- evens (x : xs) = x : odds xs
-- x = 'a'
-- xs = "bcde"
-- evens "abcde" = 'a' : odds "bcde"
'a' : odds "bcde"
-----------------
匹配 的第一个模式odds，忽略'b'并继续：
'a' : odds "bcde"
-----------
-- odds (_ : xs) = evens xs
-- xs = "cde"
-- odds "bcde" = evens "cde"
'a' : evens "cde"
-----------
的第一个模式evens，添加'c'：
'a' : evens "cde"
-----------
-- evens (x : xs) = x : odds xs
-- x = 'c'
-- xs = "de"
-- evens "cde" = 'c' : odds "de"
'a' : 'c' : odds "de"
---------------
的第一个模式odds，忽略'd'：
'a' : 'c' : odds "de"
---------
-- odds (_ : xs) = evens xs
-- xs = "e"
-- odds "de" = evens "e"
'a' : 'c' : evens "e"
---------
的第一个模式evens，添加'e'：
'a' : 'c' : evens "e"
---------
-- evens (x : xs) = x : odds xs
-- x = 'e'
-- xs = "" = []
-- evens "e" = 'e' : odds ""
'a' : 'c' : 'e' : odds ""
-------------
现在，最后，第一个模式odds不匹配，因为空列表[]与列表构造函数不匹配_ : _，所以我们进入第二个（默认）模式：
'a' : 'c' : 'e' : odds ""
-------
-- odds _ = []
-- odds "" = []
'a' : 'c' : 'e' : []
--
给出最终结果：
"ace"
基本上，这些函数将输入视为值的“流”并生成一个流作为结果：evens消耗一个元素并将其输出到结果，然后继续获取odds其余元素；whileodds消耗一个元素并丢弃它，取evens其余元素。
这不会对索引进行任何计算，因为它没有必要——它只是遵循列表的结构。根据定义，列表中的第一个值位于偶数索引处（从 0 计数时），因此evens保留它并获取余数的奇数索引，同时odds丢弃它并获取余数的偶数索引。删除每个元素会将所有索引向下移动一个 - 也就是说，1输入列表中位于 index处的元素位于输入0尾部的 index 处：
zip [0..] "abcde" == [(0, 'a'), (1, 'b'), (2, 'c'), (3, 'd'), (4, 'e')]
'a' 'b' 'c' 'd' 'e'
0 1 2 3 4
| | | | |
x / / / /
/ / / /
/ / / /
/ / / /
| | | |
'b' 'c' 'd' 'e'
0 1 2 3
zip [0..] "bcde" == [(0, 'b'), (1, 'c'), (2, 'd'), (3, 'e')]
您还可以使用索引而不是相互递归来显式实现这些函数。使用列表推导：
evens xs = [x | (i, x) <- zip [0..] xs, even i]
odds xs = [x | (i, x) <- zip [0..] xs, odd i]
或使用明确的mapand filter：
evens = map snd . filter (even . fst) . zip [0..]
odds = map snd . filter (odd . fst) . zip [0..]
然后你甚至可以将索引上的谓词变成一个参数：
indices f = map snd . filter (f . fst) . zip [0..]
evens = indices even
odds = indices odd
于 2018-04-17T03:26:39.630 回答
0
我们自己的语言非常强大。我在教自己微积分时遇到了极限问题，直到我读到牛顿的一段中的一句话。当然，那是英文的。
首先，您对未使用或不需要索引是正确的。
其次，代码不知道偶数或奇数之间的区别，您再次质疑它是正确的。
最后，我稍微修改了这些以在我的实现中正常工作。
evens [x] = [x]; evens (x:xs) = x:odds xs
odds [x] = []; odds (_:xs) = evens xs
他们是如何工作的。它构建输出列表。它获取列表中的第一项并使其成为输出列表的第一项或下一项。它用列表的其余部分调用赔率。赔率只是将它收到的尾部返回到偶数。
像tail一样，它丢弃它收到的第一项。
evens 生成一个列表，其中大约有一半的项目被丢弃。赔率只会产生关键的丢弃。
如果你给 evens 列表[0,1,2,3,4]，它会返回以 开头的所有其他项目0，即[0,2,4]。如果你给偶数[1,2,3,4]它返回的列表，[1,3]因为列表以奇数开头。无论从哪里开始，这就是它产生的结果。
尝试使用 [1,1,1,1,1] 或“bcdefg”
对函数所做的修改反映了每个函数分别对剩余元素所做的事情。赔率丢弃它，偶数将它附加到输出列表的末尾。
只有给定一个以偶数开头的列表时，这两个函数才能正常工作。如果给定一个带有奇数的列表，它们会反向工作。
这是一个函数，它将根据指定的起始编号和指定的结束编号生成偶数或奇数列表。
eo s e = [s,s+2..e]
于 2018-04-27T02:23:54.767 回答