Erlangでmerge sortを作ってみる練習

なんとなく最近Erlangの勉強を始めて,ざっと飛行機本の最初を眺めてみたんだけど,眺めただけでまったく何も作れなかったのでmerge sort(マージソート)を作ってみた.
最初に,Pythonで作ってみたら意外とさらっとできたので,移植すればすぐ終わるかなとタカをくくっていたら,めちゃめちゃ時間がかかったので,気づいたトコロをメモ.
まったくもって素人もいいトコなので間違ってたらごめんなさいです.

listの大きさ

lengthというBIF(Built-In Function)でとる,でもなぜかtupleはsizeというBIFでとる.

1> length([1,2,3,4,5]).
5
2> size({1,2,3,4,5}).
5

headとtailのとりかた

Schemeでいうcarとcdrのとりかた
%0 [Head|Tail]というふうにパターンマッチさせる.

1> [Head|Tail] = [1,2,3,4,5].
[1,2,3,4,5]
2> Head.
1
3> Tail.
[2,3,4,5]

%1 hd(List),tl(List)というBIFがある.

1> hd([1,2,3,4,5]).
1
2> tl([1,2,3,4,5]).
[2,3,4,5]

整数/整数は浮動小数

なので必要に応じてtrunc(切り捨て),round(四捨五入で整数)といったBIFを使う.

1> 5/2.
2.5
2> trunc(5/2).
2
3> round(5/2).
3

ifにはelseがない

なので代わりに最後にtrue -> hogeみたいにする.

1> if 2+2 == 5 -> io:format("illogical~n");
true -> io:format("logical~n") end.
logical
ok

リスト系の処理はlistsモジュールにいろいろ用意されてる

appendとかreverseとかそういうのはだいたい揃ってる.
http://www.erlang.org/doc/man/lists.html

listやtupleのインデックッスは1から始まる

1> lists:nth(1, [1,2,3,4,5]).
1
2> element(1, {1,2,3,4,5}).
1

作ったコードはこんな感じ.

%% -*- coding: utf-8 -*=

-module(mergesort).
-export([mergesort/1]).


merge(Llist,Rlist) ->
    if (length(Llist) > 0) and (length(Rlist) > 0) ->
	    if hd(Llist) =< hd(Rlist) ->
		    [hd(Llist)|merge(tl(Llist),Rlist)];
	       true ->
		    [hd(Rlist)|merge(Llist,tl(Rlist))]
	    end;
       length(Llist) == 0 ->
	    Rlist;
       length(Rlist) == 0 ->
	    Llist
    end.


mergesort(List) ->
    if length(List) == 1 ->
	    List;
       true ->
	    Mid = trunc( length(List)/2 ),
	    Llist = element(1,lists:split(Mid,List)),
	    Rlist = element(2,lists:split(Mid,List)),
	    merge( mergesort(Llist), mergesort(Rlist))
    end.

実行結果.

bash-3.2$ erlc mergesort.erl
bash-3.2$ erl mergesort.beam 
Eshell V5.6.3  (abort with ^G)
1> mergesort:mergesort([3,2,0,1,5,8,4,2,2,7]).
[0,1,2,2,2,3,4,5,7,8]