Skip to main content

懒惰的自然数 Lazy natural numbers

我们介绍了懒惰的自然数，并提供了一个应用示例，以使某种算法更快。

激励性的例子 Motivating example​

如果列表 xs 很大，那么下面的程序就很慢。此外，如果列表 xs 是无限的，它将循环而不给出答案：

checkLengthBiggerThan :: [a] -> Int -> Bool
checkLengthBiggerThan xs n = length xs > n

Examples:

*Main> :set +s
*Main> checkLengthBiggerThan [1..10^6] 3
True
(0.04 secs, 72,067,432 bytes)
*Main> checkLengthBiggerThan [1..10^7] 3
True
(0.19 secs, 720,067,488 bytes)
*Main> checkLengthBiggerThan [1..10^8] 3
True
(1.47 secs, 7,200,067,600 bytes)
*Main> checkLengthBiggerThan [1..10^9] 3
True
(14.35 secs, 72,000,067,640 bytes)

我们可以通过以下方式使其更快，无论 xs 的长度如何，它最多需要 n 步。

checkLengthBiggerThan' :: [a] -> Int -> Bool
checkLengthBiggerThan' []     0 = False
checkLengthBiggerThan' xs     0 = True
checkLengthBiggerThan' []     n = False
checkLengthBiggerThan' (x:xs) n = checkLengthBiggerThan' xs (n-1)

我们正在忽略负数。

Example:

*Main> checkLengthBiggerThan' [1..10^9] 3
True
(0.01 secs, 68,408 bytes)

懒惰的自然数 Lazy natural numbers​

还有一种方法可以使上述算法变得快速，即用原算法中的懒惰自然数的类型 Nat 代替 Int 类型的使用。

data Nat = Zero | Succ Nat deriving (Eq,Ord)

我们的想法是，这代表自然数 0,1,2,3,...，如下所示

         Zero
         Succ Zero
         Succ (Succ Zero)
         Succ (Succ (Succ Zero))
         ...

我们可以在 Haskell 中定义为

one, two, three :: Nat
one   = Succ Zero
two   = Succ one
three = Succ two

此外，我们可以将一个非负整数转换成一个懒惰的自然数，如下所示：

toNat :: Int -> Nat
toNat 0 = Zero
toNat n = Succ (toNat (n-1))

但我们在 Nat 类型中也有无限大：

infty = Succ infty

这将永远计算下去，产生无限多的 Succ (Succ (Succ ... 的继承构造函数，但关键是，这种计算是懒惰的。

我们现在可以定义一个长度函数，如下所示：

length' :: [a] -> Nat
length' []     = Zero
length' (x:xs) = Succ (length' xs)

For example, we have that

  • length [0..] loops without giving any answer, but
  • length' [0..] = infty.

现在定义一个懒惰的比较算法，如下所示：

biggerThan :: Nat -> Nat -> Bool
Zero     `biggerThan` y        = False
(Succ x) `biggerThan` Zero     = True
(Succ x) `biggerThan` (Succ y) = x `biggerThan` y

关键是在第二个方程中，x 不需要被评估就能得到答案 True。比如说：

*Main> infty `biggerThan` three
True

这样一来，第一种算法就变得很快，而且也适用于无限的列表：

checkLengthBiggerThan'' :: [a] -> Int -> Bool
checkLengthBiggerThan'' xs n = (length' xs) `biggerThan` (toNat n)

For example:

*Main> checkLengthBiggerThan'' [1..10^9] 3
True
(0.02 secs, 69,032 bytes)

但实际上我们可以这样写，因为我们导出了Ord：

checkLengthBiggerThan''' :: [a] -> Int -> Bool
checkLengthBiggerThan''' xs n = length' xs > toNat n

而这也同样快，这意味着 Ord 的推导机制必须产生一个与我们类似的懒惰比较算法：

*Main> checkLengthBiggerThan''' [1..10^9] 3
True
(0.01 secs, 70,200 bytes)

问题是，使用懒惰的自然数使得自然算法变得快速，而对于整数来说，自然算法是缓慢的。此外，使用懒惰自然数的一个好处是，它使无限列表的长度得到很好的定义，因为有懒惰自然数 infty 可用。