algorithm - `foldr` 或其他高阶函数的一般性

Question

这是一个简单的函数，它接受一个列表和一个数字，并计算列表的长度是否大于该数字。

例如

compareLengthTo [1,2,3] 3 == EQ
compareLengthTo [1,2] 3 == LT
compareLengthTo [1,2,3,4] 3 == GT
compareLengthTo [1..] 3 == GT

注意它有两个属性:

1. 它适用于无限列表。
2. 它是尾递归的并且使用常量空间。

import Data.Ord

compareLengthTo :: [a] -> Int -> Ordering
compareLengthTo l n = f 0 l
  where
    f c [] = c `compare` n
    f c (l:ls) | c > n = GT
               | otherwise = f (c + 1) ls

有没有办法只使用 foldr 来编写 compareLengthTo？

请注意，这是使用 drop 的 compareLengthTo 版本:

compareLengthToDrop :: [a] -> Int -> Ordering
compareLengthToDrop l n = f (drop n (undefined:l))
  where
    f [] = LT
    f [_] = EQ
    f _ = GT

我猜另一个问题是，你能根据 foldr 实现 drop 吗？

Answer 1

开始吧(注意:我只是更改了一个比较，这让它变得更懒惰):

compareLengthTo :: [a] -> Int -> Ordering
compareLengthTo l n = foldr f (`compare` n) l 0
  where
    f l cont c | c >= n = GT
               | otherwise = cont $! c + 1

这使用与根据 foldr 实现 foldl 的技术完全相同。有一篇关于一般技术的经典文章叫做A tutorial on the universality and expressiveness of fold .您还可以看到我在 Haskell Wiki 上写的分步说明。 .

为了帮助您开始，请注意 foldr 在这里应用于 四个 个参数，而不是通常的三个。这是可行的，因为被折叠的函数接受三个参数，并且“基本情况”是一个函数，(`compare` n)。

编辑

如果你想像 J. Abrahamson 那样使用惰性 Peano 数字，你可以倒数而不是倒数。

compareLengthTo :: [a] -> Nat -> Ordering
compareLengthTo l n = foldr f final l n
  where
    f _ _ Zero = GT
    f _ cont (Succ p) = cont p

    final Zero = EQ
    final _ = LT