# Learning Haskell: Implementing map with foldr

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 learnyouahaskell.com.
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 functions^{1}.
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 topic^{2} 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.*