Updating Elixir structs selectively

In previous Exercism.io problem, we needed to merge two structs in a way that concatenates their list type properties, as opposed to replacing them. For example, let’s say we have a User struct like this:

defmodule User do
  defstruct name: nil, age: 18, phones: []
end

The user has a name, age and list of contact phones. Updating a user with new information is rather straightforward:

annika = %User{name: "Annika"}
%{annika | age: 21}
> %User{age: 21, name: "Annika", phones: []}

Elixir structs, as documentation states, behave as bare maps, meaning you can apply all the Map module functions to them. Since they behave like bare maps, you can also:

annika = %User{name: "Annika"}
Map.put(annika, :age, 21)
> %User{age: 21, name: "Annika", phones: []}

You can even merge two structs like this:

annika = %User{name: "Annika"}
formInput = %User{name: "Annika", age: 21}
Map.merge(annika, formInput)
> %User{age: 21, name: "Annika", phones: []}

But, this kind of merge overwrites values! Let’s try adding phones in that manner:

annika = %User{name: "Annika", phones: ["+44100200300"]}
annika |> Map.merge(%User{name: "Annika", age: 21, phones: ["+44111222333"]})
> %User{age: 21, name: "Annika", phones: ["+44111222333"]}

As you can see, this will overwrite the phones, so only last one is preserved. Map.merge/3 comes to rescue the day:

update_user = fn(user, other) ->
  Map.merge(user, other, fn(_, v1, v2) ->
    cond do
      is_list(v1) ->
        v1 ++ v2
      v2 == nil ->
        v1
      true ->
        v2
    end
  end)
end

annika = %User{name: "Annika", phones: ["+44100200300"]}
annika |> update_user.(%User{phones: ["+44111222333"]})
> %User{age: 18, name: "Annika", phones: ["+44100200300", "+44111222333"]}

What did we do here? Well, we used a combinator function for Map.merge/3 that inspects each prop and decides how to merge them selectively.

We decided to concatenate lists, use other’s user struct values when present (not nil) and fall back to original props otherwise. This allows us to update user only with some properties. The downside is that we can’t update with nil, but that’s outside of scope this time.

Happy structing 🙂

Meta(sploit)ing Elixir

The last exercise from Exercism.io had to do with meta programming Elixir in disguise. The task was an interesting one. You’re supposed to write a custom DSL that supports Graphviz like language for building graphs. So, one could write something like:

graph
  graph [bgcolor="yellow"]
  a [color="red"]
  b [color="blue"]
  a -- b [color="green"]

and get back a graph structure like this:

Graph {
  attrs: [
    bgcolor: "yellow"
  ],
  nodes: [
    {:a, [color: "red"]},
    {:b, [color: "blue"]}
  ],
  edges: [
    {:a, :b, [color: "green"]}
  ]
}

Cool! Essentially it will transform “simpler” DSL language to Graph structure defined as:

defmodule Graph do
  defstruct attrs: [], nodes: [], edges: []
end

Now, if there was only something we could use to generate the desired graph structure, but without having to write support for every node name, type etc…

Elixir macros to the rescue! I tend to think about them as code that writes code, but for this case another aspect is far more important. Namely, when using macros, all the code that lands into macro is quoted. The official documentation offers some pretty detailed information, but it basically boils down to two simple facts:

• code is represented as a tuple with specific structure that describes that code (that’s the “quote”)
• the quoted / described code is not evaluated at that time

Now this has some pretty nice implications. E.g. you can inspect all the code prior to deciding what to do with it, but also it prevents side effects from discarded code. You become the master of all code 😀

Excellent, what now? Well, aside from quoted thingy protection, the tuple that quotes input code can be pattern matched. The structure is always:

{atom | tuple, list, list | atom}

Let’s see how that relates to our graph DSL problem space. We have the following sentences:

graph [attributes]
node [nodes]
node -- other_node [attributes]

You can inspect those in iex, e.g.:

quote do: c -- d [color: :blue]

This results with:

{:--, [context: Elixir, import: Kernel], [{:c, [], Elixir}, {:d, [], [[color: :blue]]}]}

As you can see, you can then create matching patterns like:

{:--, _, [{a, _, _}, {b, _, [attrs]}]}

This pattern would match any relation with attributes, e.g. a — b [color: :blue] or a — c [label: “meta!”]. This little neat iex trick helps a lot, you can basically take any code, quote it, and see what is it actually made of. Kinda like Matrix, right?!

OK, so now we have our macro, we get the quoted graph DSL expression as argument, and we can pattern match parts of that quoted DSL to generate the desired output. Let’s build that graph:

defp build_graph({:graph, _, [attrs]}) do
  quote do: %Graph{attrs: unquote(attrs)}
end

Two things happen here:

• returning quoted result
• unquoting values

With macros it’s quite straight forward. You receive quoted code as attributes and you need to return quoted result back. Hence the quote do: in the above example.

Excellent, but what is that unquote thing? Well, it’s a way to inject dynamic values into quoted expressions. You can think of it as evaluating quoted code and interpolating it in the result. In the above example we’ve pattern matched a value, the attributes of the graph, and then used the unquote to inject them into the resulting graph structure.

So, now you know. Let’s see a partial implementation of our graph DSL:

defmodule Dot do
  defmacro graph(do: ast) do
    build_graph(ast)
  end

  defp build_graph({:__block__, _, graphs}) do
    graphs
    |> Enum.map(&(&1 |> build_graph |> Code.eval_quoted |> elem(0)))
    |> Enum.reduce(%Graph{}, &merge_graphs_sorted/2)
    |> Macro.escape
  end

  defp build_graph({:--, _, [{a, _, _}, {b, _, [attrs]}]}) do
    quote do: %Graph{edges: [{unquote(a), unquote(b), unquote(attrs)}]}
  end

  defp build_graph({:graph, _, [attrs]}) do
    quote do: %Graph{attrs: unquote(attrs)}
  end

  defp build_graph({node, _, [keywords]}) do
    quote do: %Graph{nodes: [{unquote(node), unquote(keywords)}]}
  end

  defp build_graph(_) do
    raise ArgumentError
  end
end

Most of the code looks familiar, but there are a few tricks 🙂

defmacro graph(do: ast)

is just a simplified way to parse a passing block to the macro. Let’s compare the quoted input to macro, when invoking it with e.g. Dot.graph do a [color: :green] end:

• [do: {:a, [line: 26], [[color: :green]]}] - using defmacro graph(ast)

• {:a, [line: 26], [[color: :green]]} - using defmacro graph(do: ast)

The difference is obvious, we’re just shortening our macro implementation.

defp build_graph({:__block__, _, graphs}) do

is there for processing multiple lines of input to our graphs DSL. Essentially, Elixir tells us that a block has been passed in, that’s the :__block__ atom part. All the lines in the block are part of graphs pattern matched variable. As you can see in it’s implementation, we’re basically invoking build_graph per block line and merging the results.

Code.eval_quoted

is used to evaluate the build_graph result, which is quoted of course. We need the resulting graph structure, so we can merge it into the resulting graph (the reduce section).

Macro.escape

is finally used to create quoted result, because that’s what we want to return from macro.

That is pretty much it. Working with macros is certainly not simple and follows it’s own rules. Even official documentation warns against abusing them too much, but they do have their place and certainly help with this kind of problems.

The complete example is available at exercism.io or github as well.

Resources:

• Elixir docs: Macros
• Elixir docs: Quote and unquote
• Elixir docs: Domain Specific Languages
• Understanding Elixir Macros, Part 1 – Basics
• Understanding Elixir Macros, Part 2 – Micro Theory
• Elixir metaprogramming example

Elixir Zipper, a Love Story

So this Zipper problem from Exercism.io got me a little busy! Aside from being very useful, it also served as a mind puzzle for quite a few days.

Can’t say why really, but I just couldn’t figure out how to model this problem. Since I haven’t been familiar with the concept before, I started by reading the Haskell document. And it was really fun and easy to understand, and the Greek mythology sketches where totally hilarious! But, when it came to actually implementing it, I kind of got stuck for a while. Maybe it had to do with how all those mathematical explanations and reading existing implementations in Haskell or Clojure or even Elixir mixed up and created much confusion in my head.

Then I took Gregory‘s advice and let it simmer for a week, without actually doing anything about it, and voilà, solved it today! Talking about Hammock Driven Development 😀

For the uninitiated, the zipper is a fancy data structure that allows you to go up and down a tree in a cheap and easy to track manner. Changes are allowed as well. And it is not limited to trees either!

So anyway, this will be more of an overview of specific points and why some of them created the confusion in the first place (and some still do).

To begin with, this particular Exercism.io problem tries to build a zipper for a binary tree structure:

@type bt :: %BT{
                value: any,
                left: BinTree.t | nil,
                right: BinTree.t | nil
               }

The initial question was how to actually structure the zipper record? By most definitions, a zipper record contains:

• node’s value
• left branch
• right branch
• trail

A trail might be something like:

@type trail :: :top
             | { :left, BT.t, trail }
             | { :right, BT.t, trail }

So trail is a recursive structure that keeps records of the traversal path. The current node’s trail is it’s context and it is customary to call that node the focus. I guess the focus means that you don’t actually change the tree, but rather the point at which you are viewing the tree structure from. Could be viewpoint as well 🙂 The Haskell document has a nice analogy here:

“Well, indeed you don’t need a thread. Another view is to literally grab the tree at the focus with your finger and lift it up in the air. The focus will be at the top and all other branches of the tree hang down. You only have to assign the resulting tree a suitable algebraic data type, most likely that of the zipper.” – Ariadne

My first point of confusion was the combination of list of zipper record properties and what I had in my mind after reading the descriptions. The Exercism.io hint mentioned all the properties and I thought about something like:

@type zipper :: {
                 left: BT.t,
                 right: BT.t,
                 value: any,
                 trail: trail
                }

After loosing some sleep on it, it finally occured to me that I already have many of the properties inside the BT structure! So, the final zipper looks like:

@type zipper :: { BT.t, trail }

Simple, not easy 😀

So now we have the zipper record that contains the node (BT.t) and the trail that says how we got to that node. Now we can do stuff like create zipper from a tree:

def from_tree(bt) do
  {bt, :top}
end

Or go left:

def left({%{left: left}, _}) when is_nil(left) do
  nil
end
def left({bt, trail}) do
  {bt.left, {:left, bt, trail}}
end

We can’t go left from the leftmost node, otherwise we create a new zipper record, containing the left node as the new focus and adding current focus to the trail. Similar solution goes for going right. An important thing to notice here, and the second thing that confused me, is to not think of “going left” as finding a sibling on the left, but rather finding the first child on the left branch. Funny how wrong interpretation of a simple term causes havoc!

Returning to some previous node is thusly considered as “going up”. It essentially means we need to go back in history, or rather follow our trail back one step:

def up({_, :top}) do
  nil
end
def up({_, {_, parent, trail}}) do
  {parent, trail}
end

We can’t go up from the top node, and for the rest we just return the parent and it’s trail as the new focus or point of view into the tree.

So now we can traverse the tree in any direction and this also gives us the ability to get the tree (from the root node) from any other node:

def to_tree({bt, :top}) do
  bt
end
def to_tree(zipper) do
  zipper |> up |> to_tree
end

As you can see, the traversal is rather cheap.

And now something completely different! We also need to be able to change the tree:

• by changing the focus node’s value
• by replacing focus node’s left branch
• by replacing focus node’s right branch

This is the point that got me confused the most. Namely, the hints and docs mention that the zipper record contains node’s value. So my initial attempts were are related to changing that part of the zipper, be it change of node’s value or one of it branches. This is how the trail portion looked at that time:

@type trail :: :top
             | { :left, any, BT.t, trail }
             | { :right, any, BT.t, trail }

Note the “any” part that represents the value. That is what is actually missing from the final solution. It occurred to me that since we have BT.t inside the zipper record, it would be just fine to update it’s value / structure directly. Here’s a first attempt:

def set_value({focus, trail}, new_value) do
  {focus | %{value: new_value}, value, trail}
end

This works nicely when you inspect the current focus. You get node’s new value, or it can even be applied to structure (replacing left or right branch) and it works from the perspective of the focus node. But, the problem arises when we try to fetch the resulting tree. Then, the focus is changed until we reach the top, and the top node doesn’t know about the change we made on the original focus node. So, then you get the original tree rather then the updated one.

I tried to figure out if that hinted “value” in zipper record could be used to save the day, but alas, no luck in that department. Then, after “deliberate rest period”, it dawned on me that the trail contains everything we need to make this work:

def set_value({focus, {direction, parent, trail}}, new_value) do
  focus = focus | %{value: new_value}
  {_, parent} = parent |> Map.get_and_update(direction, fn(focus_in_parent) ->
    {focus_in_parent, focus}
  end)
  {focus, {direction, parent, trail}}
end

So what is going on here? First we calculate the new value for the focus, that hasn’t changed. But, then we go to parent in the trail, and update it’s representation of the focus node to contain the updated value as well. Here the Map.get_and_update/3 greatly helps, since it allows us to fetch the focus node and update it at the same time. Note that we actually do know how to get the current focus in parent since we recorded it’s position during traversal. E.g. on going left, the trail recorded that :left, and we can use it now to get to our focus node in parent structure.

Finally, with a bit of refactoring to make the above function applicable to all updates, we can do something like:

def set_value(zipper, value) do
  update(zipper, value, :value)
end
def set_left(zipper, left) do
  update(zipper, left, :left)
end
def set_right(zipper, right) do
  update(zipper, right, :right)
end

And that’s it, we have a functional zipper for our binary tree structure! We can now do stuff like:

bt |> Zipper.from_tree |> Zipper.left |> Zipper.set_left(bt(6, leaf(7), leaf(8))) |> Zipper.to_tree
bt |> Zipper.from_tree |> Zipper.left |> Zipper.set_value(100) |> Zipper.to_tree

As always you can find the complete solution at Github, but feel free to inspect some other Exercism.io solutions as well:

All the Zipper solutions @ Exercism.io
Norbert Melzer’s solution
Kevin Smith’s solution
Zach Kemp’s solution

Zipper resources:

You could have invented zippers
Haskell/Zippers + Theseus and the Zipper Story
Gérard Huet. The Zipper. Journal of Functional Programming
Getting Acquainted With Clojure Zippers
Clojure Zippers: Structure Editing With Your Mind
Clojure Zipper
Roll Your Own Window Manager: Tracking Focus with a Zipper
ZipperTree – Elixir
Erlang port of Clojure’s Zipper by Inaka

Parallel Elixir Run

Last time we’ve managed to access a worker from multiple processes. This time, we’ll try to distribute worker’s load across several processes. The problem we’re trying to solve is to calculate occurrence of letters in given list of texts. There is no need for shared state, we just want to distribute the load. Hence, the Agent is not really needed. Task supports exactly what we need, the async call.

It works like this:

• invoke a job, asynchronously
• wait for job to finish and return results

And you have the corresponding methods:

• Task.async/1
• Task.await/2

Or, taken from the documentation:

task = Task.async(fn -> do_some_work() end)
res  = do_some_other_work()
res + Task.await(task)

Here, the important thing to notice is that you need to await for the result, and that both processes are linked so any crashes on either side will cause the other to fail as well. This suits our purpose quite nicely, so no worries there.

The above example shows how to spawn and await a single process. But, we’d like to spawn more, and distribute an unknown load evenly across those processes / workers, later collecting all of their results. And, funny enough, Enum.map/2 to the rescue!

@spec frequency([String.t], pos_integer) :: Dict.t
def frequency(texts, workers) do
  texts
    |> group_by(workers)
    |> Enum.map(fn(texts_for_a_worker) ->
      Task.async(fn -> count_frequencies(texts_for_a_worker) end)
    end)
    |> Enum.map(&(Task.await(&1, 10000)))
    |> merge_results
end

So, the actual magic happens with first Enum.map/2, which spawns a new worker and delivers it the texts to process and in the second Enum.map/2, which awaits each worker, mapping it’s results. The complete example is a bit more elaborate and can be found at Github.

So how much speed we’ve gained? To get a rough estimate, I’ve created a list of ten thousand short poems (through List.duplicate/2 on some national anthems, I’m not that eager to write poems yet!) and put it through the loops, while changing the number of workers. Here are some very much informal results:

• 1 worker – 12 seconds
• 4 workers – 5 seconds
• 16 workers – 5 seconds
• 32 workers – 5 seconds
• 128 workers – 5 seconds

I didn’t go so far as to inspect the reasons behind the top off, that might be an interesting exercise for later time. The take away is that we do have some significant gain compared to a single process, with little more code than usual, so it’s a win in my book 🙂

Elixir, Agent Elixir

So far, the exercism.io problems were fun to solve, but were contained within single process domain. The Bank Account problem opens up a new dimension 🙂

The task is rather simple: create a simplistic bank account manager that can open or close a bank account, query it’s balance and deposit to / redraw from it. The catch is, it needs to support access from multiple processes. Finally some distributed action!

The main issues here are:

• how to communicate with other processes
• how to keep state in sync

There are a number of techniques at our disposal, like ETS (Erlang Term Storage), GenServer or we can wire our own as described in docs about state in processes. The main thing to understand is that we actually only need message passing between processes to complete this task, with a little help from the Agent (sorry Neo :-)).

What we want to do is:

• spawn a new Agent
• remember it’s pid
• perform all account management operations using that pid
• stop Agent when done

The Agent’s pid serves as our account number for this simple exercise.
The simplest solution could look like this:

defmodule BankAccount do
  @opaque account :: pid

  @spec open_bank() :: account
  def open_bank() do
    Agent.start_link(fn -> 0 end) |> elem(1)
  end

  @spec close_bank(account) :: none
  def close_bank(account) do
    Agent.stop(account)
  end

  @spec balance(account) :: integer
  def balance(account) do
    Agent.get(account, &(&1))
  end

  @spec update(account, integer) :: any
  def update(account, amount) do
    Agent.update(account, &(&1 + amount))
  end
end

What goes on is, when we open the bank account, Agent is started and linked to current process and we just need to store it’s pid, that acts as our account number, for future account operations.

Spawning an Agent requires only a single function, one that initializes the state. Agent then exposes get/3 and update/3 which can be used to change the state accordingly. All those state manipulating functions expect earlier stored pid, so they can access the related Agent, plus a function that operates on the state.

Very very simple and straight forward. It hides the underlying stuff like processes, message passing and message receiving in a nice manner and really allows us to concentrate on the business side of things. Much appreciated, and kind of justifies the hipe 🙂

And testing this isn’t much of a problem either!

setup do
  account = BankAccount.open_bank()
  { :ok, [ account: account ] }
end

test "incrementing balance from another process then checking it from test process", context do
  assert BankAccount.balance(context[:account]) == 0
  this = self()
  spawn(fn ->
    BankAccount.update(context[:account], 20)
    send(this, :continue)
  end)
  receive do
    :continue -> :ok
  after
    1000 -> flunk("Timeout")
  end
  assert BankAccount.balance(context[:account]) == 20
end

Basically, it just spawns a new process that makes a deposit to our bank account and then notifies of job completion (line 11 in the above code). The main test process is set to receive a message of type :continue (line 14) after which it can verify that the deposit has been made indeed.

This message passing between main test process and spawned one is the key to all distributed computing in Elixir / Erlang. Even without Agent’s help, it looks and works quite nicely.

The entire code can be found at Github.

Unfolding Elixir

WARNING: not for the allergy prone people! 🙂

Last Elixir problem from exercism.io was related to how to detect stuff a person is allergic to, based on her allergy index / flags.

For example, given these allergens:

@allergens %{
  1 => "eggs",
  2 => "peanuts",
  4 => "shellfish",
  8 => "strawberries",
  16 => "tomatoes",
  32 => "chocolate",
  64 => "pollen",
  128 => "cats"
}

A person with allergy index 5 would be allergic to eggs and shellfish.

Since index flags are powers of two, a simple solution is:

import Bitwise

def allergic_to(flags) do
  @allergens |> Enum.filter(fn({flag, _}) ->
    (flags &&& flag) != 0
  end) |> Dict.values
end

This uses the Bitwise.&&&/2 bitwise AND operator, and it works 😀

But, what originally came to my mind was something like this (pseudo code):

• take first allergen who’s value is lesser or equal to person’s allergy index / flags
• deduct allergen’s value from allergy index and add it to the list
• repeat until remaining value reaches zero

So, for the sake of exercise (this is exercism.io after all), I wanted to see how this could be implemented. Enum.reduce/3 was the initial thought, but it can’t really work since collection elements are visited only once. Here’s the code that works for most cases:

def allergic_to(flags) do
  @allergens |> Enum.reverse |> Enum.reduce({[], flags}, fn({flag, allergen}, {allergies, remaining}) ->
    if flag <= remaining do
      {[allergen | allergies], remaining - flag}
    else
      {allergies, remaining}
    end
  end) |> elem(0)
end

Unfortunately, it gives the wrong result for allergic index 509 for example.

Namely, it traverses allergens 128, 64 etc. in sequence and this includes peanuts as well. But, the idea was to reuse a specific allergen as long as it’s value is lesser than or equal to the remaining allergic index.

So, the formula should actually be: 509 – 128 = 381 – 128 = 253 – 128 = 125 – 64 = 61 – 32 = 29 – 16 = 13 – 8 = 5 – 4 = 1 – 1 = 0. And, the allergens would be 128, 64, 32, 16, 8, 4 and 1. Allergen 2, peanuts, would be excluded.

So, I needed a way to turn allergic index and allergens into a loop that could reuse allergens as needed.

Stream.unfold/2 to the rescue! Basically, it can turn anything into a stream, since you define a starting point and a function that calculates the next value. As long as you don’t return nil, the stream continues. And because of the next function, it is as flexible as you want it to be.

With that in mind, here’s what the Stream.unfold/2 solution looks like:

def allergic_to(flags) do
  Stream.unfold({flags, @allergens |> Enum.max |> elem(0)}, fn({_, 0}) -> nil; ({remaining, flag}) ->
    if flag <= remaining do
      {@allergens[flag], {remaining - flag, flag}}
    else
      {nil, {remaining, Bitwise.bsr(flag, 1)}}
    end
  end) |> Enum.to_list |> Enum.reject(&(!&1))
end

It’s not beautiful or easy to read as the Bitwise.&&&/2 solution, but, as mentioned before, this was just an exercise and a nice way to see how Stream.unfold/2 works.

As always, you can find the entire code at Github.

Elixir Function Headers

While playing with the new exercise.io problem, the prime factorization of a number, I came across an interesting feature in Elixir.

I tried defining a couple of incarnations of pattern matched function with default values, like this:

defp decompose(1, divisor \\ 2, acc \\ []) do
  ...
end

defp decompose(number, divisor \\ 2, acc \\ []) do
  ...
end

But, that did not do well with Elixir compiler. It seems you need to add an empty clause, sort of a function header, as explained in this Github issue:

# function header / empty clause
defp decompose(number, divisor \\ 2, acc \\ [])

defp decompose(1, divisor, acc) do
  ...
end

defp decompose(number, divisor, acc) do
  ...
end

And then, only that empty clause requires default values. Nice to know!

Elixir fun continues

These last few days I’ve continued the Elixir exercises journey on exercism.io:

• gigasecond
• triangle
• scrabble score
• roman numerals

Nothing fancy there, but I still picked up a few tricks. So, in no particular order 🙂

If you use map, the ordering of keys is not maintained as with keyword lists.
Also, there is a way to pass anonymous function to pipe as well! Behold:

defmodule Roman do
  @roman_values [
    {1000, "M"},
    {900, "CM"},
    {500, "D"},
    {400, "CD"},
    {100, "C"},
    {90, "XC"},
    {50, "L"},
    {40, "XL"},
    {10, "X"},
    {9, "IX"},
    {5, "V"},
    {4, "IV"},
    {1, "I"}
  ] # using keyowrd list instead of map because ordering is important

  @doc """
  Convert the number to a roman number.
  """
  @spec numerals(pos_integer) :: String.t
  def numerals(0) do
    ""
  end
  def numerals(number) do
    @roman_values |> Enum.find(fn({arabic, roman}) -> number >= arabic end) |> fn({arabic, roman}) ->
      roman <> numerals(number - arabic)
    end.()
  end
end

Method signature doesn’t have to match the arguments:

defmodule Gigasecond do
  @doc """
  Calculate a date one billion seconds after an input date.
  """
  @spec from({{pos_integer, pos_integer, pos_integer}, {pos_integer, pos_integer, pos_integer}}) :: :calendar.datetime
  def from(datetime) do
    datetime
      |> :calendar.datetime_to_gregorian_seconds
      |> +(1_000_000_000)
      |> :calendar.gregorian_seconds_to_datetime
  end
end

Short but sweet and still very much fun 🙂

Elixir on the run

Continuing with Elixir problems from exercism.io, this time something completely different 😀
It’s a variation of the chess board and grains of wheat story, and basically you need to create a function that returns the total number on the chess board, along with one that returns the number of grains on given square. Not much to it, just return 2 to the power of desired square – 1 and that’s it:

def square(number) do
  :math.pow(2, number - 1) |> round
end

So this works, but there are a few issues. And one of those is nicely mentioned in tests:

NOTE: :math.pow/2 doesn’t do what you’d expect:
`:math.pow(2, 64) == :math.pow(2, 64) – 1` is true.
It’s best to avoid functions operating on floating point numbers for very large numbers.

Also, this solution throws “(ArithmeticError) bad argument in arithmetic expression” for large numbers, e.g. 32768. So, off to seek another solution. Enum.reduce/2 to the rescue:

def square(number) do
  1..number |> Enum.reduce(fn(x, acc) -> acc * 2 end)
end

It returns correct results, but for very large numbers it is rather slow. E.g. 1.2 seconds for square(262144). So, Jim Menard offered a nice solution:

use Bitwise

def square(number) do
  bsl(1, number - 1)
end

One forgets that multiplying by 2 is equal to bit shift left operation. And, of course, there is the related Bitwise.bsl/2 method that does just that. Now the square(262144) runs as fast as square(1). Who says Elixir/Erlang isn’t fast! 😀

Wishful types

In the last exercise, there was some redundancy in the code I wished to eliminate.
For example, there is a type definition that defines possible week days:

@type weekday ::
  :monday |
  :tuesday |
  :wednesday |
  :thursday |
  :friday |
  :saturday |
  :sunday

So, someone invoking the meetup date calculation, would have to use one of the valid atoms for the desired day in the week.

Now, to match those agains Erlang’s calendar.day_of_the_week/1, I needed a way to match say :wednesday to 3, since day_of_the_week returns day number, not the atom fom above type.

An easy solution:

@weekdays %{
  :monday => 1,
  :tuesday => 2,
  :wednesday => 3,
  :thursday => 4,
  :friday => 5,
  :saturday => 6,
  :sunday => 7
}

No magic there, just repeat the atoms, map values from day_of_the_week on them, and off we go.

But, it would be much nicer if I could just do:

@weekdays weekday |> Enum.with_index(1) |> Enum.into(%{})

That would produce the exact same map, just in a dry way.

Another thing that could benefit from the same pattern was the schedule policy filtering.
So, say that we have a few functions we would like to map to a constant in the module and use like this:

@type schedule ::
  :first |
  :second |
  :third |
  :fourth |
  :last |
  :teenth

@schedules %{
  :first => &first/1,
  :second => &second/1,
  :third => &third/1,
  :fourth => &fourth/1,
  :last => &last/1,
  :teenth => &teenth/1
}

defp filter_by_schedule(dates, schedule) do
  @schedules[schedule] |> apply([dates])
end

defp first(dates) do
  dates |> hd
end

defp second(dates) do
  dates |> Enum.at(1)
end

defp third(dates) do
  dates |> Enum.at(2)
end

defp fourth(dates) do
  dates |> Enum.at(3)
end

defp last(dates) do
  dates |> Enum.reverse |> hd
end

defp teenth(dates) do
  dates |> Enum.find(fn({_, _, day}) ->
    day >= 13 && day <= 19
end)
end

That way, the @schedules map would be a constant, and the code would be much cleaner. Also, it would be nice if I could also:

 @schedules schedule |> Enum.map(fn(sch) -> %{sch => __info__(:functions)[sch]} end) |> Enum.into(%{})

Unfortunately, couldn’t find a way to acomplish this. So, if you have any suggestions, I’m all ears!