Tower of Hanoi

Tower of Hanoi is a recurrent mathematical problem. In recurrence, the solution to each problem depends on the solutions to smaller instances of the same problem.

I'd solved this problem a few years ago. But now, since we talk about functional programming, I decided to solve the problem using Elixir.

Read more about the problem statement here: Tower of Hanoi.

If you want to try it interactively, go here.

Here is my solution:

defmodule TowerOfHanoi do

  def move(1, source, destination, intermediate) do
    IO.puts ["Move ", source, " to ", destination]
  end

  def move(no_of_disks, source, destination, intermediate) do
    move(no_of_disks - 1, source, intermediate, destination)
    IO.puts ["Move ", source, " to ", destination]
    move(no_of_disks - 1, intermediate, destination, source)
  end

end

I'm updating my GitHub repository (yedhukrishnan/mathematics) with more math problems. Feel free to check them out to suggest improvements or to give comments.

Recursion (Part 1)

Unlike in imperative languages, functional programming languages (including Elixir) achieve looping through recursion. Why? To explain that, let's consider C:

for(i = 0; i < 5; i++) {
  sum = sum + i;
}

Here we are modifying (mutating) the value of i as well as sum in each interation. Mutation is considered as a bad practice and functional programming languages do not encourage it. Let's see some basic examples of recursion in Elixir.

Say, we want to print the message "hello" five times. How do we do that?

defmodule Recursion do
  def print_hello(n) when n <= 1 do
    IO.puts "hello"
  end

  def print_hello(n) do
    IO.puts "hello"
    print_hello(n - 1)
  end
end

Recursion.print_hello("Hello!", 3)
# Hello!
# Hello!
# Hello!

Here, defmodule is used to define a module (group of several functions). We can have multiple definitions of the same function. In the first function when n <= 1 is a guard. This function will get executed only when the guard condition is satisfied (no wonder why it is called a guard!). When there are multiple clauses (definitions) of the same function, Elixir looks for a match and executes it when it finds one. If no matches are found, it will throw error.

In this case, when n = 3 and n = 2, the second clause will be executed. When n = 1, the first clause will get executed. 

Read more:

• Modules
• Recursion

Elixir Language (Part 5)

Binaries

In the last section, we talked about representing strings as UTF-8 encoded binary. But we left a topic for this section: How a character having code point above 255 is represented in binary?

Well, we all know that a single byte can only hold a value between 0 and 255. Let's consider the string hełło. Here ł has a code point 322.

This is where UTF-8 comes into picture. It solves the problem by using 2 bytes to represent each ł, and one byte each to represent h, e and o.

iex> string = "hełło"
"hełło"
iex> byte_size string
7
iex> String.length string
5

Here, we can see that the byte size of the string is 7 while the string length is 5. The function byte_size/1 can be used to check how many bytes are actually used in the memory to represent the given string.

Read more: Binaries, strings and char lists

Elixir Language (Part 4)

Binaries

In Elixir, strings are UTF-8 encoded binaries.

What is a binary?

A binary is just a sequence of bytes.  By default, each character in a string is internally represented in memory using 8 bits.

Let's take a simple example. The string "hello" in UTF-8 encoded binary form is 104, 101, 108, 108, 111. As you can see, each character uses a number (code point) between 0 and 255, which is represented with 8 bits or 1 byte.

You can define a binary using <<>> as shown below.

iex> <<0, 1, 2, 3>>
<<0, 1, 2, 3>>

We have the string concatenation operator <> in Elixir, which is actually a binary concatenation operator.

iex> "hello" <> "world"
"helloworld"
iex> <<0, 1, 2, 3>> <> <<4>>
<<0, 1, 2, 3, 4>>

Let's see "hello" in Elixir's binary form:

iex> "hello" <> <<0>>
<<104, 101, 108, 108, 111, 0>>

Here, I just used a concatenation operator to append a binary to a string. It converted the string to its internal binary representation.

The unicode standard assigns code points to many of the characters we know. For example, a has code point of 97. Here, as you can see, h has a code point of 104.

All commonly occuring characters have code points between 0 and 255. But there are characters whose code points are above 255, which cannot be represented in memory using a single byte. In the next post, I'll explain how they are represented and stored in memory.

Read more: Binaries, strings and char lists

Elixir Language (Part 3)

The Match Operator

In Elixir, we use = operator to assign value to a variable:

iex> x = 1
1

What's the big deal? Well, in Elixir, = is not just an assignment operator. It's a match operator.

iex> x = 1
1
iex> 1 = x
1

As long as the left hand side and the right hand side are equal, Elixir will not complain. But when a mismatch occurs, it raises a MatchError:

iex> 1 = x
1
iex> 2 = x
** (MatchError) no match of right hand side value: 1

For assigning value to a new variable, the variable should always be on the left hand side of the operator.

The match operator can be used to destructure complex data structures into its components. Here is an example where Elixir uses pattern matching on a list:

iex> [a, b, c] = [1, 2, 3]
[1, 2, 3]
iex> a
1

Here is a common question that pops up in mind when we talk about the match operator. If we are using the expression x = 1 in Elixir. How does elixir know whether we want to do a match or assignment? 

By default, Elixir always performs assignment if the variable is on the left hand side. If you specifically want to perform match, you can use the pin operator (^).

iex> x = 1
1
iex> ^x = 2
** (MatchError) no match of right hand side value: 2

Here I explained the parts which I liked the most in Elixir. This is only meant for an introduction into the language. All the examples are taken from the Elixir's getting started guide. 

Read more and learn here: Elixir: Pattern Matching

Elixir Language (Part 2)

Here are the few things I liked about the language at the first glance:

Lists and Tuples

Square brackets are used in Elixir to specify a list of values. They can hold values of multiple data types. 

iex> [1, 2, true, :atom, 3]
[1, 2, true, :atom, 3]

They are represented in memory using linked lists. This means accessing the length of a list is a linear operation.

Tuples, unlike lists, store elements contigiuously in memory. They can also hold values of any type.

iex> {:ok, "hello"}
{:ok, "hello"}

Short-Circuit Operators: and, or

By default, and and or operators are short-circuit operators in Elixir. That means, the right hand side of these operators will be executed only if the left hand side is not enough to determine the result.

iex> false and error("This error will never be raised")
false

iex> true and error("This error will never be raised")
** (RuntimeError) undefined function: error/1

Here, the first expression returns false because 'false and anything' is always false. But in the second part, the left hand side is not enough to get the result. Hence, it tries to execute the right hand side, and it fails because there is no function called error/1.

In the next part, I'll share what I learned and liked about the match operator in Elixir.

Read more:

• (Linked) Lists
• Tuples
• Basic Operators
• Short-Circuit Evaluation (wikipedia)

Elixir Language (Part 1)

After listening to the Introduction into Elixir language, by Dave Thomas, in Bangalore Ruby Users Group meetup, I always wanted to learn the language, or at least functional programming part of it. I did a failed attempt the same day evening! Yesterday, I started again with the tutorials. I am sharing some of my learnings here.

Elixir Language

Elixir is a simple, easy to learn functional programming language build on top of Erlang VM. It is a dynamic language which allows metaprogramming and can be used for building concurrent, distributed and fault-tolerant applications with hot code upgrades.

Installing Elixir in Ubuntu/Debian

The only prerequisite for installing Elixir is Erlang, version 17 or later. Precompiled packages are available in Erlang Solutions website. Follow the instructions on their website to install Erlang. Then, install Elixir by cloning their repository and generating binaries:

$ git clone https://github.com/elixir-lang/elixir.git
$ cd elixir
$ make clean test

Make sure to add the bin directory to the PATH environment variable ( Add it to ~/.bashrc file for bash, ~/.zshrc file for ZSH ... )

$ export PATH="$PATH:/path/to/elixir/bin"

This is a distilled version of installation instructions for Debian/Ubuntu users (like me!). Refer the original version for detailed instructions.

In the next part, I'll share the basic constructs I liked in Elixir language on the first day of learning.

References: 

• Elixir: Getting Started Guide
• Elixir Primer and Resources
• Elixir (Programming Language)