唐揚げ問題 －Elixir見習いの実習ー

はじめに

Elixirに慣れるために基本的な問題を解いています。Qiitaで関数プログラミングに関連して唐揚げ問題が例題として示されていました。Elixirでやってみることにしました。

唐揚げ問題

下記のものが原典のようです。
https://qiita.com/stkdev/items/5c021d4e5d54d56b927c

引用させていただきます。

課題：
唐揚げ弁当がいくつかあるとします。それぞれ唐揚げが複数入っています。
この中からｘ個の唐揚げをつまみ食いするプログラムを作りましょう。
つまみ食いはバレないようにするために、
その時点で最も唐揚げ数が多いお弁当から取るという仕様にします。

考えたこと

当初、Elixirらしいデータ変換による方法を考えて見ました。　|>　をつかって次々とデータを変換していく方法です。しかし、どうもうまい方法を思いつきません。そこでオーソドックスに再帰を使うこととしました。

唐揚げのデータはリストにします。n個の唐揚げ弁当の唐揚げの個数は長さnのリストとします。[10,8,6]のようなります。

リスト中から最大要素を取り出すのには組込みのEnum.max/1が使えます。その最大要素をそこから1減算したものに置換する必要があります。Enumの組込みにないかと探してみたのですが見当たりません。自分で書きました。そのリストの最大要素を書き換える処理を指定回数、再帰により繰り返します。

コード

karaage/2 初期値リストを第１引数に、繰り返し回数を第２引数に指定します。経過を表示します。
replace_at/3　第３引数のリストの第１引数番目を第２引数の値で置換したものを返します。
find_index/2　第２引数のリストのなかの第１引数と同じ要素が何番目にあるのかを求めます。

defmodule M do

  def karaage(_,0) do :end end
  def karaage(l,n) do
    max = Enum.max(l)
    index = find_index(max,l)
    l1 = replace_at(index,max-1,l)
    :io.write(l1)
    karaage(l1,n-1)
  end

  def replace_at(1,x,[_|ls]) do [x|ls] end
  def replace_at(n,x,[l|ls]) when n>0 do
    [l] ++ replace_at(n-1,x,ls)
  end

  def find_index(x,[x|_]) do 1 end
  def find_index(x,[_|ls]) do
    find_index(x,ls) + 1
  end

end

実行例

iex(2)> M.karaage([10,8,6],10)
[9,8,6][8,8,6][7,8,6][7,7,6][6,7,6][6,6,6][5,6,6][5,5,6][5,5,5][4,5,5]:end
iex(3)>

考察

関数プログラミングとは何か？ということについては明確な定義はないそうです。しかし、副作用を避け参照透明性を確保するというのは共通の考え方のように思います。Elixirでの＝は破壊的代入ではなく、一時的な置き換えであり、Lispのlet構文のようなものだろうと思います。karaage/2で＝を使っていますが、これは副作用には当たらないと思います。writeを使っているのは副作用ですが、このあたりはElixirではそれほど神経質には考えていないようです。

破壊的代入を避けようとすると繰り返しは使えず、再帰を使うこととなります。再帰を使えばその式に人間の意図が込められていますから、その意図の読み取りは容易です。破壊的代入をしているとその変数にどのようにして値が与えられたのかを調べないといけません。

find_index/2で、要素がリスト中になかった場合を考慮していません。探そうとする最大要素はあることがわかっているので省略しています。replace_at/3 でwhenによるガードをかけています。これも省略してもこの問題の場合にはよさそうです。

唐揚げが全部、無くなってしまった場合のことを考慮していません。ちゃんとしようとすると唐揚げ0個を検出して停止させる必要があります。