「関数型脳になろう 〜 脱 for 文編 〜」の解答例

「関数型脳になろう 〜 脱 for 文編 〜」はこちら。

問題 1.

[ 10, 20, 30, 40 ] = [10 | [ 20, 30, 40 ] ] … (1)
[ 20, 30, 40 ] = [20 | [ 30, 40 ] ] … (2)
[ 30, 40 ] = [30 | [ 40 ] ] … (3)
[ 40 ] = [40 | [  ] ] … (4)

定義 1. より、 [ ] はリスト。
よって、 (4) と定義 2. より、 [40] はリスト。
よって、 (3) と定義 2. より、 [30, 40] はリスト。
よって、 (2) と定義 2. より、 [20, 30, 40] はリスト。
よって、 (1) と定義 2. より、 [10, 20, 30, 40] はリスト。

[ 10, 20, 30, 40 ] は [ 10 | [ 20, 30, 40 ] ] のことであり、 [ [ 10, 20, 30 ] | [ 40 ] ] とは完全に別物なことに注意しよう。

リストの図解

問題 2.

defmodule Exercise do
  def product([]), do: 1
  def product([head | tail]), do: head * product(tail)
end

問題 3.

defmodule Exercise do
  def len([]), do: 0
  def len([_ | tail]), do: 1 + len(tail)
end

length って名前で関数を作ろうとしたら、組み込みの length 関数と競合してエラーが出た。これは出題が悪かった。スマソ。

問題 4.

defmodule Exercise do
  def each_double([]), do: []
  def each_double([head | tail]), do: [head * 2 | each_double(tail)]
end

問題 5.

defmodule Exercise do
  def odd_only([]), do: []
  def odd_only([head | tail]) do
    if rem(head, 2) === 1 do
      [head | odd_only(tail)]
    else
      odd_only(tail)
    end
  end
end

問題 6.

defmodule Exercise do
  def map([], _), do: []
  def map([head | tail], f), do: [f.(head) | map(tail, f)]
end

問題 7.

defmodule Exercise do
  def reduce([], acc, _), do: acc
  def reduce([head | tail], acc, f), do: f.(head, reduce(tail, acc, f))
end

参考までに reduce_left のパターンも載せておく。「末尾呼出最適化」を利用したい時、このパターンの実装も必要になってくる。

defmodule Exercise do
  def reduce_left([], acc, _), do: acc
  def reduce_left([head | tail], acc, f), do: reduce_left(tail, f.(head, acc), f)
end

問題 8.

each_double 関数を作るとこうなる。

defmodule Exercise do
  def reduce([], acc, _), do: acc
  def reduce([head | tail], acc, f), do: f.(head, reduce(tail, acc, f))

  def each_double(a_list), do: reduce(a_list, [], fn (x, acc) -> [x * 2 | acc] end)
end

x * 2 を f.(x) に置き換えることで map 関数が作れる。

defmodule Exercise do
  def reduce([], acc, _), do: acc
  def reduce([head | tail], acc, f), do: f.(head, reduce(tail, acc, f))

  def map(a_list, f), do: reduce(a_list, [], fn (x, acc) -> [f.(x) | acc] end)
end

問題 9.

defmodule Exercise do
  def repeat(_, 0), do: ""
  def repeat(text, num), do: text <> repeat(text, num - 1)
end

-2 とか 1.5 とか入れると無限ループになる危険プログラムと化しているので、本当はもうちょっと色々なんとかした方がいい。

全部解けたら

他に押さえておきたい重要な関数型の概念として、「末尾呼出最適化」「メモ化」「遅延評価」などがある。適宜ググって掘っておいてほしい。