how is this haskell expression evaluated

Question

I am learning haskell and I came across this expression which I could not understand.

(flip const 1 . const flip 3 const 4) 5

The final result is 5 but I have no idea how it is evaluated.

Answer 1

Every time you see some “clever” function invocation in Haskell, always check its types, then try to play with it in GHCi.

The only way to learn Haskell is actually try it out, and you can't do it just by reading StackOverflow answers or online tutorials, you have to put expressions into GHCi, fail miserably, try to figure out the error for yourself, try to substitute different values in different places to make the error go away, try to divide the problem into chunks and comprehend them separately, and so on.

It's impossible to code Haskell without understanding its type system (which, I promise, is not hard). If you don't understand what, for example, a “type variable” means, read the chapter on Types and Typeclasses, and make sure you diligently try out every expression in GHCi.

Your original expression is:

(flip const 1 . const flip 3 const 4) 5

(.) is function composition, and if the expression typechecks (i.e. it doesn't throw a compile-time type error), then flip const 1 and const flip 3 const 4 got to be functions.

Exercise: Now open GHCi and enter the following one by one and inspect the types (:t GHCi command is to check a type of some value):

:t const
:t flip

First of all, remember this fact about Haskell's type system. If there is a type variable, such as a, in a type declaration, then the function must accept any type. If there is a type variable bounded by a typeclass, e.g. f :: Num a => a -> a, then the function must accept any type, that is instance of typeclass Num (i.e. any number). You can't have a function that returns a, but in whose body you make it return a String.

Second, if there are more than 1 type variables in the type declaration, their type is always the same. So if you have a function has the type f :: a -> a, and you gave it an Int, it must return Int. Because Haskell has no runtime type checking, you can't assume anything about the types, if you accept a type variable.

These 2 facts restrict what a function can do, if it has a certain type. Thus:

• f :: a -> a always returns the argument; it can't reason about the argument, because it doesn't know its type, it can't apply any functions with more specific types, so it has to just return the argument
• f :: (a, b) -> a is fst, and nothing else, it doesn't know anything about the first element of a pair, so it has to just return it
• f :: (a, b) -> b is snd, for the same reason
• f :: a -> b -> a takes 2 arguments and returns the first
• f :: b -> a -> a takes 2 arguments and returns the second

This restriction is a good thing, because just by looking at the type you can guess a lot about the function. Some types are just impossible, for example f :: a -> b, there is no function of such type (because what would b be anyway?).

Remember, -> in type declaration is right-associative, so:

f :: (a -> b -> c) -> b -> a -> c
f :: (a -> b -> c) -> b -> (a -> c)
f :: (a -> b -> c) -> (b -> a -> c)
f :: (a -> b -> c) -> (b -> (a -> c))
f :: (a -> (b -> c)) -> (b -> (a -> c))

are all equivalent. So you can treat a function of type f :: a -> b -> c as taking 2 arguments and returning a value, or you can treat it as taking 1 argument and returning a function of 1 argument.

“Wait,” you might say, “you said a function of type a -> b is impossible, then how can f be of type (a -> b -> c) -> b -> (a -> c), that is, return a function of type a -> c?” Well, f actually never returns a function of type a -> c, because you never pass a function of type a -> b -> c to it. Instead, you might pass a function of type Int -> a -> [a] and get a function of type a -> (Int -> [a]).

Then you pass another value, let's say of type String, to this new function. You get a function of type Int -> [String] as a result. Now Int -> [String] is not an impossible function, is it?

Technically speaking, you can return a function of type a -> b, it's called undefined. undefined is a value of type a, that is, it inhabits any type. But that's a topic for another time.

Exercise: So let's continue playing with types in GHCi:

:t const
:t flip
:t const flip
:t flip const

What have you learned from the types? Which arguments will these functions ignore? Which values (or functions) will they return?

Exercise: If you still don't understand, where I'm heading, try to enter these into GHCi in that order, to see how partial application changes types:

:t flip
:t flip const
:t flip const 1
:t const
:t const flip
:t const flip 3
:t const flip 3 const
:t const flip 3 const 4
:t id

Answer 2

By definition of (.):

  flip const 1 $ ((const flip 3) const 4) 5

By definition of const:

= flip const 1 $ flip const 4 5

By definition of flip:

= flip const 1 $ const 5 4

By definition of const:

= flip const 1 5

By definition of flip:

= const 5 1

Which is 5.

(As a little bonus insight, can you find out why flip const y is just id for all y? This reduces your expression to (id . id) 5.)