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
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:
because Elixir / Erlang matching can’t match through these
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.
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.
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:
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:
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
result the final stream.
result is returned from