`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

有没有办法只compareLengthTo使用foldr？

请注意,这里有一个版本的compareLengthTo使用drop:

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

我想另一个问题是,那么,你可以实现drop的方面foldr？

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

这正是使用同一种技术,用于实现foldl在以下方面foldr.有一篇关于一般技术的经典文章叫做关于折叠的普遍性和表现力的教程.您还可以看到我在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