Hello All, I have the following functions, based on Thompson's CFP example (also in Control.Monad.State documentation) of using a state monad on a tree. My functions (on a list) work, but I don't understand why. Main> getInds ["house","tree","cat","house","cat","dog","tree"] [0,1,2,0,2,3,1] Main> getTb ["house","tree","cat","house","cat","dog","tree"] ["house","tree","cat","dog"] This, from CFP, is clear enough. repl1 :: String -> [String] -> ([String], Int) repl1 x tb | elem x tb = (tb, fromJust (elemIndex x tb)) | otherwise = (tb ++ [x], length tb) then, turn this into a function to a state monad type: 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. Next the book explains how to extract values from a state and again that's pretty clear: extr1 :: MyState a b -> b extr1 (MyStateC st) = snd (st []) extr2 :: MyState a b -> [a] extr2 (MyStateC st) = fst (st []) I have a list instead of a tree, so I tried: strtoMS :: [String] -> [MyState String Int] strtoMS ls = map toMyState ls and the final functions are: getInds :: [String] -> [Int] getInds = extr1 . sequence . strtoMS getTb :: [String] -> [String] getTb = extr2 . sequence . strtoMS 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 documentation says: "sequence xs evaluates all monadic values in the list xs, from left to right, and returns a list of the "contents" of these monads, placing this list in a monad of the same type. Note, that "evaluating" can be interpreted as "performing an action", for example in the case of print." It looks to me as if sequence works here because values of MyState are themselves functions, but how? Many thanks for any pointers and clarification! Hans van Thiel
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.
participants (2)
-
Albert Y. C. Lai -
Hans van Thiel