[Haskell-cafe] State of Ignorance
Albert Y. C. Lai
trebla at vex.net
Sun Mar 11 20:43:09 EDT 2007
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.
More information about the Haskell-Cafe
mailing list