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 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.
find have the same name in JS and Haskell,
reduce is called
foldr in 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
map implementation as much as possible.
This is what I started with:
If you look closely you can spot one difference.
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
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
-- 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
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.
fun1 . fun2 is a function that feeds its argument into
fun2 and the resulting value into
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.