我正在努力理解haskell语言，但我对它很困惑，因为我有以下练习，甚至不能从它开始：
evenNat :: Integer -> Bool，它接受一个非负整数作为输入确定它是否是偶数
(还有更多，但让我们现在专注于这个(
在所有这些程序中，都不允许使用内置的乘法、除法或模函数。
我应该如何开始，你能给我一些如何学习这种语言的建议吗？谢谢
一个整数是偶当且仅当其低位为0。当且仅当其低位为1时，它才是奇数。您可以在Data.Bits中使用一个简单的操作来测试这一点。
import Data.Bits
import Prelude hiding (even, odd)
even, odd :: Integer -> Bool
even x = ??
odd x = ??
也就是说，我认为Robin Zigmond可能对这次演习的意图是正确的。为了更直接地达到这个目的，你可以定义自己的数字。
import Prelude hiding (Integer, even, odd)
data PNat
= One
| Succ PNat
data Integer
= Negative PNat
| Zero
| Positive PNat
现在定义
evenNat :: PNat -> Bool
等等
evenNat :: Integer -> Bool，它接受一个非负整数作为输入并确定它是否为偶数
只需写下你所知道的：
evenNat :: Integer -> Bool
evenNat n | n < 0 = error "forbidden call to evenNat"
evenNat 0 = True
evenNat 1 = False
evenNat 2 = True
evenNat 3 = .....
.....
这是一个非常好的开始，只是，我们不希望明确列举所有必要的案例，以涵盖所有可能的输入。
但让我们停下来。我们将如何完成evenNat 3 = ...的定义？我们当然可以把明确的答案放在那里，False。但我们也可以注意到False == not True和True == evenNat 2，所以
evenNat 3 = False
= not True
= not (evenNat 2)
= not (evenNat (3 - 1))
实际上，
evenNat 2 = True
= not False
= not (evenNat 1)
= not (evenNat (2 - 1))
其完全遵循相同的模式。
就在那儿！剩下的就是，泛化通过将具体数据转化为变量，这样我们就得到了另一个最终子句
evenNat n = not (...... ( ... - ... ))
就这样。
效率方面的适度尝试：
让我们接受Robin的前提，即递归是这里的实际主题。
递归是指用一个更容易的问题，或者用一系列更容易问题来代替一个相对困难的问题。
例如，evenNat 43是对evenNat 42的否定。如果我们沿着这条路走，经过40多步后，我们到达evenNat 0，也就是众所周知的True。这个方案是可行的，但对于大数字来说可能有点慢。
一种更快的方法可以是在每一步中从手头的数字中减去2的最大可能幂。这样的子运算不会改变数字的偶数字符。所以43是偶数当且仅当(43-32(＝11是偶数。接下来，我们考虑(11-8(=3。因此，它看起来确实是一种更快的方法，尽管有些复杂。
首先，我们需要2的幂序列，直到手头的数字。当然，这可以递归地完成：
powersOf2UpToN :: Integer -> [Integer]
powersOf2UpToN n =
let -- defining auxiliary function sq:
sq m pwrs = if (head pwrs > m) -- if reached big enough
then (tail pwrs) -- then stop and return result
else -- augment:
let hps = head pwrs in sq m ((hps+hps):pwrs)
in (sq n [2])
请注意，我使用的是(hps+hps)而不是(2*hps)，因为练习的规则禁止本地乘法。
从本质上讲，只要我们保持在手头的数字以下，我们就会为幂序列准备越来越大的2次方。回想一下在Haskell中，将一个元素添加到列表中是一种廉价的操作。
ghci解释器下的测试：
$ ghci
λ>
λ> :load q64544005.hs
Ok, one module loaded.
λ>
λ> powersOf2UpToN 337
[256,128,64,32,16,8,4,2]
λ>
接下来，我们必须实现减去2的最大可能幂的函数。这样的函数将采用(数字，2的幂(对，并返回一个"改进"对，即具有较小的数字和缩短的幂列表。类型签名如下：
reduce2 :: (Integer, [Integer]) -> (Integer, [Integer])`
总体逻辑是：
reduce2 (n, pwrs) =
if (null pwrs) -- did we just run out of powers of 2 ?
then (n, []) -- nothing left to do
else if ((head pwrs) <= n) -- return a lower n if possible
...
请暂停阅读，看看你是否能填空
解决方案：在可能的情况下，我们减去2的最大剩余幂，它恰好位于(递减(列表的顶部。
reduce2 (n, pwrs) =
if (null pwrs)
then (n, []) -- nothing left to do
else if ((head pwrs) <= n) -- return a lower n if possible
then reduce2 ((n - (head pwrs)), tail pwrs)
else reduce2 (n, tail pwrs)
CCD_ 15的力学性能是关键。因此，为了帮助理解，让我们利用Haskell方便的小追踪工具。
在下面的代码中，表达式DT.trace msg res的计算结果仅为res，具有打印msg的副作用。是的，哈斯克尔通常禁止副作用，但追踪机构享有特殊特权。
这里是我们reduce2函数的一个跟踪版本：
import qualified Debug.Trace as DT
type DebugMsg = String
traceReduce2 :: DebugMsg -> (Integer, [Integer]) -> (Integer, [Integer])
traceReduce2 msg (n, pwrs) =
let res = if (null pwrs)
then (n, [])
else let msg1 = (show n) ++ " " ++ (show pwrs)
rem = n - (head pwrs)
in if ((head pwrs) <= n)
then traceReduce2 msg1 (rem, tail pwrs)
else traceReduce2 msg1 (n, tail pwrs)
in DT.trace msg res
测试我们的跟踪版本：
λ>
λ> traceReduce2 "TOP" (337, (powersOf2UpToN 337))
TOP
337 [256,128,64,32,16,8,4,2]
81 [128,64,32,16,8,4,2]
81 [64,32,16,8,4,2]
17 [32,16,8,4,2]
17 [16,8,4,2]
1 [8,4,2]
1 [4,2]
1 [2]
(1,[])
λ>
所以我们差不多完成了。在处理完2的所有幂之后，0或1的值保留为该对的左侧。我们可以继续编写我们的evenNat函数：
evenNat :: Integer -> Bool
evenNat n =
let (remainder, ys) = reduce2 (n, powersOf2UpToN n)
in
-- here, remainder is set to 0 if and only if n is even
...
剩下的应该很容易。