Elixirで再帰とかメモ化とかZコンビネータとか

Elixirを軽く触ってみたのでその備忘。

#とりあえず再帰

定番のフィボナッチで試した。

defmodule Fib do
  def get(0), do: 0
  def get(1), do: 1
  def get(x), do: get(x-1) + get(x-2)
end

Fib.get(10) #=> 55

Haskelのように関数の引数の値でパターンマッチできるのが素敵。
ただ、この作りだと40位が限界。
50だと帰ってこない。

#末尾再帰を試す

再帰の高速化の基本は末尾再帰。
ということで書き直し。

defmodule TailFib do
  def get(x), do: get(x, 0, 1)
  defp get(0, x, _), do: x
  defp get(n, x, y), do: get(n-1, y, x+y)  
end

TailFib.get(10) #=> 55

100000渡しても一瞬で帰ってくるようになった。

#無名関数で再帰
高速化のもうひとつの手法、メモ化にあたり無名再帰をしたくなったので試してみた。

ElixirにはJavaScriptのarguments.calleeのような自分自身を参照する術がないため、Zコンビネータを使った。

とりあえず無名再帰

fib = fn f ->
  fn x ->
    x.(x)
  end.(
    fn x ->
      f.(&(x.(x).(&1)))
    end
  )
end.(fn f ->
  fn 
    0 -> 0
    1 -> 1
    x -> v = f.(x-1) + f.(x-2)
  end
end)

fib.(10) #=> 55

無名末尾再帰

tailfib = fn n -> fn f ->
  fn x ->
    x.(x)
  end.(
    fn x ->
      f.(&(x.(x).(&1, &2, &3)))
    end
  )
end.(fn f ->
  fn 
    0, x, _ -> x
    n, x, y -> f.(n-1, y, x+y)
  end
end).(n, 0, 1) end

tailfib.(10) #=> 55

#メモ化
一番最初のコード（とりあえず再帰）の処理構造はそのままに、メモ化を入れてみた。
Elixirは基本Imutableのため別プロセスにMapを突っ込んで状態を持つ。
標準では自動メモ化はないようなので、Zコンビネータ内に組みこんで汎用っぽくしてみた。
このMemoZは再帰処理内で同じ引数が繰り返し多く現れるケースでは使えるはず。
一応プロセスリークもしないようにした。

defmodule MemoZ do
  def init(f) do
    fn x ->
      {:ok, pid} = Agent.start_link &Map.new/0
      try do
        fix(pid, f).(x)
      after
        Agent.stop pid
      end
    end
  end

  defp fix(pid, f) do
    fn x ->
      x.(x)
    end.(
      fn x ->
        f.(&(get_or_else_update(pid, &1, fn -> x.(x).(&1) end)))
      end
    )
  end

  defp get_or_else_update(pid, k, f) do
    case Agent.get(pid, &Map.get(&1, k)) do
      nil ->
        v = f.()
        Agent.update(pid, &Map.put(&1, k, v))
        v
      v -> v
    end    
  end
end

memofib = MemoZ.init(fn f ->
  fn 
    0 -> 0
    1 -> 1
    x -> f.(x-1) + f.(x-2)
  end
end)

memofib.(10) #=> 55

末尾再帰版程ではないがとりあえず再帰版より全然早い。

##コイン両替の可能な組み合わせ問題のメモ化
フィボナッチだけだとメモ化モジュールの汎用性がわからなかったため、コイン両替の可能な組み合わせ問題も試してみた。

###コイン両替の可能な組み合わせ問題（メモ化無し）

defmodule Coin do
  def calc(0, _), do: 1
  def calc(_, []), do: 0
  def calc(n, _) when n < 0, do: 0
  def calc(n, [h|t]) do
    calc(n, t) + calc(n-h, [h|t])
  end
end

Coin.calc(1000, [1,5,10,50,100,500]) # => 248908

普通に書くとこんな感じ。
1000円の両替パターンで10秒くらいかかった。

###コイン両替の可能な組み合わせ問題（メモ化）

coin = MemoZ.init(fn f ->
  fn 
    {0, _} -> 1
    {_, []} -> 0
    {n, _} when n < 0 -> 0
    {n, [h|t]} -> f.({n, t}) + f.({n-h, [h|t]})
  end
end)

coin.({1000, [1,5,10,50,100,500]}) # => 248908

複数引数はタプルで逃げた。
1秒かからず返ってきた。

#マクロを試す
無名再帰をマクロでやる方法をk1さんが示してくれていたのでメモ化再帰と組み合わせてみた。

defmodule MemoLoop do
  defp traverse(block, f) do
    r = f.(block)
    cond do
      is_tuple(r) -> r |> Tuple.to_list |> traverse(f) |> List.to_tuple
      is_list(r) -> r |> Enum.map(&(&1 |> traverse(f)))
      true -> r
    end
  end

  defmacro loop(p, do: block) do
    quote do
      MemoZ.init(fn f -> fn x -> case x do
        unquote(block |> traverse(fn
          # `recur(args)` -> `f.(args)`
          {:recur, meta, args} -> {{:., meta, [quote do f end]}, meta, args}
          other -> other
        end))
      end end end).(unquote p)
    end
  end
end

import MemoLoop
loop 10 do
  0 -> 0
  1 -> 1
  x -> recur(x - 1) + recur(x - 2)
end #=> 55

ちょっとすっきりした。
マクロの展開の様子は下記のようにして確認できる。

quote do loop 10 do
  0 -> 0
  1 -> 1
  x -> recur(x - 1) + recur(x - 2)
end end |> Macro.expand(__ENV__) |>  Macro.to_string |> IO.puts

↓ 出力内容

MemoZ.init(fn f -> fn x -> case(x) do
  0 ->
    0
  1 ->
    1
  x ->
    f.(x - 1) + f.(x - 2)
end end end).(10)

#ソース
https://github.com/bakenezumi/memoz

#所感
乗り遅れた感は大分あるが関数型言語としてはまとまっている印象。
endがいるのがちょっと苦手だけど楽しく書けた。
マクロは強力だけどデバッグが大変。