2009年10月27日火曜日

Haskell その2

今度はリストを逆順にする関数を作る。

module Main where
import Text.Printf

main = do print (reverse([1,2,3,4,5]))
print (reverse1([1,2,3,4,5]))
print (reverse2([1,2,3,4,5]))
print (reverse3([1,2,3,4,5]))
print (reverse4([1,2,3,4,5]))

reverse1 x | length x == 1 =x
| length x > 1 =reverse1(tail x) ++ head x:[]
reverse2 (x:xs) | length xs == 1 =xs++x:[]
| length xs > 1 =reverse2(xs)++x:[]
reverse3 x=foldl (flip (:)) [] x
reverse4 =foldl (flip (:)) []
最初のreverseは最初から定義されている関数で、その名の通りリストを逆順にする。
reverse1 x | length x == 1 =x
| length x > 1 =reverse1(tail x) ++ head x:[]
これは引数xの長さが1ならxをそのまま返し、xが1より大きければxの先頭の要素を除いたリストを逆順にしたリストにxの先頭の要素を連結した結果を返す関数である。
++はリストの連結を行う演算子で:はリストの先頭に要素を追加する演算子である。
[]は空リストである。
reverse2 (x:xs) | length xs == 1 =xs++x:[]
| length xs > 1 =reverse2(xs)++x:[]
この関数は、リストを引数に取り、その先頭をxに、それ以外をxsとする。
xsの長さが1のとき、xsとxを連結したリストを返す。xsの長さが1より大きいとき、xsを逆順にしたリストにxを連結したリストを返す。
xsのsは英語の複数形で、こういう命名規則なのだそうだ(がどこで見たのかは忘れた…)。
別に従わないとコンパイルが通らないというわけではない。
reverse3 x=foldl (flip (:)) [] x
この関数も引数にリストを取り、それをxとする関数である。
これもリストxを反転した結果を返す関数であるが、少しややこしい。
foldlは引数を3つ取り、第3引数のリストの左側の要素から順に処理を行う関数である。
その処理をC言語風に書くと、第1引数を+、第2引数をa、第3引数のi番目の要素をx[i]、処理結果をrとして、
r = a
for(i=0; i<length x; ++i)
r = r + x[i]
return r
のようになる。

flipは2引数関数の引数を入れ替える関数である。f(x,y)ならf(y,x)になる。
:は右側(第2引数)にリスト、左側(第1引数)に追加する要素を書くが、そのままではfoldlが演算子:を呼び出すときに左右が逆になってしまう。そこで、flipを使って逆向きにする。

以上より、引数で与えられたリストの先頭の要素から順に新しいリストの左側に追加していくという処理になっており、リストの順序が逆向きになることがわかる。

reverse4 =foldl (flip (:)) []
この関数は、foldlの第3引数が指定されていない関数になっている。つまり、reverse4は引数を1つ取る関数である。
foldlの第1,第2引数が指定されている関数であるともいえる。

ああ、ややこしい。

0 件のコメント :