It's a pretty simple idea: we create the AST by assembling a function taking the environment and producing a result. We're creating a function of type
Environment -> Int
It happens that there is a very simple way to combine functions like this. In particularly, if we have the following functions:
f :: Environment -> a
g :: a -> (Environment -> b)
we can "sequence" them by threading the environment through, giving us a function of type
h :: Environment -> b
This function can be defined like this:
h environment = g (f environment) environment
Basically, we first pass the environment to the first expression, get its result and then pass both that and the environment into the second expression.
Hopefully this is pretty intuitive: all we're really doing is letting both functions read from the environment. This happens to be called the "Reader" monad, and this sequencing action is bind (>>=).
The other thing we need for this to be a monad is a function called return which just embeds a value. In this particular case, we just have a constant value that ignores its argument, so:
return x = \ _ -> x
Now we specify how different base expressions can be derived from their environments. A numeric literal just ignores the environment and returns itself, so that's just return:
number = return
A variable looks itself up in the environment. If it doesn't ignore, it uses a default value of 0. Put another way, we want to find the name in the environment with a default of 0, so we just write:
variable = findWithDefault 0
This is using point-free code quite a bit. Once you get used to it, you'll find it's more readable because it's simpler; however, for a beginner, it might be clearer to writ the arguments out explicitly:
variable name = \ environment -> findWithDefault 0 name environment
We can also see how the `variable' function produces the type of value I was talking about before: it reads from an environment.
Now on to operators. Essentially, we want the operators add and mul to take two values reading from an environment and string them together as above after adding/multiplying them. This happens to correspond to a very common monadic function called liftM2; you can read the name as "lift a two-argument function to operate on some monad m".
Finally, when we put everything together, expressionTree becomes a function which takes an environment and strings it through a series of operations, giving an Int result at the very end. We can then just print this result given an arbitrary environment.
I hope this cleared things up and maybe gave you some intuition about why we care about monads.
Looking at some of the other solutions: the Haskell version is the same general idea as the some of the other solutions using functions, like pmarreck's (which is just a couple of posts above it). The main difference is that it uses some more general functions to make all the env plumbing implicit and pretty.
Many thanks for your effort to explain it to me. You made work my brain!
At first I was really stuck, when trying to understand your code. And I actually started to describe my difficulties. And then by writing them down I started to understand bit by bit. So just because most of the text is already written and maybe if somebody is struggling like me in understanding this code, I will write down my journey...
First, for the convenience of potential readers, here your original code:
First difficulty for me, as a Haskell beginner, are the functions without parameters and without types. So trying to grok the code I wrote them down with everything. I write the function 'number' as
number n = return n
If I check in GHCI with ':type number' I get
number :: Integer -> Map [Char] Integer -> Integer
How the heck can this function become this type signature? But OK, apparently there is this hidden parameter of type 'Map [Char] Integer' that is passed when it is called. So I should be able to write the function number with explicit signature (that Haskell otherwise infers) and the 2nd parameter:
number :: Integer -> Map [Char] Integer -> Integer
number n env = return n
... and guess what? GHCI does not accept it and throws some cryptic error. How does this make sense? Haskell tells me through its inferred type signature that the function number takes 2 arguments (Integer) and (Map [Char] Integer) and returns only one. But when I write the function with a 2nd argument it does NOT accept it?
I was struggling here some time. Until I realized that in this example the 'return' function actually as well needs to get the 2nd argument. So if I rewrite it like this:
number :: Integer -> Map [Char] Integer -> Integer
number n env = return n env
it is accepted by the compiler. It might seem trivial now, but when I read your definition of 'return' being:
return x = \ _ -> x
it does not show any 2nd parameter and additionally confusing in the function body takes from wherever some parameter that it ignores (_). I understand that it should mean that the function 'return' returns another function that takes whatever argument you give it and returns the value that you provided to the 'return' function. But for me as a beginner this:
return x _ = x
is much clearer and has actually the same type signature. So far I would cynically conclude that Monads are about saving keyboard strokes by omitting writing parameters which are actually there. But I guess there is more than that.
But anyway, after I understood where the strange type signature with a 2nd parameter comes from, the rest was easier. Here my beginners' rewrite of the variable function:
I could understand where 'Map [Char] Integer' comes from when I looked how 'expressionTree' is used, namely by giving it the environment 'expressionTree environment'. So I rewrite the definition of expressionTree as:
expressionTree e = add (variable "a") (multiply (number 2) (variable "b")) e
Which now makes clear that the function 'add' takes 3 parameters and returns an Integer. And here came the next difficulty:
Just for reference, I didn't actually write that code--whoever commented on GitHub did.
There's one very important note to add: monads are much more general than just this particular example. A monad is any type with certain operations; it can encode different behaviors. In this case, the type (Map [Char] Integer -> a) is a monad, representing a value reading from the Map. However, you can also have other monads like Maybe a, which represents a value that may not exist.
I don't think I can really describe monads completely here, so you'll have to look up some resources elsewhere. It's just very important to realize that monads are much more general than this specific example.
There's no hidden/default parameters in haskell (records have default values but that's different), that line is eta reduced because those 2 functions always behave identically
number = return
You have to figure what you did in that GHCi session that defined (return) to shadow the Prelude one that everybody knows about, which is the only one in language and "standard libs" with that name
I am confident you'd get good answers somewhere where people are monitoring for hsakell questions (SO, reddit, mailing list; on HN threads usually disappear in a few hours)(tikhonj's answers are excellent, but s/he is only one person):
5 comments
[ 3.0 ms ] story [ 21.0 ms ] threadHopefully this is pretty intuitive: all we're really doing is letting both functions read from the environment. This happens to be called the "Reader" monad, and this sequencing action is bind (>>=).
The other thing we need for this to be a monad is a function called return which just embeds a value. In this particular case, we just have a constant value that ignores its argument, so:
Now we specify how different base expressions can be derived from their environments. A numeric literal just ignores the environment and returns itself, so that's just return: A variable looks itself up in the environment. If it doesn't ignore, it uses a default value of 0. Put another way, we want to find the name in the environment with a default of 0, so we just write: This is using point-free code quite a bit. Once you get used to it, you'll find it's more readable because it's simpler; however, for a beginner, it might be clearer to writ the arguments out explicitly: We can also see how the `variable' function produces the type of value I was talking about before: it reads from an environment.Now on to operators. Essentially, we want the operators add and mul to take two values reading from an environment and string them together as above after adding/multiplying them. This happens to correspond to a very common monadic function called liftM2; you can read the name as "lift a two-argument function to operate on some monad m".
Finally, when we put everything together, expressionTree becomes a function which takes an environment and strings it through a series of operations, giving an Int result at the very end. We can then just print this result given an arbitrary environment.
I hope this cleared things up and maybe gave you some intuition about why we care about monads.
Looking at some of the other solutions: the Haskell version is the same general idea as the some of the other solutions using functions, like pmarreck's (which is just a couple of posts above it). The main difference is that it uses some more general functions to make all the env plumbing implicit and pretty.
At first I was really stuck, when trying to understand your code. And I actually started to describe my difficulties. And then by writing them down I started to understand bit by bit. So just because most of the text is already written and maybe if somebody is struggling like me in understanding this code, I will write down my journey...
First, for the convenience of potential readers, here your original code:
First difficulty for me, as a Haskell beginner, are the functions without parameters and without types. So trying to grok the code I wrote them down with everything. I write the function 'number' as If I check in GHCI with ':type number' I get How the heck can this function become this type signature? But OK, apparently there is this hidden parameter of type 'Map [Char] Integer' that is passed when it is called. So I should be able to write the function number with explicit signature (that Haskell otherwise infers) and the 2nd parameter: ... and guess what? GHCI does not accept it and throws some cryptic error. How does this make sense? Haskell tells me through its inferred type signature that the function number takes 2 arguments (Integer) and (Map [Char] Integer) and returns only one. But when I write the function with a 2nd argument it does NOT accept it?I was struggling here some time. Until I realized that in this example the 'return' function actually as well needs to get the 2nd argument. So if I rewrite it like this:
it is accepted by the compiler. It might seem trivial now, but when I read your definition of 'return' being: it does not show any 2nd parameter and additionally confusing in the function body takes from wherever some parameter that it ignores (_). I understand that it should mean that the function 'return' returns another function that takes whatever argument you give it and returns the value that you provided to the 'return' function. But for me as a beginner this: is much clearer and has actually the same type signature. So far I would cynically conclude that Monads are about saving keyboard strokes by omitting writing parameters which are actually there. But I guess there is more than that.But anyway, after I understood where the strange type signature with a 2nd parameter comes from, the rest was easier. Here my beginners' rewrite of the variable function:
This is pretty straight forward. Moving on: I could understand where 'Map [Char] Integer' comes from when I looked how 'expressionTree' is used, namely by giving it the environment 'expressionTree environment'. So I rewrite the definition of expressionTree as: Which now makes clear that the function 'add' takes 3 parameters and returns an Integer. And here came the next difficulty:There's one very important note to add: monads are much more general than just this particular example. A monad is any type with certain operations; it can encode different behaviors. In this case, the type (Map [Char] Integer -> a) is a monad, representing a value reading from the Map. However, you can also have other monads like Maybe a, which represents a value that may not exist.
I don't think I can really describe monads completely here, so you'll have to look up some resources elsewhere. It's just very important to realize that monads are much more general than this specific example.
http://www.haskell.org/hoogle/?hoogle=return
I am confident you'd get good answers somewhere where people are monitoring for hsakell questions (SO, reddit, mailing list; on HN threads usually disappear in a few hours)(tikhonj's answers are excellent, but s/he is only one person):
https://plus.google.com/100165496075034135269/posts/UztvNpAJ...