Strictness and Laziness in Elixir - Part 2b

Last week I fell behind in my blogging and only posted my raw notes for the exercises in “Infinite Streams and Corecursion” in Functional Programming in Scala. Elixir Fountain was kind enough to announce last week’s post so I’ve opted to leave it as is. But this week I’ll written up this small post to fill in some of the missing details in the raw notes. I will discuss Elixir’s standard Streams module next week.

I continued using the same github repo from the first part of this exploration. If you want to work through the exercises for yourself, then follow the directions in the repo’s README before reading the rest of this post.

Exercise 15 - tails

This exercise asks us to implement a function called tails which returns all tails of the stream starting with the original list. It should be implemented using unfold

My notes from last week start to fall apart at exercise 15, at least in terms of describing the tails function. What they do show are problems I encountered while trying to write up the test and solution.

The first thing that I point out in the notes is that the cons notation is less convinient than the built-in list and stream notation [h | t]. For example, I can’t write the following as a test:

test "tails" do
  assert L.tails(build_stream) == L.cons(
    L.cons(1, L.cons(2, L.cons(3, []))),
    L.cons(
      L.cons(2, L.cons(3, [])),
      L.cons(
        L.cons(3, []),
        []
      )
    )
  )
end

because Elixir / Erlang matching can’t match through these cons calls.

I instead ended up using flat_map to flatten the result of tails and then using to_list as I have in all the other tests. While this does give a nice small test it completely removes the structure that tails is expected to produce form the test.

test "tails" do
  assert L.tails(build_stream) |> L.flat_map(&(&1)) |> L.to_list == [1, 2, 3,  2, 3,  3]
end

I’ve been thinking that Elixir allows me to write my own implementation for its [h | t] operator. It would be interesting to try doing this for my streams implementation. I wonder if it would improve the matching that is possible in these tests. I will also explore this when I look into the Elixir standard streams library next week.

Exercise 16 - scan

As I mentioned last week, this was a rather difficult exercise for me. The exercise is to implement a function scanRight which is a generalization of tails. It should be similar to foldRight except that it returns a stream of the intermediate results. The text goes on to require that scanRight reuse the intermediate results as it constructs each successive element in the result.

I chose to name my function scan after Elixir’s standard Stream.scan. Then I wrote the test. Then I thought about the tests question: ““Can it be implemented using unfold?” I figured that scan could be implemented using unfold but not efficiently because unfold iterates through the stream in the wrong order making it impossible to reuse the intermediate results.

Even though a implementation based on unfold would not be efficient I wrote it anyway. This was a good exercise for my test and TDD suggests that we write up a simple implementation first. The function calls foldr each time and isn’t able to reuse the result.

def scan(s, acc, f), do: unfold(s, fn
  (:terminate) -> nil
  ([]) -> {0, :terminate}
  (%Cons{head: h, tail: t}) -> { foldr(cons(h.(), t.()), ld(acc), fn (x, acc) -> f.(x, acc.()) end), t.() }
end)

I tried anoter version that I thought were more efficient. After writing them I realized I didn’t have a good way of proving they were efficient so I wrote a test to enforce the efficiency requirement:

test "scan should reuse intermediate results" do
  {:ok, counter} = Agent.start_link(fn -> 0 end)
  count_calls = fn
    (_, _) -> Agent.get_and_update(counter, fn (current) -> {current + 1, current + 1} end)

  end

  assert L.scan(build_stream, 0, count_calls) |> L.to_list == [3, 2, 1, 0]
end

This test starts by creating an Agent to hold a counter. Then I create a function to call the Agent to increment and the counter. The assertion calls scan with the increment function. This way, for a 3 element stream I can confirm that the function passed to scan was called only 3 times during the construction of the result.

Even with this test I still had trouble coming up with the right solution. But I was at able least recognize when I had an incorrect solution. Ultimately, I had to look at the text’s solution which used foldr. I had tried thinking through foldr based solutions but missed the trick that the text employed. The key is is maintain more state in the foldr than just the resulting stream. Then when the foldr completes extract the stream and return it. After learning this lesson I wrote the folling, efficient, solution and passed my tests:

def scan(s, initial, f) do
  {_total, result} = foldr(s, ld({initial, cons(initial, [])}),
    fn (x, lazy) ->
      {val, acc} = lazy.()
      head = f.(x, val)
      {head, cons(head, acc)}
    end
  )
  result
end

This scan function uses foldr and at ever iteration it has a tuple containing val which is the last value computed and acc which is the accumulated stream. val is used when calling f so as to efficiently reuse intermediate computation. acc is used to build up the resulting stream. The tuple returned by foldr is destructured into _tatal (the final val) and result the final stream. result is returned from scan.