Hardly Functional

August 11, 2013

Is Thinking Functionally a Black Art?

As I explained in a previous post, I have been writing a genetic algorithm to find the best layout of a keyboard based on a set of ergonomic principles. I decided to write the program in both Go and Elixir as a way to “learn me some new programmings languages for the greater good”. Writing the Go program went very smoothly. I had a good working program in just over a day’s work. The Elixir code on the other hand has taken me close to three days and I am still trying to work out issues. I attribute most of this long spell to the paradigm shift one must make when switching from a procedural to a functional way of doing things.

I have two examples from my work that I think demonstrate the difficultly of this shift.

Originally I had written the following code:

    def evolve(gen) do
      :random.seed

      best = 0
      size = 16

      pop = random_keyboards(size)

      Enum.reduce (1 .. gen), pop, fn(i, p) ->
        newpop = List.concat(breed(p), p)
        newpop = natural_selection(newpop, size)

        first = Enum.at(childs, 0)
        display(first)

        if best < first.score do
          best = first.score
          size = 16
        else
          size = size + 2
        end         

        newpop
      end
    end

It all seemed rather reasonable to me. Turns out however, Elixir thought otherwise:

variable best is unused
variable size is unused

My procedural mindset was geared toward the idea of using variables to track a state while iterating around in a loop. But for a functional language this is not the correct way to think about the problem. By reassigning best and size within the reduce block function I was in effect creating new variables, not reassigning the ones defined outside.

The solution, as is the case with many such procedural conversions, is to think recursively.

    def evolve(gen) do
      :random.seed
      evolve(gen, random_keyboards(16), 16, 0)
    end

    def evolve(gen, pop, size, best) do
      if gen == 0 do
        pop
      else
        newpop = List.concat(breed(p), p)
        newpop = natural_selection(newpop, size)

        first = Enum.at(childs, 0)
        display(first)

        if best < first.score do
          evolve(gen - 1, newpop, 16, first.score)
        else
          evolve(gen - 1, newpop, size + 2, best)
        end         
      end
    end

After working this out, a part of me has to agree the fanboys of functional languages. This does smack of an certain elegance that the procedure solution lacks. The solution is also efficient thanks to tail recursion, which avoids the usual call stack overhead of repeatedly calling nested functions.

But then there was the routine that I have yet to figure out how to do in a more functional way. To get the following routine to work I basically had to make Elixir behave much like a procedural language –running in a loop shuffling list indexes around.

    def cross(mother, father) do
      offset = 0

      if numeric_layout?() do
        offset = 9
      end

      n = number_of_actions(1)  # 0 or 1

      child_layout = Enum.reduce (0 .. n), mother.layout, fn(_, c) ->
        i = :random.uniform(length(c) - offset - 1) + offset
        l = Enum.at father.layout, i
        x = Enum.find_index(c, fn(q) -> q == l end)
        if x do
          swap(c, x, i)
        else
          c  # should generally never happen
        end
      end

      make_keyboard(mutate(child_layout))
    end

Perhaps it is inevitable that some procedural-esque code will always be present. In fact, that is the one caveat about functional programming that makes me wonder if maybe it’s not quite all that. Some problems, that are relatively easy to solve in a traditional procedural language, seem markedly harder to solve functionally.

← All posts