What are good wrappers to transfer state change in haskell?

Question

I am trying to implement a simple FRP backend, for my own interest.

I decided to use pure functions: so, no IO in the core. The implementation is based on signal transformer.

I already have tried two ways:

newtype SF a b = SF { listen :: [a] -> [b] }

https://gist.github.com/Heimdell/9675964#file-streamer-hs-L1

and

newtype SF a b = SF { run :: a -> (b, SF a b) }

https://gist.github.com/Heimdell/9675964#file-behaviour-hs-L1 (misnamed, sorry)

Both ways make possible to make a fold/integrate :: (a -> b -> b) -> b -> SF a b combinator for signal integration.

Both ways have a problem: Seems to be impossible to make a valid ArrowApply/Monad instance.

• Stream-way: we have a list of pairs (arrow, x) - or, unziped, the pair of lists (arrows, xs).

  • If we will map head to the result of zipWith ($) 'em, we will loose the carried-along arrow mutation.
  • if we make head arrows listen xs, we will freeze the state of first arrow taken.

• Explicit state-way:

  instance ArrowApply Behaviour where
      app =
          Behaviour $ \(bf, a) ->
              let (bf1, c) = bf `runBehaviour` a
  
              in (app, c)
  

  Here we need to somehow validly inject bf1 into app returned, which is impossible (and actually injecting by (const bf1 *** id) produces invalid behaviour analoguous to the second one from other implementation.

Is there a possible way to make a SF which allows ArrowApply instance?

P.S.: The stream-way has a memory leak in the ArrowChoice, when a branch sits unused for a long time. For now, I cannot fix that. Is it ever possible to make a no-leak version of it?

P.P.S: If one need time, he could zip it with input.

Answer 1

I can't find any possible instance that doesn't simply discard the state of the inner container. This isn't surprising, since the return from the pure function bound to the data should return the same thing each time the input is called, regardless of if it has been called before, which you hint at in your comments.

By itself

The only Monad instances I can come up with both discard the subsequent states for the inner container.

instance Monad (SF e) where
    return a = SF . const $ (a, return a)
    (>>=) sa f = SF go
        where
            go e = 
                let
                    (a, sa') = run sa e
                    sb = f a
                    (b, _) = run sb e
                in
                    (b, sa' >>= f)

or

join :: SF e (SF e a) -> SF e a
join ssa = SF go
    where
        go e =
            let
                (sa, ssa') = run ssa e
                (a, _) = run sa e
            in
                (a, join ssa')

These can be expressed more succinctly using the Monad instance for functions

instance Monad (SF e) where
    return a = SF . const $ (a, return a)
    (>>=) sa f = SF {
        run =
            do
                (a, sa') <- run sa
                (b, _) <- run (f a)
                return (b, sa' >>= f)
    }

We can look elsewhere for something a little different.

Function Monad Instance

Your newtype SF e a = SF { run :: e -> (a, SF e a) } is very close to a function from e to a. For the Monad instance for functions the only sensible >>= is to pass the argument to both the inner and outer functions. This is what we've already come up with. Let's see if we can come up with something else.

StateT

Your code is somewhat similar to the StateT monad transformer applied to the Monad instance for functions. Unfortunantly, this doesn't yield what we are looking for.

Consider the following (the StateT monad transformer):

newtype StateT s m a = StateT { runStateT :: s -> m (a, s)}

Applied to the type ((->) e) of a function that takes an argument `e.

StateT s ((->) e) a has the single constructor StateT { runStateT :: s -> e -> (a, s) }.

This differs from your type in that an initial state must be provided, and the state is tracked explicitly instead of already wrapped up in the returned next value. Let's see what the Monad instance for this would be. StateT's Monad instance is

instance (Monad m) => Monad (StateT s m) where
    return a = state $ \s -> (a, s)
    m >>= k  = StateT $ \s -> do
        ~(a, s') <- runStateT m s
        runStateT (k a) s'

state f = StateT (return . f)

Combined with an instance for (->) e

instance Monad ((->) e) where
    return = const
    (>>=) x y z = y (x z) z

We'd get the following, where the do dumps the work off onto the instance for ((->) e)

instance Monad (StateT s ((->) e) where
    return a = StateT (const . (\s -> (a, s)))
    m >>= k  = StateT $ \s e ->
        let (a, s`) = runStateT m s e
        in runStateT (k a) s` e

This looks quite different. We aren't losing the history of any state. What's happening here is that the state for the inner container is being passed to it from the outer container, and the two containers must have the same type for the state for this to work. This isn't what we want at all.

Something New

What happens if we try to make something like StateT from your type? We'd like to be able to pass in the type (->) e and get a structure like yours. We'll make something called SFT m a such that SFT ((-> e) a has the same structure as SF e a.

newtype SF  e a = SF  { run   :: e -> (a, SF  e a)
newtype SFT m a = SFT { unSFT :: m    (a, SFT m a) }

We can substiture a type made by applying SFT to (->) e) for SF applied to e

SF        e  a -- is replaced by
SFT ((->) e) a

This has a single constructor

SF  { run   :: e -> (a, SF        e  a) }
SFT { unSFT :: e -> (a, SFT ((->) e) a) }

This provides no new insight, the only Monad instance I can think of for it is almost identical to the original one.

instance Monad m => Monad (SFT m) where
    return a = SFT . return $ (a, return a)
    (>>=) sa f = SFT {
        unSFT =
            do
                (a, sa') <- unSFT sa
                (b, _) <- unSFT (f a)
                return (b, sa' >>= f)
    }