使用`streamInterleave`实现标尺功能 [英] Implementing the ruler function using `streamInterleave`

问题描述

我正在做CIS 194的作业.问题是通过使用streamInterleave来实现标尺功能.代码看起来像

I am doing the homework of CIS 194. The problem is to implement the ruler function by using streamInterleave. The code looks like

data Stream a = Cons a (Stream a)

streamRepeat :: a -> Stream a
streamRepeat x = Cons x (streamRepeat x)

streamMap :: (a -> b) -> Stream a -> Stream b
streamMap f (Cons x xs) = Cons (f x) (streamMap f xs)

streamInterleave :: Stream a -> Stream a -> Stream a
streamInterleave (Cons x xs) ys = Cons x (streamInterleave ys xs)

ruler :: Stream Integer
ruler = streamInterleave (streamRepeat 0) (streamMap (+1) ruler)

我真的很困惑为什么可以像这样实现标尺.这会给我[0,1,0,1....]吗?

I am really confused why ruler can be implemented like this. Is this going to give me [0,1,0,1....]?

任何帮助将不胜感激.谢谢！！

Any help will be greatly appreciated. Thank you!!

推荐答案

首先，我们将这样表示Stream:

Firstly, we'll represent a Stream like this:

a1 a2 a3 a4 a5 ...

现在，让我们来分开ruler的定义:

Now, let's take the definition of ruler apart:

ruler :: Stream Integer
ruler = streamInterleave (streamRepeat 0) (streamMap (+1) ruler)

在Haskell中，重要的一点是懒惰.也就是说，在需要评估之前，不需要对事物进行评估.这一点很重要:这就是使此无限递归定义起作用的原因.那么我们如何理解呢?我们从streamRepeat 0位开始:

In Haskell, an important point is laziness; that is, stuff doesn't need to be evaluated until it needs to be. This is important here: it's what makes this infinitely recursive definition work. So how do we understand this? We'll start with the streamRepeat 0 bit:

0 0 0 0 0 0 0 0 0 ...

然后将其馈送到streamInterleave中，并与streamMap (+1) ruler(以x s表示)的流(尚不为人所知)交织:

Then this is fed into a streamInterleave, which interleave this the with (as yet unknown) stream from streamMap (+1) ruler (represented with xs):

0 x 0 x 0 x 0 x 0 x 0 x ...

现在，我们将开始填写这些x.我们已经知道ruler的每个第二个元素是0，所以streamMap (+1) ruler的每个第二个元素必须是1:

Now we'll start filling in those xs. We know already that every second element of ruler is 0, so every second element of streamMap (+1) ruler must be 1:

  1   x   1   x   1   x   1   x   1   x ... <--- the elements of (streamMap (+1) ruler)
0 1 0 x 0 1 0 x 0 1 0 x 0 1 0 x 0 1 0 x ... <--- the elements of ruler

现在我们知道每四个元素中的第二个元素(所以数字2,6,10,14,18，...)是1，因此streamMap (+1) ruler的对应元素必须是2 :

Now we know every second element out of each group of four (so numbers 2,6,10,14,18,...) is 1, so the corresponding elements of streamMap (+1) ruler must be 2:

  1   2   1   x   1   2   1   x   1   2 ... <--- the elements of (streamMap (+1) ruler)
0 1 0 2 0 1 0 x 0 1 0 2 0 1 0 x 0 1 0 2 ... <--- the elements of ruler

现在我们知道八组中的每四个元素(因此数字4,12,20，...)为2，因此streamMap (+1) ruler的对应元素必须为3:

Now we know that every fourth element out of each group of eight (so numbers 4,12,20,...) is 2 so the corresponding elements of streamMap (+1) ruler must be 3:

  1   2   1   3   1   2   1   x   1   2 ... <--- the elements of (streamMap (+1) ruler)
0 1 0 2 0 1 0 3 0 1 0 2 0 1 0 x 0 1 0 2 ... <--- the elements of ruler

我们可以通过替换每个n/2, 3n/2, 5n/2, ...编号的ruler值，像这样 ad infinitum 一样继续构建ruler.

And we can continue building ruler like this ad infinitum, by substituting back each n/2, 3n/2, 5n/2, ... numbered value of ruler.

这篇关于使用`streamInterleave`实现标尺功能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！