用于Vector.Stream的流转换器Monad [英] Stream transformer Monad for Vector.Stream

问题描述

<代码> Data.Vector.Stream 提供了一个很好的 Stream 实现，这非常有效，这要归功于对可熔性的关注(请参阅

Data.Vector.Stream provides an nice Stream implementation that is very efficient thanks to the focus on fusability (see this paper for more). Since vector-0.1 this Stream implementation changed slightly by moving the Step type into a monad. (Now, the implementation is located in Data.Vector.Fusion.Stream.Monadic.)

简而言之，这是 Stream 的定义:

In a nutshell, here's the definition of Stream:

data Step s a where
    Yield :: a -> s -> Step s a
    Skip  :: s -> Step s a
    Done  :: Step s a

data Stream a = forall s. Stream (s -> Step s a) s

步骤s 使用更新功能 s->封装状态 s 的一次迭代的三种可能的结果.步骤s .流要么是 Done ，要么跳过输出，或者产生输出.(上面的定义使用了GADT，但这并不相关.)

Step s a encapsulates the three possible results from one iteration of state s with update function s -> Step s a. The stream is either Done, or skips output, or yields output. (The definition above uses GADTs, but that's not relevant, here.)

此 Stream 的简单应用程序是:

empty :: Stream a
empty = Stream (const Done) ()

singleton :: a -> Stream a
singleton x = Stream step True where
    step True  = Yield x False
    step False = Done

fromList :: [a] -> Stream a
fromList zs = Stream step zs
where
    step (x:xs) = Yield x xs
    step []     = Done

严格的左折是这样的:

foldl'S :: (a -> b -> a) -> a -> Stream b -> a
foldl'S f a0 (Stream step s) = go a0 s where
    go a s = a `seq`
                case step s of
                    Yield b s' -> go (f a b) s'
                    Skip    s' -> go a       s'
                    Done       -> a

并提供了通常的类似于列表的函数 lengthS = foldl'S(\ n _-> n + 1)0 ，依此类推.这当然不如

and that gives the usual list-like functions lengthS = foldl'S (\n _ -> n+1) 0, etc. This certainly isn't as elegant as Conduit or Pipes, but it's simple and fast. So far so good.

现在，让我们尝试将低级"流聚合到更高级的流中.例如，如果您有位流 Stream Bool ，则可能需要使用一些聪明的编解码器对位进行解码，以产生 Stream Int .当然，总是有可能建立一个新的步进函数 s->.从 step 函数提取的给定 Stream步骤s 的step s b .重复应用 step :: s-> step sa 函数会导致... 级联的尴尬情况(步骤s)，可处理三种可能性 Done， Skip ， Yield ，一遍又一遍.理想情况下， aggregate 应该像这样:

Now, let's try to aggregate 'low-level' streams to more high-level ones. For example, if you have a bitstream Stream Bool you may want to decode the bits to yield a Stream Int by using some clever codec. Of course it's always possible to build up a new step function s -> Step s b from the step function extracted of a given Stream step s. Repeated applications of the step :: s->Step s a function result in awkward case (step s) of ... cascades that handle the three possibilities Done, Skip, Yield, over and over again. Ideally, the aggregate should like this:

aggregate :: Stream a -> M?? -> Stream b
newStream = aggregate oldStream $ do
    a1 <- get    -- a1 :: a
    if a1 == True then doSomething
    else do
        a2 <- get
        -- etc.

要定义的 M ?? 是单子.让我们尝试类型 Appl s :

The M?? is some monad, to be defined. Let's try a type Appl s a:

newtype Appl s a = Appl ((s->Step s a) -> s -> Step s a)

它被称为 Appl ，因为它具有功能应用程序的签名.monad实例非常简单:

It's called Appl because it has the signature of a function application. The monad instance is quite straightforward:

instance Monad (Appl s) where
    return a = Appl (\_ s -> Yield a s)
    (Appl ap) >>= f = Appl (\step s ->
        case (ap step s) of
            Done -> Done
            Skip s' -> untilNotSkip step s'
            Yield a' s' -> ap' step s' where Appl ap' = f a'

其中 untilNotSkip :::(s->步骤s a)->s->步骤sa 只是重复(嵌套)应用 step ::(s-> Step sa)，直到 Done 或 Yield 返回.

where untilNotSkip :: (s->Step s a) -> s -> Step s a is just repeated (nested) application of a step :: (s->Step s a) until a Done or a Yield is returned.

get 功能只是普通功能应用程序

The get function is just normal function application

get :: Appl s a
get = Appl(\step s -> step s)

为了解决问题，需要完成 Functor 和 Applicative ，这是一个问题:无法创建 Appl 函子签名是

To tie things up, Functor and Applicative need to be done, and here comes the problem: Appl s can't be made a functor. The signature is

fmap :: (a->b) -> Appl s a -> Appl s b

，这只是不起作用，因为为了创建功能(s->步骤s b)->s->功能(步骤s a>步骤s a)->中的步骤s b).s->步骤s a)，我需要一个 b-> a .我可以在 a-&b; b 上拉回 Appl sb ，但是我不能推进 Appl sa -即我可以具有逆变函子，但没有函子.那真是怪了.流是很自然的comonads ，但我看不到连接. Appl 的目的是将步进函数 s-> Step sa 转换为另一个 s-> Step sb .

and that just doesn't work because in order to make a function (s->Step s b) -> s -> Step s b) from a function (s->Step s a) -> s -> Step s a) I'd need a b->a. I can pull back an Appl s b over an a->b, but I can't push forward an Appl s a - i.e. I can have a contravariant functor but not a functor. That's weird. Streams are quite naturally comonads, but I don't see the connection. the purpose of Appl is to turn a step function s->Step s a into another one s->Step s b.

这里有些错误， Appl 不是正确的" M ?? ".有人可以帮忙吗?

Something is very wrong here, Appl isn't the right "M??". Can anyone help out?

更新

夏丽瑶指出，类型应为

data Walk a b = forall s. Walk ((s->Step s a) -> s -> Step s b)

Functor，Applicative和Monad实例为

And the Functor, Applicative and Monad instances would be

instance Functor (Step s) where
    fmap f Done        = Done
    fmap f (Skip s)    = Skip s
    fmap f (Yield a s) = Yield (f a) s

instance Functor (Walk a) where
    fmap f (Walk t) = Walk ( \step s -> fmap f (t step s) )

-- default Applicative given a monad instance
ap :: (Monad m) => m (a -> b) -> m a -> m b
ap mf m = do
    f <- mf
    x <- m
    return (f x)

untilNotSkip :: (s->Step s a) -> s -> Step s a
untilNotSkip step s = case step s of
    Done        -> Done
    Skip s'     -> untilNotSkip step s'
    Yield a' s' -> Yield a' s'

instance Monad (Walk a) where
    return a = Walk (\_ s -> Yield a s)
    Walk t >>= f =
        Walk (\step s -> case t (untilNotSkip step) s of
            Done        -> Done
            Skip _      -> error "Internal error."
            Yield b' s' -> case f b' of Walk t' -> t' step s'   -- bad
    )

instance Applicative (Walk a) where
    pure = return
    (<*>) = ap

但是，类型检查器不允许此monad实例.在>> = 的定义中， Walk(\ step s-> ... >>'s 在 Yield b's'-> ... 中，但必须相同，这里的基本问题是(>> =):: Walk ab->(b-> Walk ac)-> Walk ac 具有两个独立的全量化状态 s ，一个在第一个参数中，另一个在是由 b-> Walk ac 返回的.实际上，这是(滥用符号)(forall s.Walk s a b)->(全部s'.b->步行s'a'c)->(forall s''.walk s''a c)，这在概念上和类型检查器上都没有意义.所有三个 s ， s'， s''必须是同一类型.

The type checker won't allow this monad instance, however. In the definition of >>= the s in Walk (\step s -> ... is different from the s' in Yield b' s' -> ..., but it must be the same. The fundamental problem here is that (>>=) :: Walk a b -> (b->Walk a c) -> Walk a c has two independently all-quantified states s, one in the first argument, and another one that is returned by b->Walk a c. Effectively this is (with abuse of notation) (forall s. Walk s a b) -> (forall s'. b->Walk s' a' c) -> (forall s''. Walk s'' a c), which doesn't make sense, neither conceptually nor for the type checker. All three s, s', s'' must be the same type.

一种变体，其中 Walk 不能在 s 上全部量化:

A variation where Walk is not all-quantified over s:

data Walk s a b = Walk ((s->Step s a) -> s -> Step s b)

允许正确定义绑定，但是 aggregate 无效:

allows correct definition of bind, but then aggregate won't work:

-- does not compile
aggregate :: Stream a -> Walk s a b -> Stream b
aggregate (Stream step s) (M t) = Stream (t step) s

同样，流状态 s 必须始终相同.一种解决方法是引入 data PreStream s = PreStream(s-> Step s a)s ，但这不允许 aggregate :: Stream a->.??->要么流b .

Again, the stream state s must always be the same. One way out of this would be to introduce a data PreStream s a = PreStream (s -> Step s a) s, but that doesn't allow an aggregate :: Stream a -> ?? -> Stream b either.

源代码位于 github 上.

推荐答案

让我们再次看一下 Appl ，因为它看起来几乎是正确的.

Let's look at Appl again, because it seems almost right.

newtype Appl s a = Appl ((s->Step s a) -> s -> Step s a)

该想法是通过将低级"阶跃函数转换为高阶"阶跃函数来定义流转换器.在这种情况下，这两个步骤函数不应​​具有相同的输出.例如，如果将位转换为字节，则需要(s-> Step s Bit)->.s->步骤s字节.

The idea is to define a stream transducer by converting a "low-level" step function to a "high-level" one. With that view, those two step functions shouldn't have the same output. For example, if we're transducing bits to bytes, we want (s -> Step s Bit) -> s -> Step s Byte.

因此，更好的类型将是

newtype Walk s b a = Walk ((s -> Step s b) -> s -> Step s a)
-- A walk is many steps.

此外，由于 Stream 通过 s 定量地存在，因此您需要在某些时候对 s 进行通用量化才能使用步行，因此您最好将其放入类型定义中.

Furthermore, since Stream quantifies existentially over s, you'll need some universal quantification over s at some point to use Walk, so you might as well put it in the type definition.

newtype Walk b a = Walk (forall s. (s -> Step s b) -> s -> Step s a)

这篇关于用于Vector.Stream的流转换器Monad的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！