Language Comparison --- A Simple AST example | Hacker News Reader

Language Comparison --- A Simple AST example

gist.github.com

4 pointscygwin985 comments

Cannot understand the version of "Tagless, Monadic, Inferred Haskell". But it is very short.

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:

  import Data.Map
  import Control.Monad

  number   = return
  add      = liftM2 (+)
  multiply = liftM2 (*)
  variable = findWithDefault 0

  environment = fromList [("a",3), ("b",4), ("c",7)]

  expressionTree = add (variable "a") (multiply (number 2) (variable "b"))

  main = print $ expressionTree environment

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:

  variable :: [Char] -> Map [Char] Integer -> Integer
  variable vn env = findWithDefault 0 vn env

This is pretty straight forward. Moving on:

  *Main> :t expressionTree 
  expressionTree :: Map [Char] Integer -> Integer

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:

  *Main> :type add
  add
    :: (Map [Char] Integer -> Integer)
       -> (Map [Char] Integer -> Integer) -> Map [Char] Integer -> Integer

My first reaction was: What? Why does (variable "a") have a signature of a function, it should just return an Integer? This helped me to understand:

  *Main> :type variable
  variable :: [Char] -> Map [Char] Integer -> Integer
  *Main> :type variable "a"
  variable "a" :: Map [Char] Integer -> Integer

With 'variable "a"' a new function is constructed which has already got its 1st parameter and just needs the environment as 2nd environment, which again will be done by the 'liftM2' function inside 'add'. If I recall correctly the construction of such new function is called 'partial function application' in Haskell terminology. But anyway from there on the rest becomes clear. Maybe just for beginners (the '$' sign is confusing) and completeness of this explanation I would rewrite the last line as:

  main = print (expressionTree environment)

As I told you, you made my brain do a lot of work (and my fingers too) - thanks! But at least I have understood a bit more about Monads: It is just about avoiding to explicitely type all the parameters. But at the same time this is possible without Monads. I guess I still miss something.

Thanks again for your code. I like Haskell, because the code appears to me beautiful, concise but not ugly and when trying to unwind all the details everything seems to fit, there are no contradictions.

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

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...

Reply on news.ycombinator.com