问题描述
我正在研究 UPENN Haskell家庭作业6练习5,尝试定义统治者函数
I'm working on UPENN Haskell Homework 6 Exercise 5, trying to define a ruler function
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,...
其中流中的第n个元素(假设第一个元素对应于 n
= 1)是2的最大幂次
,该均分结果是 n .
where the nth element in the stream (assuming the first element corresponds to
n
= 1) is the largest power of 2
which evenly divides n
.
我只是想出了一个无需任何可分性测试即可构建的想法:
I just came up with an idea to build it without any divisibility testing:
data Stream x = Cons x (Stream x) deriving (Eq)
streamRepeat x = Cons x (streamRepeat x)
interleaveStreams (Cons x xs) (Cons y ys) =
Cons x (Cons y (interleaveStreams xs ys))
ruler =
interleaveStreams (streamRepeat 0)
(interleaveStreams (streamRepeat 1)
(interleaveStreams (streamRepeat 2)
(interleaveStreams (streamRepeat 3) (...))
其中的前20个元素
ruler =
interleaveStreams (streamRepeat 0)
(interleaveStreams (streamRepeat 1)
(interleaveStreams (streamRepeat 2)
(interleaveStreams (streamRepeat 3) (streamRepeat 4))))
是
[0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2]
很显然,我无法将其手动定义为无限,所以我定义了
infInterStream
来帮助这种无限递归定义:
Obviously I couldn't define it manually to infinite so I defined a
infInterStream
to help such infinite recursion definition:
infInterStream n = interleaveStreams (streamRepeat n) (infInterStream (n+1))
ruler = infInterStream 0
但是现在我在
ghci
中键入 ruler
时陷入困境,它可能陷入无限循环.
But now I get stuck when typing in
ruler
in ghci
, it probably falls into infinite loop.
不应该使用懒惰评估.我想知道为什么懒惰评估在这里失败.
It shouldn't be if lazy evaluation works. I want to know why lazy evaluation fails here.
用于观察
Stream
的帮助器功能:
Helper function to observe
Stream
:
streamToList (Cons x xs) = x : streamToList xs
instance Show a => Show (Stream a) where
show = show . take 20 . streamToList
推荐答案
您的交错功能太严格.以下作品:
Your interleaving function is too strict. The following works:
interleaveStreams (Cons x xs) ys = Cons x (interleaveStreams ys xs)
这也有效:
interleaveStreams (Cons x xs) ~(Cons y ys) =
Cons x (Cons y (interleaveStreams xs ys))
原始定义进入无限循环,因为
interleaveStreams
要求两个参数都必须为 Cons
形式. infInterStream n
评估两个流的交织,第一个可以立即评估为 Cons
,但是第二个也必须首先简化为 Cons
,因此我们递归调用 infInterStream(n + 1)
,它会无限期地自称ad.
The original definition goes into infinite loop because
interleaveStreams
demands that both arguments must be of Cons
forms. infInterStream n
evaluates to the the interleaving of two streams, and the first one can be immediately evaluated to Cons
, but the second one must also be reduced first to Cons
, so we recursively call infInterStream (n + 1)
, which keeps calling itself ad infinitum.
如果
interleaveStreams
可以返回 Con _ ,而不必首先强制第二个参数,则
infInterStream
也可以逐步生成结果.
If
interleaveStreams
can return a Cons a _
without first having to force the second argument, infInterStream
can also incrementally build the result.
这篇关于无法定义无限流的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!