在不计算元素个数的情况下判断一个列表是否有偶数个元素
Decide if a list has an even number of elements without counting the number of elements
Implement the isLengthEven :: [a] -> Bool function that decides if a list contains an even number of elements. In this exercise, using the length function or any other function that returns the number of elements of a list is prohibited. Hint: All we have to check is whether we can walk the entirety of the list through two by two or does the function miss an item at the very end.
For example: isLengthEven "Apple" == True, isLengthEven "Even" == True, isLengthEven [] == False
到目前为止，我尝试了模式匹配和递归，在我看来这是进行此练习的最佳方式。我的代码如下：
isLengthEven :: [a] -> Bool
isLengthEven [] = False
isLengthEven (x:[]) = False
isLengthEven (x:(y:[])) = True
isLengthEven (x:(y:(z:[]))) = False
isLengthEven (x:(y:(z:(q:[])))) = True
isLengthEven (x:xs) = isLengthEven (xs)
这 returns 正确的值，直到我将第五个元素插入到列表中。它 returns True 对于大于或等于 5 的任意数量的元素。我想递归部分有问题。
这里你只需要两个基本案例：
- 一个空列表，其长度为
0，因此应该return True；和
- 一个 单例 列表，其中包含一个元素，因此长度为奇数。
递归情况每次在列表中向前移动两步，所以：
isLengthEven :: [a] -> Bool
isLengthEven [] = True
isLengthEven [x] = False
isLengthEven (_:_:<strong>xs</strong>) = isLengthEven <strong>xs</strong>
通常定义两个函数：isLengthEven 和 isLengthOdd 因此这些函数每次都递归地相互调用：
isLengthEven :: [a] -> Bool
isLengthEven [] = True
isLengthEven (_:xs) = <b>isLengthOdd</b> xs
isLengthOdd :: [a] -> Bool
isLengthOdd [] = False
isLengthOdd (_:<strong>xs</strong>) = <b>isLengthEven</b> xs
单步解决方案
注意，优秀的已经是优化过的
如果您更喜欢直接的未优化版本并选择忽略提示，您可以只使用初始代码的第一个和最后一个子句。像这样：
-- warning: the following is incorrect, needs changes:
isLengthEven :: [a] -> Bool
isLengthEven [] = False
isLengthEven (x:xs) = isLengthEven (xs)
这两个条款都不正确，但很容易改正：
isLengthEven :: [a] -> Bool
isLengthEven [] = True
isLengthEven (x:xs) = not (isLengthEven xs)
这两个条款放在一起，涵盖了所有可能的情况。
附录：
按原样，此函数使用大量堆栈 space 进行长输入。这可以通过常见的 accumulator-as-argument 技巧来解决。这里：
isLengthEven :: [a] -> Bool
isLengthEven xs = go True xs where
go b [] = b
go b (x:xs) = go (not b) xs
其中 go 辅助步进函数是尾递归的。
在我的机器上，这个单步解决方案（包括最后一个更改）的性能非常接近问题文本中提倡的“两两”解决方案。
这两种方法的性能大约是直接但被禁止的 (even (length xs)) 解决方案的三分之二。
Implement the
isLengthEven :: [a] -> Boolfunction that decides if a list contains an even number of elements. In this exercise, using thelengthfunction or any other function that returns the number of elements of a list is prohibited. Hint: All we have to check is whether we can walk the entirety of the list through two by two or does the function miss an item at the very end.
For example:
isLengthEven "Apple" == True,isLengthEven "Even" == True,isLengthEven [] == False
到目前为止，我尝试了模式匹配和递归，在我看来这是进行此练习的最佳方式。我的代码如下：
isLengthEven :: [a] -> Bool
isLengthEven [] = False
isLengthEven (x:[]) = False
isLengthEven (x:(y:[])) = True
isLengthEven (x:(y:(z:[]))) = False
isLengthEven (x:(y:(z:(q:[])))) = True
isLengthEven (x:xs) = isLengthEven (xs)
这 returns 正确的值，直到我将第五个元素插入到列表中。它 returns True 对于大于或等于 5 的任意数量的元素。我想递归部分有问题。
这里你只需要两个基本案例：
- 一个空列表，其长度为
0，因此应该returnTrue；和 - 一个 单例 列表，其中包含一个元素，因此长度为奇数。
递归情况每次在列表中向前移动两步，所以：
isLengthEven :: [a] -> Bool
isLengthEven [] = True
isLengthEven [x] = False
isLengthEven (_:_:<strong>xs</strong>) = isLengthEven <strong>xs</strong>
通常定义两个函数：isLengthEven 和 isLengthOdd 因此这些函数每次都递归地相互调用：
isLengthEven :: [a] -> Bool
isLengthEven [] = True
isLengthEven (_:xs) = <b>isLengthOdd</b> xs
isLengthOdd :: [a] -> Bool
isLengthOdd [] = False
isLengthOdd (_:<strong>xs</strong>) = <b>isLengthEven</b> xs
单步解决方案
注意，优秀的
如果您更喜欢直接的未优化版本并选择忽略提示，您可以只使用初始代码的第一个和最后一个子句。像这样：
-- warning: the following is incorrect, needs changes:
isLengthEven :: [a] -> Bool
isLengthEven [] = False
isLengthEven (x:xs) = isLengthEven (xs)
这两个条款都不正确，但很容易改正：
isLengthEven :: [a] -> Bool
isLengthEven [] = True
isLengthEven (x:xs) = not (isLengthEven xs)
这两个条款放在一起，涵盖了所有可能的情况。
附录：
按原样，此函数使用大量堆栈 space 进行长输入。这可以通过常见的 accumulator-as-argument 技巧来解决。这里：
isLengthEven :: [a] -> Bool
isLengthEven xs = go True xs where
go b [] = b
go b (x:xs) = go (not b) xs
其中 go 辅助步进函数是尾递归的。
在我的机器上，这个单步解决方案（包括最后一个更改）的性能非常接近问题文本中提倡的“两两”解决方案。
这两种方法的性能大约是直接但被禁止的 (even (length xs)) 解决方案的三分之二。