休斯的斐波那契流

Question

我试图理解约翰休斯著名的“将箭头概括为单子”中的“流作为箭头”部分。更准确地说，我有兴趣写下斐波那契流。

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

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

首先，我将流处理器视为可能阻塞（等待输入）的列表。那是：

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

因此，如果我们删除 ，Get我们会得到一个类似列表的结构。如果我们也删除，Halt我们会得到一个类似无限列表的结构。

以下是我理解“斐波那契数列”的两种方式：

• 一个非阻塞的无限流（类似无限列表）：

  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第 Fibonacci 数并再次阻塞。Hughes 的Arrow界面帮助我们以一种非常简洁的方式表达它：

  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 !!)
  

然而，在我链接的论文中，约翰休斯展示了另一种解决方案，Arrow他的方法是：

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）：

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

所以，这是我们得到的：

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

如果我们检查模式，我们会看到它阻塞（即我们偶然发现了Get）。

我不知道是否应该这样。如果这是我们想要的，为什么？如果不是，问题是什么？我检查并重新检查了我编写的代码，它与 Hughes 文章中的定义非常匹配（好吧，我不得不添加id和模式Halt- 我看不出他们是如何把过程搞砸的）。

---

编辑：正如评论中所说，在论文的后期版本中 bypass略有更改（我们使用那个）。它能够积累都扣bS和dS（即有两个队列），而bypass从原来的纸积累只是dS（即一个队列）。

---

编辑#2：我只是想写下一个函数，它会从 中弹出斐波那契数列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]

Answer 1

问题出在纸张上。到底责任在哪里，很大程度上取决于主观解释的问题。我认为这是论文中一个被忽视的错误，因为该类型StreamProcessor并不像看起来那么直观。

首先关注fibsHughes流的具体示例，它确实包含Get，但它们是常量函数。您必须提供一些参数才能访问流的其余部分。在某种程度上，“真实”类型fibsHughes是SP () b，而您可能直观地想要的是SP Void b编码不存在Get（这不太适合这种方式，这就是问题的根源），并且“喂养”它的输入是如何从一个到另一个：

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操作才能生成对的第二个组件作为输出：

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

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

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

如果您想编写预期类型的​​内容，这就是您需要做的事情，但这可能不是一件自然的事情。

定义之后first就会导致定义和使用(&&&)运算符，这具有不直观的语义。要了解为什么它不直观，请专门(&&&)使用Void流输入类型：

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

任何看到这一点的人都会认为，当然，结果一定是一个制片人，这从来都不Get是什么，这是荒谬的。但那(&&&)是荒谬的事情；因此专门化为Void，它在道德上等价于以下内容（忽略它的存在，undefined技术上可以用来在 Haskell 中区分它们）：

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

流上的递归有一个更自然的定义(&&&)，可以避免这个问题：如果两个参数从不执行任何操作Get，那么结果也从不执行任何操作Get。

据我所知，这个“更好”(&&&)不能用first,(>>>)和 来定义arr。

然而，它是有代价的：从箭头的图形解释的角度来看，它并不直观，因为它打破了这个方程（可以用图形方式将其绘制为“滑出” f）&&&：

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

无论你选择哪个定义(&&&)，它都会让某人感到困惑。

IMO 归结为StreamProcessor不能排除使用Get. 即使输入类型是Void，流仍然可以执行 vacuum Get。

一种没有此类定义问题的更好类型的流处理器是来自管道库的流处理器（称为Proxy）。特别是，它不同于 ，SP因为它可以禁止使用Get，并且它提供了真正“生产者”的忠实编码，例如斐波那契流。