今日の風景

f:id:nisemono_san:20161106011717j:plain

知っている人から知らないものをさしいれでいただきました。

f:id:nisemono_san:20161106011727j:plain

ところで、みなさんは完全ですか?

はじめに

知人が唐突に「これからElixirやっていくぞ」という気持ちになったため、Elixirのもくもくと勉強する会を秋葉原で定期的にやることになった。今回は第一回目であったため、以前に会をやっていたルームシェアでやることにした。

その中で、ウェブ媒体のライターをしつつ、のちのちはプログラマになりたいという若人がいたために、Elixir最速基礎文法をあらかじめ目を通しておいて、そのあとの課題としてProject Eulerの最初の10問程度をできるだけ自分で問いてみるということを提案してりたりした。他の人は、直接HTMLなどが表示できるほうがいいのではないか、という提案があったりしたのだが、個人的にはまず「分岐」「反復」といった考え方になれたほうがいいし、最初の10問程度はそれで済む程度の問題なので、それを頑張ってもらうようにした。

で、教える側というのは、往々にして教えられるというか、学びがあったので、そのあたりを共有しておこうかなあというのが今回のエントリの目的となる。多分、こういった「関数型」に近い言語に接するときの戸惑いというのは、わりと似ているように感じたので、そのあたりを共有していきたいと思う。

再帰の考え方

やはり、慣れなかったのは、再帰によって反復を行なうという部分だった。例えば、1から10の数字を表示するという場合、次のように書ける:

defmodule Count do
  def up(n) do
    _up(1, n)
  end

  defp _up(counter, m) do
    IO.puts(n)
    if counter != m do
      _up(counter + 1, m)
    end
  end
end

Count.up(100)

Elixirに関して、基本的にはwhileといったようなループ構文は用意されていないようなので、自分で自分の関数を呼びだすといった再帰的方法に慣れないといけない。今回の場合であるならば、1から100まで表示するためにはカウンターをただ1足していく方法でいいのだけれども、例えばProject Eulerの最初の問題でどうも躓いてしまうのである:

10未満の自然数のうち, 3 もしくは 5 の倍数になっているものは 3, 5, 6, 9 の4つがあり, これらの合計は 23 になる.同じようにして, 1000 未満の 3 か 5 の倍数になっている数字の合計を求めよ.

このとき、慣れているプログラマであるならば、まずカウントする従来の関数と、数字の合計を保持するための何らかの方法が必要となる、というように問題を読みとける。問題は、この数字の合計を何処に保持しておくのか、ということになる。

再帰的な方法として、一番簡単なのは、再帰するさいに、カウンダーとは別に「数字の合計」という暫定的な値を引数として渡してあげる、ということであるんだけれども、これを思いつくのがなかなか難しい。最初のカウンターを引数として渡してあげる、という発想から、引数というのは同時に次の実行する関数に渡してあげるさいに利用できるという考えに至るのが難しい。たぶん、これは再帰を勉強するにあたってひっかかる、まず最初の難関だと思う。

素朴に再帰を使って上の問題を解くと次のようになる:

defmodule Problem1 do
  def solve do
    _solve(1, 0)
  end

  defp _solve(1000, result) do; result end
  defp _solve(n,   result) do
    if rem(n, 3) == 0 || rem(n, 5) == 0 do
      _solve(n + 1, result + n)
    else
      _solve(n + 1, result)
    end
  end
end

IO.puts Problem1.solve

とはいえ、この再帰の方法は、直観的ではないようにも思える。ここまで書ければ上等なのだけれども、自分だったら、メモリ効率の問題とかを度外視した場合には次のように書くだろうと思う。

defmodule Problem1 do
  def solve do
    1..999
    |> Enum.filter(&(rem(&1, 3) == 0 || rem(&1, 5) == 0))
    |> Enum.sum
    |> IO.puts
  end
end

Problem1.solve

要するに、1から999のEnumerator(でいいのか？)を作り、そこから3と5の倍数のみの要素リストに加工してあげて、それを合計するという方法を取る。関数型の世界だと再帰は強すぎるので、もし再帰が必要になったさいには、その再帰はmapやfilterなどの高階関数で表現できないものなのかどうなのか、というを検討するのが良い(という話をどこかで聞いた)。

また、Elixirというか、関数の引数においてパターンマッチを採用している言語(Haskellとか？)でもそうなんだけど、このときに関数が実行される順序がわからない、という混乱があったようで、これ自体に関しては条件があっている関数が見つかったときに、その関数が実行される、という説明くらいしかできなかったけれども合ってるのだろうか。

あともう一つとして、ちょっと難しいなあと思ったのは、例えば次の問題:

フィボナッチ数列の項は前の2つの項の和である. 最初の2項を 1, 2 とすれば, 最初の10項は以下の通りである. 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... 数列の項の値が400万以下の, 偶数値の項の総和を求めよ.

この問題のときに、C言語のサンプルなんかを参考にしていたみたいだけれども、それが余計混乱する要因になっていたようで、C言語はわからないけれど、例えばPythonで泥臭く書くならば、次のように書くことができる:

def fib_sum():
    f0 = 1
    f1 = 1
    result = 0

    while f1 < 4000000:
        if f1 % 2 == 0:
            result += f1
        f2 = f0 + f1
        f0 = f1
        f1 = f2

    print(result)


if __name__ == "__main__":
    fib_sum()

このように泥臭く書くことはできるのだが、しかしElixirでは先程もいったように、そもそもwhile自体をどのように再帰的なコードに書き直すのか、というところがある。フィボナッチ数列自体は、数列にした場合に、「横にずれていく」数列であるということに気がつけば、前の二項の後ろ側を一つずらし、新しく二項を足したものを新しく後ろに追加していくようなことを繰りかえすことを考えるとわかりやすい。

defmodule Problem2 do
  def solve do
    _fib_sum(1, 1, 0)
  end

  defp _fib_sum(f0, f1, result) do
    cond do
      f1 >= 4000000   -> result
      rem(f1, 2) == 0 -> _fib_sum(f1, f0 + f1, result + f1)
      true            -> _fib_sum(f1, f0 + f1, result)
    end
  end
end

IO.puts Problem2.solve

しかし、個人的な審美眼からすれば、このコードはそもそも直感的ではないのではないか、という不安を感じざるを得ない。というのは、フィボナッチ数列から指定された範囲の中で偶数の数字を取りだして、それを足しあわせればいいのではないか、ということで、自分の解答は以下の通りになる:

defmodule Problem2 do
  def solve do
    Problem2.gen_fib(1, 1)
    |> Enum.filter(&rem(&1, 2) == 0)
    |> Enum.sum
    |> IO.puts
  end

  def gen_fib(prev, next) do
    if prev + next <= 4000000 do
      [prev + next | gen_fib(next, prev + next) ]
    else
      [prev + next]
    end
  end
end

Problem2.solve

こうすると、指定させた範囲のフィボナッチ数列から、偶数の数だけを取りだしてきて、それを合計するということが表現しやすくなった。ただし、この方法は、フィボナッチ数列がある程度のリストまで増えないということがわかっているが故の方法でもある。

まとめ

たぶん、大企業の人々は、新卒の本当に「プログラミングを経験したことがありません」という人に対してこういった初歩的な分岐や反復を教えるということは多々やってきていると思うのだけれども、そういう機会が全くない人間にとっては、こういう風に教えることは殆どないので、教えることで学ぶことができたというのは大きい。

また、やはりいきなりの初心者にとって、Elixirはハードルが高いのはあたりまえで、そういうのにぶちこんでしまったこっちの責任もあるのだろうけれども、しかしここの考え方自体は他のプログラムを組むさいにも流用できると信じて、応用していって欲しいなあという気がした。教えた方は別件でPythonチュートリアルもやっているようなので、それを比較しながら、「こういう風に違うのか」ということを学んでいってくれればなあ、という気持ちになったりした。