Pure Functional Programming in Haskell

Menu Menu

I/O などが関係しない、入力から出力が常に同じに決まる関数プログラミングを Pure Functional Programming と言う。

---

再帰的な処理

変数の値を関数中で変えることができないので、 while 文などは、再帰で置き換える。

例えば、Ruby の fibonacci

    fib n     # write Fibonacci series up to n
	result = []
	a, b = 0, 1
	while b < n do 
	    result.push(b)
	    a, b = b, a+b 
	end
	return result
    end

は、以下のようになる。 ループで使う変数をすべて引数にしてしまうのが簡単。

    fib n = fib1 0 1 n
    fib1 a b n = 
	if b < n then
	    (b : fib1 b (a + b) n)
        else []
    :l fib.hs
    *Main> fib 10
    [1,1,2,3,5,8]

---

Haskell の リスト

( : ) で、リストを作っている (cons) 。ちょっと手で作ってみよう。

    *Main> ( 1 : [] )
    [1]
    *Main> (1 : (1 : [] ))
    [1,1]
    *Main> [1,2] ++ [3,4]
    [1,2,3,4]
    *Main> head [1,2,3]
    1
    *Main> tail [1,2,3]
    [2,3]
    *Main> head (1: (2: 3))
    <interactive>:1:13:
	No instance for (Num [t])
	  arising from the literal `3' at <interactive>:1:13
	Possible fix: add an instance declaration for (Num [t])
	In the second argument of `(:)', namely `3'
	In the second argument of `(:)', namely `(2 : 3)'
	In the first argument of `head', namely `(1 : (2 : 3))'
    *Main> head (1:(2:[]))
    1
    *Main> tail (1:(2:[]))
    [2]

リストは [] で終らないと怒られる。

---

逆順のリストを作る

こういう方法でリストを作ると、一番先に入れたものが先頭に来る。逆順のリストを再帰で作るには、最初に [] を引数で渡してしまうと良い。

    rev x = rev1 x []
    rev1 [] x = x
    rev1 (x:xs) y = rev1 xs (x:y)

異なる決まった値の入力を複数の関数で選択するのは、パターン、あるいはルールと呼ばれる。ここではリストの終了と cons pair を選択している。

    rev2 n = 
	if n==[] then 
            []
        else
            (rev2 (tail n)) ++ [head n]
            

この方法だと ++ を n 回繰り返すことになる。

rev1 は、

    rev3 n t = 
	if n==[] then 
           t 
        else
            rev3 (tail n) ((head n) : t)
            

と書いても同じ。(この方が普通っぽい?)

---

無限リスト

    inc 0 = []
    inc n = n : inc (n + 1)

inc 1 は、普通止まらない。これは無限リストを表している。でも、Haskell では必要とされる分しか計算されない。

    take1 0 x      = []
    take1 n (x:xs) = x : take1 (n-1) xs

というのを作り、

    *Main> take 10 (inc 1)
    [1,2,3,4,5,6,7,8,9,10]

というように使うことができる。

データ型