こんにちは。
今回は、プログラミング言語「Haskell」を触ってみます。
最近は一風変わったプログラミング言語シリーズ (?) を更新していますが、そのネタを探す最中「ラムダ計算」というものに出会いました。
いろいろ歩き回っていたら「Haskell」という言語が出てきまして、ちょっと見てみたらおもしろそうだったので手を伸ばしてみることにしました。
目次
「Haskell」とは
Haskell (Haskell Language) はプログラミング言語のひとつで、「関数型」に分類されます。
ちなみに、今までやってきた Processing や Python といった言語は「手続き型」に分類されるようです。
(このブログを開設してから2年以上経ちますが、このような分類は全く意識してきませんでした…)
実はおもしろそうだと思ったポイントはここで、杜甫々さんのサイト (とほほのHaskell入門 - とほほのWWW入門) を見たときに
「iには1が代入されていて... totalには100が代入されていて...」といった変数状態を考えながら、コンピューター目線でデバッグするのが手続き型。変数状態を意識することなく、純粋に「定義は正しいか」でデバッグできるのが関数型言語の優位性です。
とあった部分に興味を持ったのでした。
仕様に関しては、有名な言語なので日本語の記事もたくさんあるでしょうしここに書く必要もないと思います。
(私はとりあえず杜甫々さんのサイトを読んで、適宜補完しながら進めることにしました。)
実行環境
VSCodeで
VSCode に Haskell の拡張機能があります。まずはそれを入れましょう。
説明欄の「Setup」の項にHaskell のインストーラーである GHCupのリンク (GHCup) があります。
開くと Windows 用のコマンドが書いてありますので、PowerShell でこれを実行しましょう。
後は指示通りにインストールを進めていき、Installation - GHCup に従ってパスを通すなどしたら完了です。
(ここで苦戦したのですが、何回かやっていたらうまくいったので結局原因はわからず。)
ブラウザで
実はブラウザ上で動かせるものがあります。
(インストールを終えて「First Steps」を読み終えたところでさらっと紹介されるので、もっと早く言えよと思ったり。)
コーディング
ここからは、実際にいろいろつくってみます。
Hello World!
まずはおなじみの「Hello World!」を出力してみます。
ついでに、Haskell での実行までの流れを見てみましょう。
適当に「test.hs」というファイルをつくり、以下のように書きます。
main = putStrLn "Hello World!"
そして、ターミナルで
$ runghc test.hs
と実行すると、「Hello World!」が出力されます。
$ ghc test.hs
とすればコンパイルが行われ、exeファイル他が作成されます。
$ ./test
で実行可能です。
ちょっとした解説
(杜甫々さんのサイトを読めばわかりますが)
main はエントリポイントとよばれる、実行時に最初に読まれる部分です。
(Processing でいう setup() と同じ？)
putStrLn は文字列を改行付きで出力する関数です。
引数を書くときは空白を空けるだけでも良いし、括弧 () をつけても良いし、$ を挟んでも良いです。
($ は同じ行にあるそれ以降の記述を () に入れたのと同じ効果があるとのこと。)
ちなみに、
$ ghci
で対話的に実行可能です。
(Ctrl+d を押すか、ターミナルで :quit や :q を実行すれば抜けられます。)
フィボナッチ数列
単純な方法
fib :: Int -> Int fib 0 = 0 fib 1 = 1 fib n = fib (n-2) + fib (n-1) main = print $ fib 20
Int型の引数を受け取ってInt型の値を返す、という意味で fib :: Int -> Int と宣言を行っています。
(型推論可能なので無くても動きはしますが、型を明確にしたい場合などに。)
関数は、左辺に関数名と引数、右辺に計算したい式を書くことで定義できます。
また、パターンマッチにより引数の値によって別々の定義にすることができます。
フィボナッチ数列の定義をそのまま書いたような感じですが、これを実行すると 6765 と正しい値が出力されました。
しかし、引数の値が大きくなってくると遅さが目立ちます (50項くらいで限界)。
メモを使った方法
いつだったか触れた「メモ化」を使ってみます。
fib :: Int -> Integer fib 0 = 0 fib 1 = 1 fib n = fiblist !! (n-2) + fiblist !! (n-1) -- メモの作成 fiblist :: [Integer] fiblist = map fib [0..] main = print $ fib 10000
ここで、Int は固定長整数、Integer は多倍長整数です。
固定長整数は有限 (30 bit以上) の整数ですが、多倍長整数は理論上無限まで扱うことができます。
Int型で計算を行ってしまうと、あるところでオーバーフローが起こって計算結果が正しくなくなってしまいますので、それを解決するために無限まで扱えるInteger型を使います。
(わざわざ宣言しなくても、勝手にInteger型で計算してくれるようですが。)
fiblist !! (n-2) は fiblist の n-2 番目の要素を参照する、という意味です。
fiblist の定義の部分は
fiblist = [fib x | x <- [0..]]
と書くこともできます。
どちらも意味するところは同じで、[0..] で 0 から無限までの整数の配列をつくり、要素を1つずつ関数 fib にあてはめていっています。
無限長のリスト…？と思われるかもしれませんが、Haskell では「遅延評価」が採用されているので、必要なところだけしか考えません。
つまり、本来は無限まであるはずだけど、計算においては fiblist の引数で与えられた数までしか考えない、ということになります。
(たいていの言語は遅延評価の逆である「正格評価」を採用しています。)
この方法で5万項くらいまでそれなりの速さで計算できるようになりました。
zipWith を使った方法
こんな書き方もできるようです (Haskellでフィボナッチ数列 〜Haskellで非実用的なコードを書いて悦に入るのはやめろ〜 #Haskell - Qiita)。
fib :: [Integer] fib = 0 : 1 : zipWith (+) fib (tail fib) main = print $ fib !! 10000
ここでは fib をリストとして定義しています。
Haskell では [1 2 3] と 1:[2 3]、1:2:[3]、1:2:3:[] は同じ意味となっているので、上のような記述だと1つ目を 0、2つ目を 1、それ以降を zipWith (+) fib (tail fib) とするリスト、という意味になります。
zipWith は、1つ目に関数、2, 3つ目にリストを受けとる関数で、2つのリストの各要素について1つ目として与えた関数を適用してくれます。
つまり、fib と tail fib の各要素の和 (+) を計算してくれる、ということになります。
tail は引数のリストの先頭を除いたリストを返す関数ですので、zipWith の部分ではまさしくフィボナッチ数列の定義に従った計算を行っていることになるのです。
この方法で100万項くらいまで広がりました。
ちなみに zipWith は、
zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys
こんな処理をしているようです。
(x:xs) や (y:ys) は、対応するリストの先頭を x や y に、残りを xs や ys に入れる処理です。
先程した説明のままといえばそうですね。
zipWith (改) を使った方法
実は、遅延評価が悪さ (?) をして遅い (Haskellの神話 - あどけない話) ようで、zipWith を
zipWith' f (x:xs) (y:ys) = z `seq` (z : zipWith' f xs ys) where z = f x y
のように定義した zipWith' を使うとさらに高速化できるとのこと。
where は補助的な定義を行う際に使われます。
また、'seq' は正格評価を行う関数で、x 'seq' y の形で「x を評価した後に y を評価する」という意味になります。
つまり、zipWith では遅延評価のためいつまでも f x y が残ったままでしたが、zipWith' では f x y を評価して z としてから次に進むようになっています。
(これでなぜ早くなるのかはよくわかりません。)
変更の結果、200万項くらいまで許容できるようになりました。
まとめ
以上、Haskell を触ってみました。
軽い気持ちでフィボナッチ数列に手を出したら思ったより深かったので、一旦これだけで終わりにすることにしました。
まだ最初も最初の部分だとは思いますが実際触ってみても結構おもしろい言語だったので、今後続編が出るかもしれません。
最後まで読んでいただいてありがとうございました。また次回。
