[Haskell-cafe] State of Ignorance

[Albert Y. C. Lai]

Hans van Thiel wrote:
> toMyState :: String -> MyState String Int   
> toMyState x = MyStateC (repl1 x)
> 
> where the monad is defined as:
> 
> data MyState a b = MyStateC ([a] -> ([a], b))
> 
> instance Monad (MyState a) where
>    return x = MyStateC (\tb -> (tb, x))
>    (MyStateC st) >>= f =  
>        MyStateC (\tb -> let                       
>                           (newtb, y) = st tb
>                           (MyStateC trans) = f y 
>                         in trans newtb )
> 
> Now I understand this (barely) in the sense that >>= works through
> defining how f takes its values from st. So, f would be the function:
> toMystate and trans would be: (repl1 x). 
> But then y would have to be of type String, whereas the y in the tuple
> would have type Int, since it is generated by st. I just don't get it.

No, y has type String. In more detail: in order for
   foo >>= toMyState
to make sense, these must be the types:
   foo :: MyState String String
   st :: [String] -> ([String], String)
y is forced to have type String for the sake of toMyState.

> They work, but now I don't understand sequence, defined in the Prelude.
> From: a Tour of the Haskell Monad Functions
> http://members.chello.nl/hjgtuyl/tourdemonad.html
> 
> sequence :: Monad m => [m a] -> m [a]
> sequence = foldr mcons (return [])
>   where
>     mcons p q = p >>= \x -> q >>= \y -> return (x : y)
> 
> This has a different bind (>>=) from the one in the MyState monad, 
> yet is appears to perform all the state transformations. 

The >>= used by sequence is the same >>= in the MyState monad, since you 
instantiate m to MyState String. Therefore, sequence performs all the 
state transformations correctly, since >>= is correct.

A method of understanding a program is to reinvent it. Let us do that to 
sequence.

Preliminary: I have three actions:
   p = toMyState "house"
   b = toMyState "tree"
   c = toMyState "house"
I want to perform them in that order; moreover, each returns a number, 
and I want to collect all three numbers into a list, also in that order. 
If I may hardcode everything, I may write:

   do x <- p
      y0 <- b
      y1 <- c
      return [x,y0,y1]

But we always want to generalize. I do not want to hardcode p,b,c; I 
want to take them from a parameter, which can be a list of arbitrary 
length in general. To see how, I first rewrite my hardcoded version as:

   do x <- p
      y <- do {y0 <- b; y1 <- c; return [y0,y1]}
      return (x:y)

I have the middle line handle "the rest of the list", and if somehow it 
works correctly (later I will replace it by recursion), I just have to 
handle the first of the list before, and return the combined answer 
after. Now I use recursion in the middle, and introduce parameters:

mysequence (p:bc) = do x <- p
                        y <- mysequence bc
                        return (x:y)
mysequence [] = return []

Or in terms of >>= :

mysequence (p:bc) = p >>= \x -> mysequence bc >>= \y -> return (x:y)
mysequence [] = return []

This is now equivalent to the sequence code in the standard prelude.