这是一个简单的函数,它接受一个列表和一个数字,并计算列表的长度是否大于该数字。
例如
compareLengthTo [1,2,3] 3 == EQ
compareLengthTo [1,2] 3 == LT
compareLengthTo [1,2,3,4] 3 == GT
compareLengthTo [1..] 3 == GT
注意它有两个属性:
- 它适用于无限列表。
- 它是尾递归的并且使用常量空间。
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
吗?
最佳答案
开始吧(注意:我只是更改了一个比较,这让它变得更懒惰):
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
关于algorithm - `foldr` 或其他高阶函数的一般性,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28207182/