<   2018年 10月 ( 29 )   > この月の画像一覧

クイックソートの見える化

クイックソートの見える化をやってみた。プログラムは次のようになる。

qsort [] = []
qsort (x:xs) = qsort (filter (<=x) xs) ++ [x] ++ qsort (filter (>x) xs)

qsort' [] = ([], "")
qsort' (x:xs) = (
  fst (qsort' (filter (<=x) xs)) ++ [x] ++ fst (qsort' (filter (>x) xs)),
  "(" ++ snd (qsort' (filter (<=x) xs)) ++ ")" ++ "[" ++ show x ++ "]" ++ "(" ++ snd (qsort' (filter (>x) xs)) ++ ")")

qsort はクイックソートのプログラムで、qsort' は見える化したクイックソートだ。qsort' の値はペアで第1要素はクイックソートの結果を、第2要素はクイックソートの計算の過程をリスト形式で表示する。

まず、qsort 関数でリストの整列をやってみる。

*Main> qsort [4,1,5,3,2]
[1,2,3,4,5]

次に、同じリストについて qsort' 関数を適用してみる。

*Main> qsort' [4,1,5,3,2]
([1,2,3,4,5],"(()[1]((()[2]())[3]()))[4](()[5]())")

qsort' の値のペアの第1要素は qsort と同じ出力が戻される。第2要素は qsort の計算の順序が、( ) と [ ] の2つのカッコで表わされている。リスト [4,1,5,2,3] の左端の要素 4 が取り出され 4 だけを要素とするシングルトンリスト [4] が作られる。そのシングルトンリストの左右に4以下のリストと 4 より大きい要素のリストを並べる。

([1,3,2]) [4] ([5])

次に左側のリスト [1,3,2] と右側のリスト [5] にも qsort を適用する。[1,3,2] の左端の要素 1 だけを要素とするシングルトンリスト [1] の左右にそれ以下の要素のリストとそれ以上の要素のリストを並べる。

([]) [1] ([3,2])

また、[5] の左右のリストは空リストだから ([]) [5] ([]) である。空リストの [] は表示しないことにすると、次のような表示になる。

(() [1] ([3,2])) [4] (() [5] ())

最後にリスト [3,2] を整列させると (() [2] ()) [3] () になる。これを上の途中経過に当てはめると、次のようになり、これは qsort' の値のペアの第2要素だ。

"(()[1]((()[2]())[3]()))[4](()[5]())")

このようにクイックソートの可視化も、qsort の動作を確認したあと qsort の出力をペアに変更した qsort' を定義することで割と簡単にできる。

[PR]
by tnomura9 | 2018-10-31 21:16 | Haskell | Comments(0)

挿入ソートを見える化する

前回の記事で述べた挿入ソートを見える化してみた。プログラムは次のようになる。insert, isort が元々の関数で、それを見える化したものが insert', isort' 関数だ。

insert x [] = [x]
insert x (y:ys) | x <= y = x:y:ys
insert x (y:ys) = y: insert x ys

isort [] = []
isort (x:xs) = insert x (isort xs)

insert' x [] = ([x],[])
insert' x (y:ys) | x <= y = (x:y:ys, show x ++ ":" ++ show y ++ ":" ++ show ys)
insert' x (y:ys) = (y:fst (insert' x ys), show y ++ ":" ++ "(" ++ snd(insert' x ys) ++ ")")

isort' [] = ([],"[]")
isort' (x:xs) = (insert x (fst(isort' xs)), "insert " ++ show x ++ " (" ++ snd(isort' xs) ++ ")")

insert 関数を見える化したものが次の実行結果だ。

*Main> insert 3 [1,2,4,5,6]
[1,2,3,4,5,6]
*Main> insert' 3 [1,2,4,5,6]
([1,2,3,4,5,6],"1:(2:(3:4:[5,6]))")

見える化した insert' 関数の出力から、3 が 1, 2 と次々に比較されて最後に 4:[5,6] と比較されて 4 の前に置かれて動作が終了しているのがわかる。

isort 関数を見える化したのが次の結果だ。

*Main> isort [5,1,4,3,2]
[1,2,3,4,5]
*Main> isort' [5,1,4,3,2]
([1,2,3,4,5],"insert 5 (insert 1 (insert 4 (insert 3 (insert 2 ([])))))")

こちらの方は、リストを右の方へ辿っていって最後に空リストになったところから順に挿入操作が行われていて、insert 関数を利用することで整列が機械的に行われているのがわかる。

再帰関数の見える化をどのようにしようかといろいろ工夫したが、isort 関数の動作確認をしたあと、その出力をペア化して fst に元々の関数、snd に関数を文字列化する式を記述することで、元々の関数を活かしながら、その動作を文字列化するのに成功した。このやり方は機械的にどのような再帰関数にも適用できる気がする。再帰関数の見える化は意外と簡単だ。

おまけで、階乗の計算を見える化してみた。

*Main> :{
*Main| fact 0 = (1, "1")
*Main| fact n = (n * fst(fact (n-1)), show n ++ " * (" ++ snd(fact (n-1)) ++ ")")
*Main| :}
*Main> fact 5
(120,"5 * (4 * (3 * (2 * (1 * (1)))))")

ペアを利用した再帰関数の見える化は、プログラムの式を逐語的に可視化できるので便利だ。


[PR]
by tnomura9 | 2018-10-30 00:19 | Haskell | Comments(0)

挿入ソート

整列されているリストに要素を挿入していくソート法。

最初に整列されているリストに要素を挿入する、insert 関数を定義する。

Prelude> :{
Prelude| insert x [] = [x]
Prelude| insert x (y:ys) | x <= y = x:y:ys | otherwise = y:insert x ys
Prelude| :}
Prelude> insert 3 [1,2,4,5]
[1,2,3,4,5]

x が y より小さければ y の前に挿入すればいいし、x が y より大きいときは y の後ろでリスト ys の中に挿入すればいい。

この insert 関数を使ってソートする isort を再帰的に定義する。再帰的に定義するときは isort 関数がすでに存在しているものと見做して再帰部分 recursive case を考える。リスト (x:xs) について、isort xs はリスト xs を整列させたリストであると考える。すると x を整列したリスト isort xs に挿入すればよい。したがって、isort の再帰部分のプログラムは、

isort (x:xs) = insert x (isort xs)

と書くことができる。

Prelude> :{
Prelude| isort [] = []
Prelude| isort (x:xs) = insert x (isort xs)
Prelude| :}
Prelude> isort [3,2,1,4]
[1,2,3,4]

再帰関数の再帰部分を定義するときは、再帰関数がすでに定義されているものとして定義を考えるとよい。

[PR]
by tnomura9 | 2018-10-29 00:54 | Haskell | Comments(0)

再帰関数の見える化

階乗のプログラムは再帰関数だ。定義するには base case と recursive case の2つの式を定義する。自分自身の関数を定義するのに自分自身の関数を用いるので戸惑うが、きちんと動作する。

Prelude> :{
Prelude| fact 0 = 1
Prelude| fact n = n * fact (n-1)
Prelude| :}
Prelude> fact 5
120

しかし、この計算を見える化すると次のようになる。

Prelude> :{
Prelude| fact 0 = "0"
Prelude| fact n = show n ++ " * fact (" ++ fact (n-1) ++ ")"
Prelude| :}
Prelude> fact 5
"5 * fact (4 * fact (3 * fact (2 * fact (1 * fact (0)))))"

要するに再帰関数は、再帰部分 recursive case に従って、次々に置き換えてできる多重のカッコの式を、展開が base case で止まった時点で実際の計算を行う多重カッコの計算だ。

再帰関数を定義するときにこのイメージがあればどういう計算になるのかがわかりやすくなる。

[PR]
by tnomura9 | 2018-10-28 18:10 | Haskell | Comments(0)

バブルソートの見える化

前回のバブルソートのプログラムは動いたが、なぜそうなるのかがスッキリしないので見える化してみた。リストの最大の要素を右端に移動させる bubble 関数は次のようになる。

Prelude| bubble [x] = [x]
Prelude| bubble (x:y:xs) | x > y = y : bubble (x:xs) | otherwise = x : bubble (y:xs)
Prelude| :}
Prelude> bubble [4,1,5,2,3]
[1,4,2,3,5]

この計算の途中経過が見えるように上のプログラムを次のような bubble' 関数に定義してみた。

Prelude> :{
Prelude| bubble' [x] = [[x]]
Prelude| bubble' (x:y:xs) | x > y = [y:x:xs] ++ bubble' (x:xs) | otherwise = [x:y:xs] ++ bubble' (y:xs)
Prelude| :}
Prelude> bubble' [4,1,5,2,3]
[[1,4,5,2,3],[4,5,2,3],[2,5,3],[3,5],[5]]

これを見ると、リスト [4, 1, 5, 2, 3] の先頭部分の 4 と 1 が比較され 4 のほうが大きいので交換されて [1, 4, 5, 2, 3] になる。次に 1 を外した [4, 5, 2, 3] の 4 と 5 が比較されこの場合は 5 のほうが大きいので要素の交換は起こらず [4, 5, 2, 3] のままだ。さらにこのリストから 4 を外した [5, 2, 3] で同様の比較が行われ 5 と 2 が交換されて [2, 5, 3] になるというふうに、大きい値がバブルのように右に移動していく様子がわかる。

バブルソートを行う関数 bsort は上の bubble を用いて次のようにプログラムできる。

Prelude> :{
Prelude| bsort [x] = [x]
Prelude| bsort xs = let b = bubble xs in bsort (init b) ++ [last b]
Prelude| :}
Prelude> bsort [4,1,5,2,3]
[1,2,3,4,5]

これもその過程を見える化してみた。

Prelude> :{
Prelude| bsort' [x] = ([x], [[x]])
Prelude| bsort' xs = let b = bubble xs in (fst (bsort' (init b)) ++ [last b], [b] ++ snd (bsort' (init b)))
Prelude| :}
Prelude> bsort' [4,1,5,2,3]
([1,2,3,4,5],[[1,4,2,3,5],[1,2,3,4],[1,2,3],[1,2],[1]])

これを見ると [4,1,5,2,3] が最初のスキャンで 5 が最後尾に移動し、次に [1,4,2,3] がスキャンされ 4 が最後尾に移動し、次に [1,2,3] がスキャンされと言うように最大数が最後尾に移動し、最後尾を除く前半のリストがスキャンされるのを繰り返すという動作を確認できる。

for ループは print デバッグで簡単に動作の見える化ができるのにたいし、再帰関数は計算の過程が見えにくいので難しく感じる。しかし、再帰関数の場合も見える化を工夫しているうちにその勘所がわかってくる。for 文が簡単で、再帰関数が難しいと感じるのは単に慣れの問題ではないのだろうか。


[PR]
by tnomura9 | 2018-10-28 10:27 | Haskell | Comments(0)

バブルソート

バブルソートのアルゴリズムは次のようになる。

[5, 1, 3, 4, 2] というリストがあるとき、最初の要素と、2番めの要素を比較して最初の要素が大きければ2番めの要素と交換する。次に2番めの要素と3番目の要素を比較して、2番めの要素が大きければ2番めと3番めを交換する。このような交換を続けていくと、リストの中の一番大きな要素が最後尾に来る。

[5, 1, 3, 4, 2]
[1, 5, 3, 4, 2]
[1, 3, 5, 4, 2]
[1, 3, 4, 5, 2]
[1, 3, 4, 2, 5]

そこで最高の要素は残しておいて、初めの方の [1, 3, 4, 2] について同じような交換を繰り返す。すると最終的に値の小さい順にリストをソートすることができる。一連の交換の操作で最も大きい値が泡が浮かんでいくように移動していくのでバブルソートというらしい。

これを Haskell でプログラムしてみた。まず、リストの要素を交換していく関数を bubble という名前にした。

Prelude> :{
Prelude| bubble [x] = [x]
Prelude| bubble (x:y:xs) = if x > y then y : bubble (x:xs) else x : bubble (y:xs)
Prelude| :}
Prelude> bubble [5,1,3,4,2]
[1,3,4,2,5]

この交換の操作を最後の要素を残して、最初の方のリストに次々に適用していく関数 bsort 関数を定義したら、これがバブルソートのプログラムになる。

Prelude> :{
Prelude| bsort [x] = [x]
Prelude| bsort xs = let b = bubble xs in bsort (init b) ++ [last b]
Prelude| :}
Prelude> bsort [5,1,3,4,2]
[1,2,3,4,5]

バブルソートのプログラムは、普通多重の for ループで実現するので、再帰関数でできるのだろうかと心配したが、案外簡単だった。繰り返しをループとしてとらえるか、recursive case による再帰的定義によって理解するかの違いがあるだけで、関数型言語だからといって難解になるといったものでもなかった。要は、再帰による定式化にたいする慣れの問題でしかない。

じつは再帰的関数の定義で難しいのは再帰部分の recursive case ではなく、終了条件 base case の決め方のほうなのだ。これはトライアンドエラーで決めることが多い。

[PR]
by tnomura9 | 2018-10-27 22:12 | Haskell | Comments(0)

foldr1

foldr から派生した関数に foldr1 がある。foldr1 は再帰関数の base case にリストの最後尾の要素をとるようだ。なにが便利かと言うと、foldr f z [1..n] のときの base case の z を省略できることだ。foldr1 でリストの要素の和と積を計算するのは次のようにする。注目すべきは、引数に base case がない。

Prelude> foldr1 (+) [1..5]
15
Prelude> foldr1 (*) [1..5]
120

どちらかと言うと、こちらのほうが foldr より、1 + 2 + 3 + 4 + 5 のような総和の感覚に近い。foldr1 は四則演算だけでなく、大小関係のような関数にも使える。例えば max は2引数をとり、多い方の数を返すが、これをfoldr1 に適用すると、リストの最大値を求めることができる。

Prelude> max 1 3
3
Prelude> foldr1 max [1,3,5,2,4]
5

これは次のような計算が行われたからだ。

foldr1 max [1,3,5,2,4] = (max 1 (max 3 (max 5 (max 2 4)))) = (max 1 (max 3 (max 5 4))) = ... max 1 5 = 5

また、2つの引数のうち小さい方を返す min 関数を foldr1 の引数に取ると。リストの最小値を求めることができる。

Prelude> foldr1 min [1,3,5,2,4]

Data.List の foldr1 のプログラムはエラー検出も含めた複雑なものだが、そのエッセンスは次のような簡単なプログラムだ。

Prelude> :{
Prelude| myfoldr1 f (x:[]) = x
Prelude| myfoldr1 f (x:xs) = f x (myfoldr1 f xs)
Prelude| :}

そうして、これは次のように実行可能だ。

Prelude> myfoldr1 (+) [1..5]
15

上のようなリストの要素の最大最小を求めるようなプログラムでは base case にリストの要素を選ぶのが適切だ。foldr 関数とともに foldr1 関数も応用範囲の広い関数だ。



[PR]
by tnomura9 | 2018-10-27 00:54 | Haskell | Comments(0)

手続き型プログラムみたいな Haskell プログラム

for 文と map 関数の関係が見えてきたので、手続き型プログラム風にリストのデータの基本統計の分散量を求めるプログラムを書いてみた。

variance :: [Float] -> Float
variance xs =
    let
        n = fromIntegral $ length xs
        mean = (sum xs) / n
        var = (sum $ map (\x -> (x-mean)*(x-mean)) xs) / n
    in
        var

map 関数や sum 関数が for ループを表していると考えて良い。発想的にも手続き型プログラムとそう変わったものでもないが、for ループが隠蔽されているぶんスッキリしているように見える。変数への代入(束縛)も手続き型言語風といってもいいくらいわかりやすいプログラムになった。

手続き型プログラムと Haskell の距離はそう遠くないのかもしれない。

実行例は次のようになった。

*Main> variance [1.2, 2.5, 3.4]
0.8155556


[PR]
by tnomura9 | 2018-10-25 22:41 | Haskell | Comments(0)

for 文と map 関数

Python の for 文と Haskell の map 関数は非常に関連性が高い。リスト [1,2,3] の要素をプリントする次の Python のプログラムは、

>>> for i in [1,2,3]:
... print(i)
...
1
2
3

Haskell では次のようにプログラムできる。

Prelude> mapM_ print [1..3]
1
2
3

これは、手続き型言語の for 文のプログラムは map 関数に置き換えることができるということを意味している。具体的には手続き型言語の for ループの中のプログラムを foo x という関数に翻訳し、map foo [1..n] を実行すればよいということだ。

しかし、for ループは多重ループにすることができる。多重ループを map でどのように表現すればいいのだろうか。それは、for 文のように map 関数を入れ子にすれば実現できる。例えば、リスト [1,2,3] と [4, 5, 6] の要素のペアを全て作るには次のようにする。

Prelude> map (\x -> map (\y -> (x,y)) [4,5,6]) [1,2,3]
[[(1,4),(1,5),(1,6)],[(2,4),(2,5),(2,6)],[(3,4),(3,5),(3,6)]]

しかし、for ループでは外側のループのインデックスを内側のループで利用することができる。果たして map 関数にそのような芸当ができるだろうか。それも、簡単にできるのだ。

Prelude> map (\x -> map (\y -> (x,y)) [1..x]) [1..3]
[[(1,1)],[(2,1),(2,2)],[(3,1),(3,2),(3,3)]]

出力がリストのリストになっているのが気になる場合は、外側の map の代わりに concatMap を使うと良い。

Prelude> concatMap (\x -> map (\y -> (x,y)) [1..x]) [1..3]
[(1,1),(2,1),(2,2),(3,1),(3,2),(3,3)]

実はこれらのプログラムはリストの内包記法を使うともっと直感的になる。

Prelude> [(x,y) | x <- [1,2,3], y <- [4,5,6]]
[(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]

Prelude> [(x,y) | x <- [1,2,3], y <- [1..x]]
[(1,1),(2,1),(2,2),(3,1),(3,2),(3,3)]

また、データの総和のような for 文の中にアキュームレータが現れるようなプログラムは foldr で記述すると良い。

Prelude> foldr (+) 0 [1..5]
15

こうしてみると、手続き型プログラムの for ループはほとんど逐語的に Haskell のプログラムに翻訳できることがわかる。

[PR]
by tnomura9 | 2018-10-25 21:45 | Haskell | Comments(0)

foldr の定義

foldr で無名再帰関数が定義できるのは、foldr の定義を見ればわかる。foldr の定義は次のようになる。

foldr f z [] = z
foldr f z (x:xz) = f z (flodr f z xs)

(foldr f z) を再帰関数と考えると、上の式は一行目が引数が [] のときの
base case で 2行目は引数が (x:xs) のときの recursive case になっている。

f = \x y -> x + y

のときは上の式は、

foldr f 0 [] = 0
foldr f 0 (x:xz) = f 0 (foldr f 0 xs) = 0 + (foldr f 0 xs)

となるので、(foldr f 0) が再帰関数であることがはっきりわかる。また、
f = \x y -> x + y の y が (foldr f 0 xs) であることも理解できる。

上の foldr の定義は自前でもできて、実際に動作する。

Prelude> :{
Prelude| myfoldr f z [] = z
Prelude| myfoldr f z (x:xs) = f x (myfoldr f z xs)
Prelude| :}
Prelude> myfoldr (+) 0 [1..5]
15

foldr は Data.List モジュールで定義されているが、Data.Monoid モジュール
関数を利用してあるので上の例とは異なっている。

foldr :: (a -> b -> b) -> b -> t a -> b
foldr f z t = appEndo (foldMap (Endo #. f) t) z

おそらく、foldr を List 以外のデータ、例えば木構造にも使えるように抽象化
しているものと思われる。

[PR]
by tnomura9 | 2018-10-25 07:02 | Haskell | Comments(0)