我一直在学习优秀的CIS 194课程,但在第六次作业的第五部分遇到了困难。它涉及实现标尺函数而不进行任何除法测试。
我发现可以通过不断地将累加器与无限列表中的值交错来构建标尺函数。
正如预期的那样,我因为尝试从右侧折叠而遇到了stackoverflow错误。然而,我惊讶地发现同样的算法适用于普通的无限列表。
我错过了什么?为什么一个实现可行而另一个不行?
我发现可以通过不断地将累加器与无限列表中的值交错来构建标尺函数。
nats = [0,1,2,3,..]
[3]
[2,3,2]
[1,2,1,3,1,2,1]
[0,1,0,2,0,1,0,3,0,1,0,2,0]
然后我尝试将该算法实现到Stream
数据类型上,它是一个没有nil
的列表。
data Stream a = Cons a (Stream a)
streamToList :: Stream a -> [a]
streamToList (Cons x xs) = x : streamToList xs
instance Show a => Show (Stream a) where
show = show . take 20 . streamToList
streamFromSeed :: (a -> a) -> a -> Stream a
streamFromSeed f x = Cons x (streamFromSeed f (f x))
nats :: Stream Integer
nats = streamFromSeed succ 0
interleave x (Cons y ys) = Cons x (Cons y (interleave x ys))
foldStream f (Cons x xs) = f x (foldStream f xs)
ruler = foldStream interleave nats
正如预期的那样,我因为尝试从右侧折叠而遇到了stackoverflow错误。然而,我惊讶地发现同样的算法适用于普通的无限列表。
import Data.List
interleave x list = [x] ++ (intersperse x list) ++ [x]
ruler = take 20 (foldr interleave [] [0..])
我错过了什么?为什么一个实现可行而另一个不行?
foldr
并不是从右边折叠,而是从右边关联,即foldr f z [1 .. 3]
=1 `f` (2 `f` (3 `f` z))
=f 1 $ f 2 $ f 3 $ z
。如果f
在第二个参数上是惰性的,它可以处理无限流并逐步产生结果。同样,懒惰的foldl
(而不是严格的foldl'
)对于在其第一个参数上懒惰的函数也是可以的。问题在于使用了错误的严格性——将在参数1中严格的函数给予foldl
或在参数2中严格的函数给予foldr
——因此需要一直强制到流的末尾才能开始产生结果。对于无限流,没有这样的结尾。 - Jon Purdy