haskell - 休斯的斐波那契流

Question

我试图理解 John Hughes 著名的 "Generalising Arrows to Monads" 中的“流如箭头”部分。 .更准确地说，我有兴趣写下斐波那契流。
我稍微调整了休斯的定义:

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我们得到了一个类似无限列表的结构。
以下是我理解“斐波那契流”的两种方式:

一个非阻塞的无限流(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 th 斐波那契数并再次阻止。休斯的 Arrow interface 帮助我们以非常简洁的方式表达它:

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

然而，在 the paper I linked John Hughes 展示了另一种解决方案，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 的模式 - 我看不出他们怎么会搞砸这个过程)。

编辑:正如评论中所说，在 later edition of the paper bypass略有改变(我们使用那个)。版主b都是可以累积的s 和 d s(即有两个队列)，而 bypass来自 original paper仅累积 d s(即一个队列)。

编辑#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什么都行，那太 absurd 了。除了 (&&&)做 absurd 的事；因此专门用于Void ，它在道德上等同于以下内容(忽略 undefined 的存在，这在技术上可用于在 Haskell 中区分它们):

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

(&&&) 有一个更自然的定义。通过对流进行递归来避免该问题:如果两个参数从不做任何 Get ，那么结果永远不会有任何 Get任何一个。
据我所知，这个“更好”(&&&)无法使用 first 定义, (>>>)和 arr .
然而，这是有代价的:从箭头的图形解释的角度来看，它并不直观，因为它打破了这个等式(可以用图形绘制为“滑动”f &&&):

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

(&&&) 的任何定义你选择，它会混淆某人。

IMO 归结为 StreamProcessor 类型不能排除使用Get .即使输入类型是Void ，流仍然可以做一个空的Get .
pipes library 中的一种没有此类定义问题的更好类型的流处理器。 (称为 Proxy )。特别是，它与 SP 不同。因为它可以禁止使用Get ，并且提供了对真正的“生产者”(例如斐波那契流)的忠实编码。