休斯的斐波那契流 [英] Hughes' Fibonacci stream

问题描述

我试图理解箭头流"约翰休斯着名的将箭头推广到Monads" 中的更准确地说，我有兴趣写下斐波那契流.

I am trying to understand the "Streams as arrows" section in John Hughes' famous "Generalising Arrows to Monads". To be more precise, I am interested in writing down the Fibonacci stream.

我稍微调整了休斯的定义:

I tweaked Hughes' definition a bit:

data StreamProcessor a b = Get (a -> StreamProcessor a b) | 
                           Put b (StreamProcessor a b) |
                           Halt
put = Put
get = Get

首先，我将流处理器视为可能会阻塞(等待输入)的列表.那就是:

First of all, I treat stream processors as lists which may block (waiting for input). That is:

• Put :: b->StreamProcessor a b->StreamProcessor a b 匹配(:) :: a->[a]->[a] ;
• Halt :: StreamProcessor a b 匹配 [] :: [a] ;
• Get ::(a-> StreamProcessor a b)->StreamProcessor a b 帮助我们阻止流并等待输入.

• Put :: b -> StreamProcessor a b -> StreamProcessor a b matches (:) :: a -> [a] -> [a];
• Halt :: StreamProcessor a b matches [] :: [a];
• Get :: (a -> StreamProcessor a b) -> StreamProcessor a b helps us block the stream and wait for input.

因此，如果我们删除 Get ，我们将得到一个类似列表的结构.如果我们还放弃 Halt ，我们将获得一个类似于无限列表的结构.

Therefore, if we drop the Get we get a list-like structure. If we also drop Halt we get an infinite-list-like structure.

以下是我理解斐波那契流"的两种方式:

Here are two ways I would understand "a stream of Fibonaccis":

• 无阻塞的无限流(类似无限列表):

• a non-blocked infinite stream (infinite-list-like):

zipNonBlockedStreamsWith :: (a -> b -> c) 
                            -> StreamProcessor () a 
                            -> StreamProcessor () b
                            -> StreamProcessor () c
zipNonBlockedStreamsWith f (Put x sp) (Put y sp') 
 = Put (f x y) (zipNonBlockedStreamsWith f sp sp')
zipNonBlockedStreamsWith f Halt       sp          = Halt  
zipNonBlockedStreamsWith f sp         Halt        = Halt

fibs :: StreamProcessor () Int
fibs = 
 put 0 (put 1 $ zipNonBlockedStreamsWith (+) fibs (tailNonBlockedStream fibs))

-- matches a well-known definition of an infinite Fibonacci list.
fibsList :: [Int]
fibsList = 0 : 1 : (zipWith (+) fibsList (tail fibsList))

-- with the 'fibsList', we can use folds to do the same thing.
putStream :: [b] -> StreamProcessor a b -> StreamProcessor a b
putStream bs sp = foldr Put sp bs

fibs' :: StreamProcessor () Int
fibs' = putStream fibsList Halt

阻塞的流等待 n ，输出第 n 个斐波那契数，然后再次阻塞.休斯的 Arrow 界面可帮助我们以一种非常简洁的方式表达它:

A blocked stream waits for n, outputs the nth Fibonacci number and blocks again. Hughes' Arrow interface helps us express it in a quite concise way:

instance Category StreamProcessor where
  ...

instance Arrow StreamProcessor where
  arr f = Get $ \ a -> Put (f a) (arr f)
  ...

fibsList :: [Int]
fibsList = 0 : 1 : (zipWith (+) fibsList (tail fibsList))

blockedFibs :: StreamProcessor Int Int
blockedFibs = arr (fibsList !!)

但是，在我链接的论文 中，约翰·休斯(John Hughes)提出了另一种解决方案，箭头通过以下方式进行操作:

Yet, in the paper I linked John Hughes shows another solution, Arrowing his way through:

instance Category StreamProcessor where
  id = Get (\ x -> Put x id)
  
  Put c bc . ab = Put c (bc . ab)
  Get bbc . Put b ab = (bbc b) . ab
  Get bbc . Get aab = Get $ \ a -> (Get bbc) . (aab a)
  Get bbc . Halt = Halt
  Halt . ab = Halt

bypass :: [b] -> [d] -> StreamProcessor b c -> StreamProcessor (b, d) (c, d)
bypass [] ds (Get f)          = Get $ \ ~(b, d) -> bypass [] (ds ++ [d]) (f b)
bypass (b : bs) [] (Get f)    = bypass bs [] (f b)
bypass [] (d : ds) (Put c sp) = Put (c, d) $ bypass [] ds sp
bypass bs [] (Put c sp) =      
  Get $ \ ~(b, d) -> Put (c, d) (bypass (bs ++ [b]) [] sp)
bypass bs ds Halt             = Halt

instance Arrow StreamProcessor where
  arr f = Get $ \ a -> Put (f a) (arr f)
  first = bypass [] []

liftArr2 :: Arrow k => (a -> b -> c) -> k r a -> k r b -> k r c
liftArr2 f a b = a &&& b >>^ uncurry f

fibsHughes = let 
              fibsHughes' = put 1 (liftArr2 (+) fibsHughes fibsHughes')
             in put 0 fibsHughes'

但是它不能按我期望的方式工作.以下函数将帮助我们从流中获取值，直到它阻塞或停止为止(使用 Data.List.unfoldr ):

But it does not work the way I expect. The following function would help us take the values from the stream until it blocks or halts (using Data.List.unfoldr):

popToTheBlockOrHalt :: StreamProcessor a b -> [b]
popToTheBlockOrHalt = let
                         getOutput (Put x sp) = Just (x, sp)
                         getOutput getOrHalt  = Nothing
                      in unfoldr getOutput

所以，这就是我们得到的:

So, here is what we get:

GHCi> popToTheBlockOrHalt fibsHughes
[0, 1]
GHCi> :t fibsHughes
fibsHughes :: StreamProcessor a Integer

如果我们检查模式，就会发现它阻塞了(也就是说，我们偶然发现了 Get ).

If we check the patterns, we would see that it blocks (that is we stumble into Get).

我不知道是否应该这样.如果这是我们想要的，为什么?如果没有，那是什么问题?我检查并重新检查了我编写的代码，它几乎与休斯的文章中的定义匹配(嗯，我必须添加 id 和 Halt 的模式-我看不到如何他们可能搞砸了整个过程).

I cannot tell whether it should be that way. If it is what we want, why? If not, what is the problem? I checked and rechecked the code I wrote and it pretty much matches the definitions in Hughes' article (well, I had to add id and patterns for Halt - I cannot see how they could have messed the process up).

如评论中所述，在原始文件仅累积 d s(即队列).

As it is said in the comments, in the later edition of the paper bypass was slightly changed (we use that one). It is able to accumulate both withheld bs and ds (that is has two queues), whereas the bypass from the original paper accumulates just ds (that is one queue).

编辑#2:我只想写下一个函数，该函数将从 fibsHughes 中弹出斐波那契数:

Edit #2: I just wanted to write down a function which would pop the Fibonacci numbers from the fibsHughes:

popToTheHaltThroughImproperBlocks :: StreamProcessor () b -> [b]
popToTheHaltThroughImproperBlocks = let
                                       getOutput (Put x sp) = Just (x, sp)
                                       getOutput (Get c)    = getOutput $ c ()
                                       getOutput Halt       = Nothing
                                    in unfoldr getOutput

然后我们开始:

GHCi> (take 10 . popToTheHaltThroughImproperBlocks) fibsHughes 
[0,1,1,2,3,5,8,13,21,34]

推荐答案

问题出在论文上.究竟应归咎于哪里主要是主观解释的问题.由于类型 StreamProcessor 不够直观，我认为这是本文中一个被忽略的错误.

The issue is with the paper. Where exactly the blame lies is largely a matter of subjective interpretation. I think it's an overlooked bug in the paper due to the type StreamProcessor not being as intuitive as it may seem.

首先集中讨论 fibsHughes 流的具体示例，它确实包含 Get ，但它们是常量函数.您必须提供一些参数才能访问流的其余部分.在某种程度上，真实"是指fibsHughes 的类型是 SP()b ，而您直观上想要的是 SP Void b 来编码缺少 Get (以这种方式行不通，这就是问题的根源)，然后喂"它的输入就是您如何从一个方向到达另一个方向:

To first focus on the concrete example of the fibsHughes stream, it indeed contains Get, but they are constant functions. You must feed some arguments to access the rest of the stream. In a way, the "true" type of fibsHughes is SP () b whereas what you might intuitively want is SP Void b to encode the absence of Get (which doesn't quite work that way, and that's kinda the source of the problem), and "feeding" it input is how you get from one to the other:

type SP = StreamProcessor

feed :: SP () b -> SP Void b
feed p = produceForever () >>> p

produceForever :: b -> SP Void b
produceForever b = Put b (produceForever b)

fibsHughes :: SP Void b
fibsHughes = feed (... {- rest of the definition -})

---

现在要了解如何进入这种情况，我们必须回到 first 的定义.我的观点是，首先要对流进行定义是一个有问题的操作，因为它必须引入 Get 动作才能生成对中的第二个分量作为输出:

---

Now to see how we got into this situation, we have to go back to the definition of first. My opinion is that it is a questionable operation on streams to define in the first place, because it has to introduce Get actions to be able to produce the second component of the pairs as output:

first ::: SP a b -> SP (a, c) (b, c)

有问题的部分是 bypass 的定义中的以下分支，该分支引入了 Get ，然后能够进行 Put :

The problematic part is the following branch in the definition of bypass, which introduces the Get to then be able to Put:

bypass bs [] (Put c sp) =      
  Get $ \ ~(b, d) -> Put (c, d) (bypass (bs ++ [b]) [] sp)

如果要编写期望类型的东西，这是您需要做的，但这无疑不是一件自然的事情.

It is what you need to do if you want to write something of the expected type, but it is arguably not a natural thing to do.

首先定义 是导致定义和使用具有非直观语义的(&&&)运算符的原因.要了解其不直观的原因，请以 Void 作为流输入类型来专门化(&&&):

Having defined first is what leads to defining and using the (&&&) operator, which has unintuitive semantics. To see why it's unintuitive, specialize (&&&) with Void as the stream input type:

(&&&) :: SP Void b -> SP Void c -> SP Void (b, c)

任何看过这个的人都会认为，结果当然必须是生产者，而生产者永远不会获取任何东西，这是荒谬的.除了(&&&)做荒唐的事情；因此专门用于 Void ，从道德上讲等效于以下内容(忽略了 undefined 的存在，该技术可以在Haskell中将它们区分开):

Anyone who looks at this would think that, of course, the result must be a producer, which never Gets anything, that would be absurd. Except that (&&&) does the absurd thing; thus specialized to Void, it is morally equivalent to the following (ignoring the existence of undefined which can technically be used to tell them apart in Haskell):

_ &&& _ = Get (absurd :: Void -> SP a c)

---

通过对流进行递归可以更自然地定义(&&&)，从而避免了该问题:如果两个参数从不执行任何 Get ，那么结果也不会执行任何 Get .

---

There is a more natural definition of (&&&) by recursion on streams which avoids that issue: if the two arguments never do any Get, then the result never does any Get either.

据我所知，这种更好"的含义是(&&)不能使用 first ，(>>>)和 arr .

As far as I can tell, this "better" (&&&) cannot be defined using first, (>>>) and arr.

但是，这是有代价的:从箭头的图形解释的角度来看，它是不直观的，因为它打破了这个等式(可以用滑动" f 的图形表示超出&& ):

However, it comes at cost: it is not intuitive from the point of view of a graphical interpretation of arrows, because it breaks this equation (which can be drawn graphically as "sliding" f out of &&&):

f &&& g   =   (id &&& g) >>> first f

您选择的(&&&)的定义，都会使某人感到困惑.

Whichever definition of (&&&) you choose, it is going to confuse someone.

IMO，它归结为 StreamProcessor 类型，无法排除使用 Get 的情况.即使输入类型是 Void ，流仍然可以做空虚的 Get .

IMO it comes down to the type StreamProcessor not being able to rule out the use of Get. Even if the input type is Void, a stream can still do a vacuous Get.

一种没有此类定义问题的更好类型的流处理器是 pipes库中的一种.(称为 Proxy ).特别是，它与 SP 不同，因为它可以禁止使用 Get ，并且可以对真实的生产者"提供忠实的编码.例如斐波那契流.

A better type of stream processor without such definitional issues is the one from the pipes library (called Proxy). In particular, it differs from SP because it can forbid the use of Get, and that provides a faithful encoding of true "producers" such as the Fibonacci stream.

这篇关于休斯的斐波那契流的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！