読者です 読者をやめる 読者になる 読者になる

後ろを向いて後退します

これって前に進んでいることになりませんか?

アレをErlangで解いてみようとした

Aizu Advent Calendar (Qiita) #10

qiita.com

Aizu AdC多すぎ!!!

登録駆動ブロギングで自然と進捗を記事にしようね~とか思っていたら余裕でケツが炎上して大変なことになっています。(遅刻してすみません。)

前の記事は、masapontoさんの

masaponto.hatenablog.com

次の記事は、yakumoさんの

qiita.com

です。

Learn You Some Erlang for Great Good!

Erlangを始めて5ヶ月目の僕です。

Erlangは使い所が無いとかシンタックスがキモいとかスタックトレースがクソ見にくいとか別に他の言語でできるしとか割と散々な言われような気がするんですけど、僕はErlangが好きです。

What is Erlang?

シンタックスPrologのそれを参考にしていて慣れない人が多いらしいですが、ぶっちゃけ慣れたら気にならなくなります。

Erlangは軽量プロセスによる並行処理やホットコードスワッピング、高い耐障害性がウリで、使い所は限られるかもしれませんが、ネットワークサーバーやメッセンジャーアプリのサーバーなど「たくさんの事を並行してやりたい」みたいな要望には非常に適しています。

Erlangが提供する「プロセス」は、オペレーティングシステムが提供するプロセスやスレッドとは異なり、Erlangの仮想機械(VM)によって管理される。 「プロセス」の生成オーバーヘッドは約300ワード程度に抑えられており、大量の「プロセス」を、性能を低下させずに生成できる。 あるベンチマークでは2000万個の「プロセス」を並行実行できることが示された。

2000万ですってよ、奥さん。

5 problems

並行処理とかは全く関係無いのですが、ちょっと前インターネットで話題になってたコレをErlangで解いてみました。

www.softantenna.com

Q1, 3 way sum

forループ、whileループ、および再帰を使用して、リスト内の数字の合計を計算する3つの関数を記述せよ。

早速詰みました。Erlangにはforとwhileはありません。

マイケル先生の次回作にご期待下さい。

…などというのが許されるはずもなく、

「無いのなら作ればいい」

ということでリストの合計値を求めるだけの関数をそれぞれfor、whileっぽく実装しました(結局は全部再帰なのですが…)。再帰のほうはやるだけです。基底部の定義を忘れると死。

sumFor(Index, End, {Acc, List}) ->
  case Index =< End of
    true ->
      sumFor(Index + 1, End, {Acc + lists:nth(Index, List), List});
    false ->
      Acc
  end.

sumWhile(false, {Acc, _}) ->
  Acc;
sumWhile(true, {Acc, [H|List]}) ->
  sumWhile(
    if
      List /= [] -> true;
      List == [] -> false;
      true -> true
    end,
    {Acc + H, List}
   ).

sumRec([]) ->
  0;
sumRec([H|List]) ->
  H + sumRec(List).

Q2, join 2 lists

交互に要素を取ることで、2つのリストを結合する関数を記述せよ。例えば [a, b, c]と[1, 2, 3]という2つのリストを与えると、関数は [a, 1, b, 2, c, 3]を返す。

再帰するだけですね。生成するリストの長さは引数のうち短いほうのリストに合わせます。

join(_, []) ->
  [];
join([], _) ->
  [];
join([X|XS], [Y|YS]) ->
  [X, Y | join(XS, YS)].

Q3, fibonacci

最初の100個のフィボナッチ数のリストを計算する関数を記述せよ。定義では、フィボナッチ数列の最初の2つの数字は0と1で、次の数は前の2つの合計となる。例えば最初の10個のフィボナッチ数列は、0, 1, 1, 2, 3, 5, 8, 13, 21, 34となる。

フィボナッチ項を計算するだけならいいんですが、リストも返却するとなると話は別。少し冗長になってしまいましたが、これ以上に綺麗に書く方法はあるのか…?

fib(2) -> [0, 1];
fib(N) ->
  Prev = fib(N-1),
  Nth = lists:nth(N-1, Prev) + lists:nth(N-2, Prev),
  Prev ++ [Nth].

Q4, as max as possible

正の整数のリストを与えられたとき、数を並び替えて可能な最大数を返す関数を記述せよ。例えば、[50, 2, 1, 9]が与えられた時、95021が答えとなる。

難しいと思ったけど実質ワンライナー。文字列のリストに変換してから降順ソートしてjoinすればOKです。

maxSort(List) ->
  list_to_integer(
    lists:flatten(
      lists:reverse(
        lists:sort(
          [integer_to_list(X) || X <- List]
         )
       )
     )
   ).

Q5, make 100 in several ways

1,2,…,9の数をこの順序で、"+"、"-"、またはななにもせず結果が100となるあらゆる組合せを出力するプログラムを記述せよ。例えば、1 + 2 + 34 – 5 + 67 – 8 + 9 = 100となる。

僕はこの問題は関数型言語では解ける気がしませんでした。Erlangの模範解答お待ちしております。

Summary

Q4まではスラスラ行けましたがどうしてもQ5だけはErlangでは解けませんでした。手続き型でならいくらでもやりようはありそうですが…。

というわけで僕はプログラマ失格みたいです。精進したいと思います。

ちゃんちゃん。

余談

今年は全部で6つくらいAdvent Calendarに登録したのですが、そのうちコレを含めた2~3つはErlangに関する記事にする予定です。

この記事でErlangに興味を持ってくださった方がいたりしたら、後日投稿される(はずの)Erlang Advent Calendar #17とかAizu Advent Calendar 2 on Qiita #18の記事も是非読んでみてくださいね。

僕が喜びます。