Haskell(というか主に遅延評価)について
この記事はAizu Advent Calendar 2016 18日目の記事です。
前の人は、@lycoris0731 さん、次の人は @nktafuse さんです。
自分のこと
Noahです。学部一年です。
特に好きな分野とかは無いのですが、今回は『Haskellいいぞっ』という点と、Haskellの評価戦略(主に遅延評価と正格評価のこと)を書いていきたいと思います。
自分も初めて半年も経っていないのでわからないことも多いのですが、その点はご了承ください。
Haskell とは
何をもって関数型プログラミングとするか、関数型プログラミングを行っているコミュニティ内でも正確な定義や合意というものは存在しないが、一般的には、手続き型プログラミングがコマンド実行の列としてプログラムを記述していくのに対し、関数型プログラミングは複数の式を関数の適用によって組み合わせていくプログラミングスタイルである、ということは広く認められている。 by 関数型言語 - Wikipedia
つまり、Cなどが代表される手続き型言語は、
// nは任意の数 sum = 0; for (i = 0; i < n; i++){ sum += i; }
このような感じで、命令を並べ、順番に実行するのに対し、関数型言語(今回はHaskell)では
sum' :: Int -> Int --sum'としたのは、すでにsum関数がすでにPreludeというモジュールに定義されているからです。 sum' 0 = 0 sum' n = n + sum' (n - 1)
このように、関数の適用を組み合わせてプログラミングします。（この例では再帰を利用して0-nまでの合計値を出しています）
forは特にそうなのですが、変数に値を代入する行為、いわゆる副作用を排除した考えを関数型プログラミングでは用います。そのため、for（一応、forのようなものはHaskellに存在はするが）は、基本的にはあまり使いません
Haskellでは変数に値を入れることを束縛といいます。
値を束縛することで、変数を利用します。
一旦束縛したら、中身は変えられません。これは副作用を無くすことで生まれる参照透明性を確保するためです。
そんなの不便じゃないか？？と思う方もいらっしゃると思いますが、プログラミングスタイルに慣れればこれは理にかなっているものだと感じられるようになります。
関数色々
Haskellは関数を第一級オブジェクトとして扱います。
つまり、関数を変数に束縛することや、関数の返り値として関数を返すことも可能です。
関数を引数に取る例としてmap関数があります。
map' :: (a -> b) -> [a] -> [b] map' _ [] = [] map' f (x:xs) = f x : map f xs
一番上に書いてあるものは関数の型宣言です。
f :: Int -> Int -- Int型を受取り、Int型を返す g :: (Int -> Int) -> Int -- Intを受け取りIntを返す関数、を受取、Intを返す。
map関数は、a型を受取りb型を返す関数(f) と、a型のリスト( (x:xs) ) を受取り、a型のリストの中身それぞれに関数を適用した値(b型)をリストにして返す関数です。
rubyなどのmapメソッドと同じ挙動ですね。
ちなみに、関数の型宣言で用いられているIntのように最初の文字が大文字のものは型ですが、aなどのように最初が小文字なものは型変数といい、任意の型(CharやInt, Integerなど)にできます。
更に、リスト (x:xs) で、リストの先頭要素とそれ以外の要素に分けて名前を付ける事ができます。
(:) はコンスと呼ばれる関数で、Lisp等のconsとおなじだと考えればいいです。
遅延評価と正格評価
Haskellの大きな特徴として、遅延評価を採用している点があります。
CやRubyなどでは、標準で正格評価を行います。
遅延評価が採用されると何が嬉しいかというと、簡単な例では無限リストを扱えます。
ghci > take 3 [1,2..] [1,2,3]
[1,2..]は、[1,2,3,4,5,...100,...10000000,....]と続く無限リストです。
take関数は、引数として与えたリストから指定された分だけ、先頭要素からリストにして返します。
普通こんなものを扱うと引数のリストを評価するために無限に処理が行われますが遅延評価を評価戦略にしていると、必要な分だけ処理するので、上記の例では先頭要素3つ分だけ評価します。
他の例では、たらい回し関数と言うものが有り、
tarai :: Int -> Int -> Int -> Int tarai x y z | x <= y = y | otherwise =tarai (tarai (x - 1) y z) (tarai (y - 1) z x) (tarai (z - 1) x y)
以下にRubyでのコードも記述します。
def tarai(x, y, z) x<=y ? y : tarai(tarai(x-1, y, z), tarai(y-1, z, x), tarai(z-1, x, y)) end
そして、引数として(10, 5, 0)を与えたときのHaskellでの実行時間と、Rubyでの実行時間は以下の通りです。
*Main> tarai 10 5 0 10 (0.01 secs, 90,672 bytes)
% ruby tarai.rb
user system total real
0.020000 0.000000 0.020000 ( 0.015592)
そんなに変わりませんね。体感時間でも両方一瞬で終わります。
次に引数として(14, 7, 0) を与えたときです。
*Main> tarai 14 7 0 14 (0.01 secs, 99,784 bytes)
% ruby tarai.rb
user system total real
24.420000 0.090000 24.510000 ( 24.838016)
totalの時間が (10, 5, 0) のときより遥かに大きくなっています。
なぜこうなったかというと、Haskellの遅延評価が上手く効いているのです。
たらい回し関数では関数を実行する際に、引数(x', y', z') = ( tarai(x-1, y, z), tarai(y-1, z, x), tarai(z-1, x, y)) [ 区別を付けるために引数はx', y', z'にしています ] のなかでx', y' を評価し、 y'<=x' となったときは、z'の部分は利用されず評価をしても値を利用することがありません。
遅延評価は、必要になったら評価する評価戦略なので、x'<=y'となったときには評価に不要なz'部分は評価せずに素直にy'を返します。
otherwise、つまりそれ以外になって、z'が必要になったときに初めてz'を評価するのです。
最後に
以上です。少々間違いもあるかもしれませんが、関数型やる人が増えてほしいなと切実に思います。
参考にしたサイトなど
Haskell
- すごくえっちな本
- 関数プログラミング実践入門（書籍）
時間の計測
おわり
