List Operations in Elixir - Part 2

Earlier this week I wrote about the list operations from Functional Programming in Scala that I written up in Elixir. There were a few more exercises in this section which I’ve now completed. These were pretty straightforward so this post is earlier than expected.

You can find my tests that describe the exercises and my solutions in the github repo along with the last set.

Implementing map

One of the more interesting exercise was to implement the map function for lists. I started off writing the recursive function directly.

def map([], f), do: []
def map([h | t], f), do: [f.(h) | map(t, f)]

I like writing these function directly, but while writing it I was a little concerned because the function is not tail recursive. Reading the exercises in the text again I felt encouraged to rewrite map using one of the fold functions. I came up with this:

def map(l, f), do: List.foldr(l, [], fn (x, acc) -> [f.(x) | acc] end)

While I enjoy writing out the recursive functions by hand I’ve learned a valuable lesson here. There is a lot to be gained from using these standard functions where possible: thinking a little harder about how to repose these problems can pay off.

That also made me think, Scala has a annotation that tells the compiler that the writer of a function expects that it is tail recursive. The compiler will generate an error if its not actually able to tail optimize the call. It looks like this:

def isSorted[A](as: Array[A], gt: (A,A) => Boolean): Boolean = {
  @annotation.tailrec
  def go(n: Int, acc: Boolean): Boolean = {
    if (n == 0) acc
    else go(n - 1, gt(as(n), as(n-1)))
  }

  go(as.length - 1, true)
}

I haven’t seen anything similar for Elixir but, in my limited experience it seems like it could be useful.

Implementing zip

The exercises in this section give concrete examples and then ask the reader to generalize. This is how the book teaches concepts like map and fold. I have a background in mathematics so I am familiar with this sort of generalization. I guess I also have some familiarity with these operations from Ruby as well. So when I read exercise 22 which asks the reader to write a function that adds corresponding elements from two different lists I immediately though of the zip function that I know from Ruby.
I wrote up an implementation that zips two lists into a list of tuples each consisting of corresponding paris of elements.

defp zip([], _m), do: []
defp zip(_l, []), do: []
defp zip([lh | lt], [mh | mt]), do: [{lh, mh} | zip(lt, mt)]

To solve the given exercise I was able to compose zip and map where the map would add the elements of the tuple. Writing a function that generalizes the technique to use an arbitrary operation was then no problem:

def sum_across_lists(l, m), do: zip(l, m) |> map(&( elem(&1, 0) + elem(&1, 1)))
def across_lists(l, m, f), do: zip(l, m) |> map(&(f.(elem(&1, 0), elem(&1, 1))))

I really like the the |> operator here. While I understand composition I think the concept of pipelining feels more appropriate in these list processing situations.

I was again a little concerned that I wasn’t able to implement zip in a tail recursive manner. This time the solutions from the text were no help. After a little searching I found this post, in Erlang, which initially describes a solution like mine but links to a tail call optimized version. I won’t repeat the code here but like many tail recursive functions it has to add an accumulator argument so as to accumulate a result. It also produces the zip in reverse order and then uses an optimized reverse function to yield the desired result.

I feel like I’m getting the hang of this functional list processing though I still feel like I don’t see the tail recursive implementations. The next section in the text is on trees and I hope work through the exercises over the next week.