FPOO Ch. 9: Functions That Make Functions

[boilerplate bypath=”fp-oo”]

Unlike Clojure, as far as I know Elixir does not have a library of foundational higher-order functions such as like lift or complement. So I’ll have to build them myself.

Before I do anything else, I need a helper function for adapting the arity of anonymous functions. This is because Elixir has no support for variable-arity functions. As a result, the only workable way I can find to build generic functions involves always returning a function of a single argument, where the single argument is a list of the actual arguments. Which can then be used with apply, etc.

This works, but it’s pretty unpleasant to have to call all generated functions as, e.g. add2.([2]) instead of add2.(2). Not to mention that in order to be composable, any function-modifying-function would have to have two versions: one that accepts a “normal” function of N arguments, and one that takes a function of single argument list.

So instead I define adapt_arity, which takes a function of one argument and an arity, and returns a function of arity arguments.

I spent a few days off and on trying to come up with a clean macro version of this, but I completely struck out. The problem I kept running into is that the macro is evaluated at compile time, but the arity number is only discovered at runtime. Eventually I reluctantly settled on using Code.eval_string instead.

@doc """
   iex> myfun = fn(args) -> args end
   iex> myfun3 = adapt_arity(myfun, 3)
   iex> myfun3.(:a, :b, :c)
   [:a, :b, :c]
   iex> myfun2 = adapt_arity(myfun, 2)
   iex> myfun2.(:x, :y)
   [:x, :y]
"""
def adapt_arity(fun, arity) do
  arglist = (0..arity - 1) |> Enum.map(fn(n) -> "arg#{n}" end) |> Enum.join(", ")
  code = """
    fn(#{arglist}) ->
      args = [#{arglist}]
      fun.(args)
    end
  """
  {value, _binding} = Code.eval_string(code, binding, __ENV__)
  value
end

(I even tried a version that eval-ed code at compile time to generate 256 different versions of adapt_arity, but then I ran into an issue where I couldn’t get the Code.eval_* functions to eval in the context of a given module. Instead they were evaluating in the global(?) context, and functions can’t be defined outside a module.)

UPDATE: Where I failed, meh succeeded. Check out this masterful rewrite using macros instead of evaluation: https://gist.github.com/meh/7990856/c59f69216418e27bd01f43f47262af6870c8874a

UPDATE: José Valim weighs in with an unrolled version that actually works, unlike my attempt: https://gist.github.com/josevalim/ea084b59f88de1ab6d35

Here’s the gist from meh, updated with the compile-time unrolling approach: https://gist.github.com/meh/7990856

Given a call like this:

adapt_arity(myfun, 3)

The following anonymous function will be returned from adapt_arity:

fn(arg0, arg1, arg2) ->
  args = [arg0, arg1, arg2]
  myfun.(args)
end

I also define a helper function to discover the arity of a given anonymous function.

@doc """
    iex> arity(&Kernel.even?/1)
    1
    iex> arity(&Kernel.+/2)
    2
"""
def arity(fun) do
  (0..255) |> Enum.find fn(arity) -> is_function(fun, arity) end
end

The magic number 255 corresponds to the upper bound of arguments an Erlang function can take.

So far as I can tell there’s no built-in way to check the arity of a function. This was the best I could come up with. I suspect this could be made more efficient by unrolling it into a pattern-matching version, if someone really wanted to.

UPDATE: On IRC, meh pointed me to the fun_info, which simplifies this function considerably.

@doc """
    iex> arity(&Kernel.even?/1)
    1
    iex> arity(&Kernel.+/2)
    2
"""
def arity(fun) do
  {:arity, value} = :erlang.fun_info(fun, :arity)
  value
end

Now on to the various function adapters. First up, partial.

@doc """
    iex> add2 = partial(&Kernel.+/2, [2])
    iex> add2.(4)
    6
"""
def partial(fun, partial_args) do
  arity = arity(fun) - length(partial_args)
  fn(args) -> apply(fun, partial_args ++ args) end |> adapt_arity(arity)
end

Next, complement.

@doc """
    iex> not_even = complement(&Integer.even?/1)
    iex> not_even.(2)
    false
    iex> not_even.(3)
    true
"""
def complement(fun) do
  fn(args) -> !apply(fun, args) end |> adapt_arity(arity(fun))
end

And now lift, which effectively turns a function into a function modifier.

@doc """
    iex> negate = lift(&Kernel.-/1)
    iex> neg_add = negate.(&Kernel.+/2)
    iex> neg_add.(2, 2)
    -4
"""
def lift(modifier) do
  fn(base_function) ->      
      fn(args) -> 
          result = apply(base_function, args)
          modifier.(result)
      end |> adapt_arity(arity(base_function))
  end
end

Finally, comp, to compose N functions together.

@doc """
    iex> plus = &Kernel.+/2
    iex> add = &Enum.reduce(&1, plus)
    iex> comp([&Kernel.to_string/1, add]).([8, 8, 8])
    "24"
"""
def comp(funs) do
  rfuns = funs |> Enum.reverse
  arity = arity(funs |> Enum.first)
  rfuns |> Enum.reduce fn(outer, inner) ->
                           fn(args) ->
                               outer.(apply(inner, args))
                           end |> adapt_arity(arity(inner))
                       end
end

The compact code for comp doesn’t really reflect the amount of brain pain that went into working it out. For some reason I have a hard time reasoning about reductions involving function composition.

Oops, one more: juxt.

@doc """
    iex> juxt([&Enum.empty?/1, &Enum.reverse/1, &Enum.count/1]).([:a, :b, :c])
    [false, [:c, :b, :a], 3]
"""
def juxt(funs) do
  fn(arg) ->
      funs |> Enum.map(fn(fun) -> fun.(arg) end)
  end
end

Exercise 1 challenges me to write a function that adds 2 to each element of a sequence, using a point-free style (no fn allowed).

This would be easy enough with just the capture (&) operator, but since I’ve got a shiny new partial function, I’ll use it.

test "add 2 to each element, using a point-free style" do
  result = [1,2,3] |> Enum.map(partial(&Kernel.+/2, [2]))
  assert result == [3,4,5]
end

This might draw the question “if the capture operator would have worked just as well, what’s the point of partial?” The answer is genericity. partial can be used within other functions where the number of partial arguments to be supplied isn’t known until runtime. That’s not possible with captures.

Exercise 2 is to write a separate function using juxt.

@doc """
    iex> separate([0,1,2,3], &Integer.odd?/1)
    [[1,3], [0,2]]
"""
def separate(list, pred) do
  juxt([&Enum.filter(&1, pred), &Enum.reject(&1, pred)]).(list)
end

Exercise 6 is to write always, a function that generates functions that always return a constant value regardless of arguments. As usual, Elixir complicates things by requiring an explicit arity.

@doc """
    iex> eight = always(8, 3)
    iex> eight.(1,2,3)
    8
"""
def always(value, arity) do
  fn(_) -> value end |> adapt_arity(arity)
end

Exercises 7 and 8 deal with validating ISBNs.

@doc """
    iex> check_sum([4, 8, 9, 3, 2])
    69
"""
def check_sum(digits) do
  import Enum
  digits 
  |> zip(1..length(digits))
  |> reduce(0, fn({digit, index}, sum) ->
                   sum + (digit * index)
               end)
end
@doc """
    iex> isbn?("0131774115")
    true
    iex> isbn?("0977716614")
    false
    iex> isbn?("1934356190")
    true
"""
def isbn?(num) do
  digits = String.graphemes(num) |> Enum.map(&binary_to_integer/1)
  rem(check_sum(digits), 11) == 0
end

And that’s enough for now.