Search code examples
haskellstreamtransformer-model

Convert stream transformer function into Mealy automaton in Haskell

I work with streams:

data Stream a = Cons a (Stream a)

Particularly, stream transformer functions:

f :: Stream a -> Stream b

I would like to make a Mealy automaton out of such a function:

data Mealy a b = Mealy (a -> (b, Mealy a b))

Is there a way to write such a function?

toMealy :: (Stream a -> Stream b) -> Mealy a b

I can't find a way. Although the other way works easily:

toStreamTransformer :: Mealy a b -> Stream a -> Stream b

Maybe I'm missing something trivial?

Solution

  • This answer makes use of the Stream abstraction provided by the streaming package. This abstraction:

    • Is a monad transformer, so you can put any monad under it.
    • Has a return type separate from the elements produced by the stream. A value of this type is returned when the stream is exhausted.

    Imagine you have a function like:

    module Main where

import Streaming
import Streaming.Internal (Stream(Effect,Step,Return))
import Streaming.Prelude

transformation :: Monad m => Stream (Of Int) m r -> Stream (Of String) m r
transformation = undefined -- your code here

    transformation changes a stream of Int values into a stream of String values. It is polymorphic on the base monad, which means the transformation itself is pure. It is polymorphic on the return type r, which means that the transformation always exhausts the source stream.

    Now we write these auxiliary definitions:

    data Feed a = Input a | EOF

trickster :: Monad m => Stream (Of a) (Stream ((->) (Feed a)) m) ()        
trickster = do
  r <- Effect (Step (Return . Return)) -- request a `Feed a` value
  case r of
      Input a -> Step (a :> trickster)
      EOF     -> Return ()

    trickster is a bit strange. At the outer level, it is a stream that produces a values. But underneath, we have something like a Free (->) monad (here also implemented with Stream) that takes a values and emits them at the outer level.

    What happens if we apply trickster to transformation, and then merge the two Stream layers using the unseparate function?

    machine :: Stream (Sum (Of String) ((->) (Feed Int))) Identity ()         
machine = unseparate (transformation trickster)

    We can advance through machine using the inspect function 

    inspect :: (Functor f, Monad m) => Stream f m r -> m (Either r (f (Stream f m r)))

    Here's a scary type:

    ghci> :t runIdentity (inspect machine)
runIdentity (inspect machine)
  :: Either
       ()
       (Sum
          (Of String)
          ((->) (Feed Int))
          (Stream (Sum (Of String) ((->) (Feed Int))) Identity ()))

    It basically means that at a given step the machine either terminates (but the implementation of trickster ensures that it will never do that unless we pass EOF) or it produces a String, or requires us to enter an Int value.

    (We could have done without unseparate, but the process of peeling the two Stream layers would have been more confusing.)

    (Also, see the blog post Programmatic translation to iteratees from pull-based code by Paul Chiusano for the original idea behind this code.)