UPDATE, 15 Nov 2017 — Michael Kohl@citizen428 suggested in the comments some improvements for the proposed solution that I wanted to highlight
Yesterday, I found a question on Stack Overflow that essentially asked if an Elixir implementation was properly written in the functional style of programming.
The implementation suggested by the original poster contained too much
if statements which is somewhat a smell in the functional style. In fact , loops and
if statements should be avoided in favor of pattern matching and recursion.
Back in the day, when I was playing around with Haskell, I remember that it was simply impossible to diverge from the functional style at least when avoiding monads.
I decided to implement a solution to the problem in order to have some deliberate practice in the functional style in Elixir.
The problem is simple to state.
Generate the first
n elements of the following sequence:
[1, (previous + m),...]
m = 2 initially and is incremented by
[1, (previous + 2), (previous + 2), (previous + 2), (previous + 2), (previous + 4), (previous + 4), (previous + 4), (previous + 4), (previous + 6), (previous + 6), (previous + 6), (previous + 6)]
Here are the first
16 elements of the list that must be generated:
[1, 3, 5, 7, 9, 13, 17, 21, 25, 31, 37, 43, 49, 57, 65, 73, 81]
The solution that I came up with is to basically:
- Generate an infinite list of even numbers with each numbers duplicated 4 times, essentially this list
[2, 2, 2, 2, 4, 4, 4, 4, 6, 6, 6, 6...]
- Take the count of elements needed in the final sequence
- Using reduce, iterate over the duplicated even numbers which represents the
min our problem and build the final list
Step 1: Infinite stream of duplicated even numbers
m from the problem definition, each 4 iteration it is incremented by 2, so why not generate a list of all the
m that are going to be added to the elements of the final list?
Once the previous is done, all we have to do is to iterate over these
m to figure out the value of
m for a specific element.
Here we are basically “pre-computing” an infinite sequence of
Consider the following
First, we used the
Stream module to create an infinite list starting from 1 and having its elements successively incremented by 1, then we filter out the odd numbers from the sequence keeping only the even numbers.
Each element(even number) of the infinite list is duplicated 4 times which produces a list of lists of duplicated numbers (
[[int]]) that looks something like this
[[2, 2, 2, 2], [4, 4, 4, 4]...]. Finally the previous list of lists is flattened to a list of integers (
Here we used the
Stream module to generate the sequence, which allows us to build sequences that can be processed lazily, this is similar to LINQ methods that returns an
IEnumerable in C# and which are evaluated lazily as well.
Step 2: Evaluating the needed count of elements
By using the
Enum.take function we can get a list having the desired elements count:
This evaluates the sequence eagerly for the exact number of desired elements (16 in the previous case).
Step 3: Generating the result sequence
In order to generate the result sequence we simply feed the list of duplicated evens to the
For each even number
m, if the intial list is empty then add the first element, otherwise append to the list the last inserted element + m.
This build the desired list but in reverse and without 1 as the first element, all we have to do is to reverse the list then prepend 1.
A more compact solution
One answer has been suggested to the question in Stack Overflow and I must admit that it is more compact but involves using one
Here we iterate over a sequence containing the desired count of elements and
m is actually figured out in each iteration as follows:
Although not strictly functional, I think that this solution is more pragmatic. By leveraging the flexibility of Elixir that allows to use some imperative constructs this solution is more compact and may cause less cognitive load.
A revisited solution
get_stream_of_duplicated_evens function is now much shorter;from a stream of even numbers(
Stream.iterate(2, &(&1+2))), duplicate each element 4 times which produces a list of lists looking like
[[2, 2, 2, 2], [4, 4, 4, 4]] and the
flat_map the previous list.
get_result_list function as been split out to more smaller functions by leveraging recursion and pattern matching which makes it more readable.
Every time you find yourself using
if statements in Elixir there may be something wrong, but different situations may require different approaches and
if statements are there for a reason…
Also keep in mind that multiple smaller functions that is always preferable to big function, recursion is also there for reason too…