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 :grinning:.

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.

Link