无法定义无限流 [英] Fail to define an infinite stream

问题描述

我正在研究 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.

这篇关于无法定义无限流的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！