First things first: I am a beginner with Haskell, so if you find anything odd please ask or correct me. Along with an introductory lecture in functional progamming I am currently reading One of the things the author likes to do is implement copies of standard library functions to explain how they work. I think this is a good and fun way to learn. In fact I wrote a post last year taking exactly this approach about reduce, map, filter and find in JavaScript. I used reduce to implement the other three functions1. Since these are very core functional programming concepts, they play a central role in Haskell and appear quite early in the book. The functions map, filter and find have the same name in JS and Haskell, but JavaScript’s reduce is called foldr in Haskell. Technically I should be able to take my JavaScript functions and convert them one to one to Haskell. After I did this for map, I realized that Haskell lets me express the relation between the functions in a really pure form. This pure form is called pointfree style. So instead of porting filter and find from JavaScript I decided to try and simplify the map implementation as much as possible. This is what I started with:

-- Ported from JavaScript in previous post
_map f xs = foldr (\x zs -> f x : zs) [] xs

If you look closely you can spot one difference. In JavaScript I used the spread operator to append new elements at the end of the list, while in Haskell I use : to prepend to the list. The reason is that I don’t know of an “append” function, but do know the prepend function :. Since map treats each list element in isolation, it does not matter whether we build the resulting list from left or right.

You can already see that Haskell has a lot less “syntax overhead” for this code. But we can simplify things way more using two ideas from functional programming. The first one is called currying, which allows us to omit the xs argument.

-- Use currying for second argument xs of _map
_map f = foldr (\x zs -> f x : zs) []

If you know about currying, you should be able to understand why we can do this. In case you do not, I will try to explain it in simple terms: Haskell knows that foldr is a function which takes three arguments: A function, an initial value and a list. Here we call foldr with just two arguments and omit the list to be folded (previously xs). In this case, some programming languages will throw an error (Java, C) and some will initialize the third argument to be undefined (JavaScript). Functional programming languages like Haskell do something else. The result of the call with two arguments is a new function which only takes one argument. This last argument will become the third one to the original function call. Still confused? I highly recommend the Funfunfunction episode on the topic2 then.

Not confused anymore? Let’s do more currying then:

-- Use currying for second argument zs of lambda
_map f = foldr (\x -> (:) (f x) ) []

In order to use currying inside the lambda we have to write its return value in the form function argument argument. The additional parentheses are needed to “convert” the : “operator” into a function and to make sure f x is applied before :. Other than that, this is the exact same simplification as the first step.

I figured out one more step that allows us to curry the lambda completely and omit its x argument too:

-- v4
_map f = foldr ((:) . f ) []

Here I introduced the dot operator . which denotes function composition. Basically, fun1 . fun2 is a function that feeds its argument into fun2 and the resulting value into fun1. The result from the fun1 call is then returned as result of fun1 . fun2. Therefore the result is the same as nesting function calls. The problem with nested function calls is that we can only do it when we actually call the function. In our example (:) (f x) are two function calls that are nested, the result of one is argument to the other. The dot operator simply returns a function which behaves exactly like that. So the intermediate step of the lambda is \x -> ((:) . f) x. This form now lets us use currying and arrive at the last form above.

I am sure that there is a way to get rid of the last f argument too and express _map completely pointfree. I will try to do this too, but finish this post here. The takeaway is that pointfree style lets us express how functions are composed of others by using operations on function such as composition rather than saying how individual values (arguments) pass through the different functions.