判断一个列表是否有偶数个元素，而不计算元素的个数

Question

实现判断列表是否包含偶数个元素的isLengthEven :: [a] -> Bool函数。在本练习中，禁止使用length函数或返回列表元素个数的任何其他函数。提示:我们所要检查的是我们是否可以2乘2遍历整个列表，或者函数是否在最后遗漏了一个项。

示例: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)

返回正确的值，直到我插入第五个元素到列表中。对于大于或等于5的任何数量的元素，它返回True。我想递归部分有问题。

Answer 1

这里只需要两个基本情况:

1. 和空列表，长度为0，因此应该返回True;和
2. 一个单元素列表，它包含一个元素，因此具有奇数长度。

递归情况每次在列表中向前移动两步，因此:

isLengthEven :: [a] -> Bool
isLengthEven [] = True
isLengthEven [x] = False
isLengthEven (_:_:xs) = isLengthEvenxs

通常定义两个函数:isLengthEven和isLengthOdd，因此这些函数每次都递归地调用对方:

isLengthEven :: [a] -> Bool
isLengthEven [] = True
isLengthEven (_:xs) =isLengthOddxs
isLengthOdd :: [a] -> Bool
isLengthOdd [] = False
isLengthOdd (_:xs) =isLengthEvenxs

Answer 2

单步解

请注意，威廉的精彩答案已经是优化过的了。

如果您更喜欢直接的未优化版本并选择忽略提示，则可以只使用初始代码的第一个和最后一个子句。这样的:

-- 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)

这两个条款加在一起，涵盖了所有可能的情况。

附录:

实际上，这个函数为长输入使用了大量的堆栈空间。这可以通过常用的累加器作为参数技巧来修复。:

isLengthEven :: [a] -> Bool
isLengthEven xs = go True xs  where
go b   []    =  b
go b (x:xs)  =  go (not b) xs

其中go辅助步进函数是尾递归的。

在我的机器上，这个单步解决方案(包括最后一个更改)的性能非常接近问题文本中提倡的"二乘二"解决方案。

两种方法的性能都是直接但禁止的(even (length xs))解决方案的三分之二。