Problem with own written monad
Hello list, while trying to learn the secrets of monads, I decided to write a simply monand for pure educational purpose. But it turned out that it isn't as easy as I thought... I circumnavigate quite a number of hurdles but now I reached a point where I'm at a loss. :-( The source: #! /usr/bin/env ghc data Stack a = Stack { run :: [a] -> (a, [a]) } push :: a -> Stack a push x = Stack f where f xs = ( x, x:xs ) pop :: Stack a pop = Stack f where f (x:xs) = ( x, xs ) top :: Stack a top = Stack f where f (x:xs) = ( x, x:xs ) instance Monad Stack where return x = Stack f where f xs = ( x, xs ) (>>=) stack g = Stack f where f s0 = (x2, s2) where (x1, s1) = run stack s0 (x2, s2) = run (g x1) s1 The errors: ./mymonad.hs:16:24: Couldn't match expected type `b' (a rigid variable) against inferred type `a' (a rigid variable) `b' is bound by the type signature for `>>=' at <no location info> `a' is bound by the type signature for `>>=' at <no location info> Expected type: [b] -> (b, [b]) Inferred type: [a] -> (b, [b]) In the first argument of `Stack', namely `f' In the expression: Stack f ./mymonad.hs:19:28: Couldn't match expected type `b' (a rigid variable) against inferred type `a' (a rigid variable) `b' is bound by the type signature for `>>=' at <no location info> `a' is bound by the type signature for `>>=' at <no location info> Expected type: [b] Inferred type: [a] In the second argument of `run', namely `s1' In the expression: run (g x1) s1 I think the problem is that my operator (>>=) is of type: Stack a -> (a -> Stack a) -> Stack a but should be: Stack a -> (a -> Stack b) -> Stack b But, I have simply no clue how to fix that. :-( Can anybody give my a hint? Thank you in advance. Michael Roth
Michael Roth wrote:
while trying to learn the secrets of monads, I decided to write a simply monand for pure educational purpose. But it turned out that it isn't as easy as I thought... I circumnavigate quite a number of hurdles but now I reached a point where I'm at a loss. :-(
data Stack a = Stack { run :: [a] -> (a, [a]) }
This definition means that the values in the stack are always of the same type as the values returned by the monadic computation. Try something like data Stack s a = Stack { runStack :: [s] -> (a, [s]) } and instance Monad (Stack s) where ... to thread the same stack through a monadic computation with various intermediate result types, as you probably want. Tillmann
Michael Roth wrote:
Hello list,
while trying to learn the secrets of monads, I decided to write a simply monand for pure educational purpose. But it turned out that it isn't as easy as I thought... I circumnavigate quite a number of hurdles but now I reached a point where I'm at a loss. :-(
The source:
#! /usr/bin/env ghc
data Stack a = Stack { run :: [a] -> (a, [a]) }
You want: data Stack a b = Stack { run :: [a] -> (b, [a]) } All monads have the property that they can represent calculations of values of any type. Without that, they're not so useful. So your "Stack" needs two type variables : one for the kind of thing stacked, and one for what we're actually calculating at this instant. The correct types for the other functions are:
push :: a -> Stack a
push :: a -> Stack a () [you could have a -> Stack a a, if you want to echo back the pushed value, but why bother? ]
pop :: Stack a
pop :: Stack a a
top :: Stack a
top :: Stack a a With those clues I think you will be able to write >>= and return more successfully! There are some other interesting combinators to consider, like: isolate :: Stack b x -> Stack a x -- runs the computation with an empty stack, therefore -- guaranteeing it does more pushes than pops or isolate :: Stack b x -> Stack a ([b],x) -- if you want to collect the pushes. and so on. Jules
Jules Bean schrieb:
data Stack a b = Stack { run :: [a] -> (b, [a]) }
Thank you, that does the trick.
The correct types for the other functions are:
push :: a -> Stack a () pop :: Stack a a top :: Stack a a
With those clues I think you will be able to write >>= and return more successfully!
Yes, this was the missing link. Because I thought "Stack a a" could be abbreviated using "Stack a" I run into these problems. This was also the cause that "push" echoed back the pushed value.
There are some other interesting combinators to consider, like:
isolate :: Stack b x -> Stack a x -- runs the computation with an empty stack, therefore -- guaranteeing it does more pushes than pops
Did you mean: isolate :: Stack s1 a -> Stack s2 a isolate stack = Stack f where f xs = ( fst $ run stack [], xs)
and so on.
Yes, I have done: push, pop, top, nop, count, clear, isolate and binop. All pretty easy, once I understand that "Stack a b" thing.
Michael Roth wrote:
Did you mean:
isolate :: Stack s1 a -> Stack s2 a isolate stack = Stack f where f xs = ( fst $ run stack [], xs)
Yes. What's slightly interesting is the way the types promise the isolation: the Stack s1 action clearly can't be consuming any of the [s2] stack, because that is the wrong type. This continues to hold even if you happen to run it with s1 == s2. Jules
Michael Roth wrote:
Yes, I have done: push, pop, top, nop, count, clear, isolate and binop. All pretty easy, once I understand that "Stack a b" thing.
Now you are ready to write your monad tutorial. This is a standard rite of passage (or should that be "write a passage") for new Haskell programmers. Paul.
data Stack a = Stack { run :: [a] -> (a, [a]) }
[...skipped...]
But, I have simply no clue how to fix that. :-( Can anybody give my a hint?
Yes. It's simply impossible. The Stack data type can't be turned into a monad. May be you can explain what do you want to do with this "monad"? What kind of code would you write if it would be such monad?
On Mon, 7 Jan 2008, Miguel Mitrofanov wrote:
data Stack a = Stack { run :: [a] -> (a, [a]) }
[...skipped...]
But, I have simply no clue how to fix that. :-( Can anybody give my a hint?
Yes. It's simply impossible. The Stack data type can't be turned into a monad.
What about using the State monad? Still suitable as exercise?
On Mon, 2008-01-07 at 18:15 +0300, Miguel Mitrofanov wrote:
data Stack a = Stack { run :: [a] -> (a, [a]) }
[...skipped...]
But, I have simply no clue how to fix that. :-( Can anybody give my a hint?
Yes. It's simply impossible. The Stack data type can't be turned into a monad.
Indeed, the very first hint is that Stack isn't a functor because the type variable a occurs both positively and negatively.
On Mon, 2008-01-07 at 18:21 +0000, Paul Johnson wrote:
Miguel Mitrofanov wrote:
Yes. It's simply impossible. The Stack data type can't be turned into a monad.
Why not? Surely this is just a variation on the theme of a state monad?
I somewhat explain in this reply: http://www.haskell.org/pipermail/haskell-cafe/2008-January/037605.html
Derek Elkins
On Mon, 2008-01-07 at 18:21 +0000, Paul Johnson wrote:
Miguel Mitrofanov wrote:
Yes. It's simply impossible. The Stack data type can't be turned into a monad.
Why not? Surely this is just a variation on the theme of a state monad?
I somewhat explain in this reply: http://www.haskell.org/pipermail/haskell-cafe/2008-January/037605.html
Which states that the data structure doesn't support the Monad, or that the Monad can't be implemented using that data structure. So, see, some stack data type can certainly be turned into a monad, but this Stack data type can't. -- (c) this sig last receiving data processing entity. Inspect headers for past copyright information. All rights reserved. Unauthorised copying, hiring, renting, public performance and/or broadcasting of this signature prohibited.
Yes. It's simply impossible. The Stack data type can't be turned into a monad. Why not? Surely this is just a variation on the theme of a state monad?
Because it can't be turned into a functor. You can't, given a function a -> b, construct a function Stack a -> Stack b. On the contrast, you can easily construct a function State z a -> State z b.
Miguel Mitrofanov schrieb:
May be you can explain what do you want to do with this "monad"?
Pure educational purpose, just "learning by doing".
What kind of code would you write if it would be such monad?
Useless stuff like: s2 = do push 11 push 17 count >>= push binop (+) binop (*) pop
participants (8)
-
Achim Schneider -
Derek Elkins -
Henning Thielemann -
Jules Bean -
Michael Roth -
Miguel Mitrofanov -
Paul Johnson -
Tillmann Rendel