List Operations in Elixir - Part 1

Getting Started

As I promised yesterday I’ve started converting exercises from Functional Programming in Scala to Elixir. This week the focus was on list operations from sections 3.3 and 3.4 in the chapter “Functional data structures”. For the most part this was straightforward so I won’t go into a lot of detail on many of the operations. This post will focus on the most interesting exercises. However, if you’d like to look through all the other exercises, I put them on github. If you want to work through the exercises for yourself, then I recommend you grab the tests from the github repo now and work through them before reading the rest of this post.

foldl and foldr

Some of the most interesting questions involved implementing foldLeft and foldRight in several different ways. The text gave an implementation for foldRight, I didn’t bother adding it to my module and instead used the built-in List.foldr/3.

First I wrote a recursive implementation of foldLeft:

def foldLeft([], acc, _f), do: acc
def foldLeft([h | t], acc, f), do: foldLeft(t, f.(h, acc), f)

The next few exercises involved using foldLeft to implement functions to sum over a list, compute the product over a list and to compute the length of a list. I wrote simple recursive, pattern matching functions to implement these.

The next exercise was to implement a function to reverse a list using foldLeft. I had implemented this directly in the list-ops exercise on exercism.io so I was able to write up this implementation on top of foldLeft which simply pushes each element, starting from the left, into a new list:

def reverse(l), do: foldLeft(l, [], fn (x, acc) -> [x | acc] end)

The next exercise was really interesting, and much more difficult. The question is if foldLeft can be implemented using foldRight. And more importantly, can foldRight be implemented using foldLeft? The reason this is important, is that the naive implementation of foldRight isn’t tail recursive and will exceed the available stack space for large lists. But foldLeft is tail recursive and be optimized.

First I implemented foldRight in terms of foldLeft. The thing to note is that foldRight and foldLeft process the elements in reverse order. Based on this I realized if I first reversed the list and then used foldLeft I would in effect have performed foldRight. Because reverse was implemented using foldLeft this was within the requirements for the exercise. Here’s my solution:

def foldRightUsingLeft(l, acc, f), do: reverse(l) |> foldLeft(acc, f)

Much more difficult was to implement foldLeft using foldRight. I was not able to just reverse the list as my reverse function depends on foldLeft. I looked at the scala solution but still had trouble understanding how the solution worked or how to rewrite it in Elixir. I spent some time working through it and learned that the key is to accumulate a chain of composed functions that will ultimately compute the foldLeft. For example for the call

L.foldLeftUsingRight([x, y, z], acc , f)

we want to construct the function chain:

f(z, f(y, f(x, acc)))

Here’s the solution which I’ll explain in detail:

def foldLeftUsingRight(l, acc, f) do
  base = fn (b) -> b end
  chain = List.foldr(l, base,
    fn (x, accumulator) -> (fn (b) -> accumulator.(f.(x, b)) end) end)
  chain.(acc)
end

In the call to List.foldr/3 I pass a function

fn (x, accumulator) -> (fn (b) -> accumulator.(f.(x, b)) end) end

Note that this function returns a function so that the List.foldr/3 operation will accumulate by composing functions in the following progression:

(b) -> (b)
(b) -> f.(z, b)
(b) -> f.(z, f.(y, b))
(b) -> f.(z, f.(y, f.(x, b)))

Note that the initial case, (b) -> (b), is precisely the initial accumulator value I passed to List.foldr/3:

base = fn (b) -> b end

Back to final composition

f.(z, f.(y, f.(x, fn (b) -> b)))

which is a function of a single variable, b. The final step is to evaluate this function at the original initial accumulator value, acc. For clarity, I’ve separated this out into the call

chain.(acc)

The evaluation will give:

f.(z, f.(y, f.(x, acc)))

which is exactly what we set out to compute.

I really enjoyed this set of exercises. It was interesting to really learn how these fold operations work. My prior experience was with Ruby’s reduce so I wasn’t familiar with the folding left vs. right. Implementing one function in terms of the other really helped to reinforce what’s possible with these functions and the function approach in general. Next week I’ll continue with the rest of the exercises in this section.