# Implementing Map function with List.fold_left

#1

I am going through the exercises of learn-reasonml-workshop, it’s been going well and I feel good about finally getting comfortable with the language after previously only reading about it.

In the 21st exercise the task is two implement `Map`, `Iter` and `Filter` functions, using `List.fold_left`.

/* Now let’s use List.fold_left to write some other useful List functions. */

I have managed to implement `Iter` and `Filter` using `List.fold_left`, but I can’t find a way to do it for `Map`, given the defined signature:

`let map: ('a => 'b, list('a)) => list('b);`

I did manage to write an implementation without `fold_left`:

``````let map = (fn: 'a => 'b, xs: list('a)) : list('b) => {
let rec aux = xs =>
switch (xs) {
| [] => []
| [y, ...ys] => [fn(y), ...aux(ys)]
};
aux(xs);
};
``````

But, if someone knows how to do this with `fold_left` I would like to have a look at the implementation.

#2

The approach is to use `[]` as the initial value for the fold, and appending to it on each accumulation.

``````let map = (f: 'a => 'b, xs: list('a)): list('b) =>
List.fold_left((acc, x) => List.append(acc, [f(x)]), [], xs);
``````

This works nicely for the tests in learn-reasonml-workshop, but if you were to implement a map with fold then you’d want to use `fold_right` instead of `fold_left`. This avoids having to use `List.append` which is not performant here, and instead you can use the cons constructor to quickly prepend elements to a list.

Here’s an example from the CS 3110 OCaml book that uses `fold_right` and cons: http://www.cs.cornell.edu/courses/cs3110/2018fa/textbook/hop/using_fold.html
(you might want to use the Reason Chrome extension to convert the OCaml syntax to Reason)

#3

Thanks for the reply. I have also had a look at the examples from Cornell University, I was trying to convert the `fold_right` example to `fold_left`, but without success .

I think it’s best to move on and don’t sweat it over this example…

#4

Here’s a nice comparison of the `List.fold_right` and `List.fold_left` functions.