Nested States in Haskell

Question

I am trying to define a family of state machines with somewhat different kinds of states. In particular, the more "complex" state machines have states which are formed by combining the states of simpler state machines.

(This is similar to an object oriented setting where an object has several attributes which are also objects.)

Here is a simplified example of what I want to achieve.

data InnerState = MkInnerState { _innerVal :: Int }

data OuterState = MkOuterState { _outerTrigger :: Bool, _inner :: InnerState }

innerStateFoo :: Monad m => StateT InnerState m Int
innerStateFoo = do
  i <- _innerVal <$> get
  put $ MkInnerState (i + 1)
  return i

outerStateFoo :: Monad m =>  StateT OuterState m Int
outerStateFoo = do
  b <- _outerTrigger <$> get
  if b
    then
       undefined
       -- Here I want to "invoke" innerStateFoo
       -- which should work/mutate things
        -- "as expected" without
       -- having to know about the outerState it
       -- is wrapped in
    else
       return 666

More generally, I want a generalized framework where these nestings are more complex. Here is something I wish to know how to do.

class LegalState s

data StateLess

data StateWithTrigger where
  StateWithTrigger :: LegalState s => Bool -- if this trigger is `True`, I want to use
                                   -> s    -- this state machine
                                   -> StateWithTrigger

data CombinedState where
  CombinedState :: LegalState s => [s] -- Here is a list of state machines.
                                -> CombinedState -- The combinedstate state machine runs each of them

instance LegalState StateLess
instance LegalState StateWithTrigger
instance LegalState CombinedState

liftToTrigger :: Monad m, LegalState s => StateT s m o -> StateT StateWithTrigger m o
liftToCombine :: Monad m, LegalState s => [StateT s m o] -> StateT CombinedState m o

---

For context, this is what I want to achieve with this machinery:

I want to design these things called "Stream Transformers", which are basically stateful functions: They consume a token, mutate their internal state and output something. Specifically, I am interested in a class of Stream Transformers where the output is a Boolean value; we will call these "monitors".

Now, I am trying to design combinators for these objects. Some of them are:

• A pre combinator. Suppose that mon is a monitor. Then, pre mon is a monitor which always produces False after the first token is consumed and then mimicks the behaviour of mon as if the previous token is being inserted now. I would want to model the state of pre mon with StateWithTrigger in the example above since the new state is a boolean along with the original state.
• An and combinator. Suppose that m1 and m2 are monitors. Then, m1 `and` m2 is a monitor which feeds the token to m1, and then to m2, and then produces True if both of the answers were true. I would want to model the state of m1 `and` m2 with CombinedState in the example above since the state of both monitors must be maintained.

Wira

FYI, _innerVal <$> get is just gets _innerVal (as gets f == liftM f get, and liftM is just fmap specialized to monads). – Uropygium

Where are you getting a StateT InnerState m Int value in the first place in outerStateFoo? – Uropygium

@Uropygium in case the value b is true, I want to run the innerStateFoo – Wira

Are you comfortable with lens? This use case seems to be exactly what zoom is for. – Epiboly

@Epiboly I have seen some lenses but don't understand them very well. Maybe you can explain in an answer how to use zoom? – Wira

An observation: This entry does not contain a single question. – Antichrist

Answer 1

For your first question, as Carl mentioned, zoom from lens does exactly what you want. Your code with lenses could be written like this:

{-# LANGUAGE TemplateHaskell #-}

import Control.Lens
import Control.Monad.State.Lazy

newtype InnerState = MkInnerState { _innerVal :: Int }
  deriving (Eq, Ord, Read, Show)

data OuterState = MkOuterState
  { _outerTrigger :: Bool
  , _inner        :: InnerState
  } deriving (Eq, Ord, Read, Show)

makeLenses ''InnerState
makeLenses ''OuterState

innerStateFoo :: Monad m => StateT InnerState m Int
innerStateFoo = do
  i <- gets _innerVal
  put $ MkInnerState (i + 1)
  return i

outerStateFoo :: Monad m =>  StateT OuterState m Int
outerStateFoo = do
  b <- gets _outerTrigger
  if b
    then zoom inner $ innerStateFoo
    else pure 666

Edit: While we're at it, if you're already bringing in lens then innerStateFoo can be written like so:

innerStateFoo :: Monad m => StateT InnerState m Int
innerStateFoo = innerVal <<+= 1

Senary

Answer 2

For context, this is what I want to achieve with this machinery:

I want to design these things called "Stream Transformers", which are basically stateful functions: They consume a token, mutate their internal state and output something. Specifically, I am interested in a class of Stream Transformers where the output is a Boolean value; we will call these "monitors".

I think that what you want to achieve doesn't need very much machinery.

newtype StreamTransformer input output = StreamTransformer
  { runStreamTransformer :: input -> (output, StreamTransformer input output)
  }

type Monitor input = StreamTransformer input Bool

pre :: Monitor input -> Monitor input
pre st = StreamTransformer $ \i ->
  -- NB: the first output of the stream transformer vanishes.
  -- Is that OK? Maybe this representation doesn't fit the spec?
  let (_, st') = runStreamTransformer st i
  in  (False, st')

and :: Monitor input -> Monitor input -> Monitor input
and left right = StreamTransformer $ \i ->
  let (bleft,  mleft)  = runStreamTransformer left  i
      (bright, mright) = runStreamTransformer right i
  in  (bleft && bright, mleft `and` mright)

This StreamTransformer is not necessarily stateful, but admits stateful ones. You don't need to (and IMO should not! in most cases!!) reach for typeclasses in order to define these (or indeed ever! :) but that's another topic).

notStateful :: StreamTransformer input ()
notStateful = StreamTransformer $ \_ -> ((), notStateful)

stateful :: s -> (input -> s -> (output, s)) -> StreamTransformer input output
stateful s k = StreamTransformer $ \input ->
  let (output, s') = k input s
  in  (output, stateful s' k)

alternateBool :: Monitor anything
alternateBool = stateful True $ \_ s -> (s, not s)

Craniate

I'd just call it pure functional programming! But I know that's not the answer you're looking for :) StreamTransformer is in fact a "Mealy machine" hackage.haskell.org/package/machines-0.7/docs/… – Craniate

No, the first output vanishing isn't what I intended. I would like to delay the first output to be the second one. – Wira

And so on so that every output is delayed by one step? That can be done. – Craniate

very nice, thanks for posting! (sorry for commenting previously without heaving read the Q properly). I think the OP meant pre st = stateful (Nothing, st) k where k i (s,st) = let (o, st') = runStreamTransformer st i in ( maybe False id s , (Just o, st')). – Inveracity