Haskell ハンズオン
scrapbox.io/takoeight0821-public/Haskell_ハンズオン
GHCiで遊んで基本的な文法を確認しましょう。端末にghciと打ち込むと対話実行環境が立ち上がります。
code:ghci.hs
$ ghci
Loaded GHCi configuration from ~/.ghci
Prelude> 2 + 15
17
Prelude> 49 * 100
4900
Prelude> 5 / 2
2.5 -- 2じゃない!数値リテラルが整数か浮動小数点数かは文脈から自動で判断される(型推論の応用)
演算子の優先度は:infoコマンドで確認できます。
code:ghci.hs
Prelude> :info (+) -- ()で演算子を囲う
class Num a where
(+) :: a -> a -> a
...
-- Defined in ‘GHC.Num’
infixl 6 +
Prelude> :info (*)
class Num a where
...
(*) :: a -> a -> a
...
-- Defined in ‘GHC.Num’
infixl 7 *
(+)は優先度6の左結合、(*)は優先度7の左結合です。察しのいい人は気づいたかもしれませんが、演算子の優先度はinfix文を使ってプログラマが自由に指定することができます。
続いて真偽値です。
code:ghci.hs
Prelude> True && False
False
Prelude> False || True
True
Prelude> not False
True
真偽値はTrue/Falseです。演算子は次の通り。
code:ghci.hs
Prelude> 5 == 5
True
Prelude> 5 /= 5
False
Prelude> 5 /= 4
True
等価判定は==, /=。!=ではないことに注意。数学の≠の気持ちです。
code:ghci.hs
Prelude> 5 + "hello"
• No instance for (Num Char) arising from a use of ‘+’ • In the expression: 5 + "hello"
In an equation for ‘it’: it = 5 + "hello"
型が違うと型検査で弾かれます。型検査は静的に行われるので、型が合ってるかどうかはコンパイル時に分かります。
エラーメッセージは「文字列は'+'に必要なNumを実装していないよ」と言ってます。ちょっと変わった言い回しですね。
Haskellにも関数があります。むしろ「関数しかない」と言ったほうがいいかもしれないレベルで関数を多用します。
code:ghci.hs
Prelude> succ 1
2
Prelude> min 9 10
9
Prelude> max 3.4 3.2
3.4
Prelude> min "hello" "world"
"hello" -- いわゆる辞書順。他にも順序を持ちそうな型ならたいてい使える
関数適用は関数 引数1 引数2のように空白区切りで並べます。
code:ghci.hs
Prelude> succ 9 + max 5 4 + 1
16
Prelude> (succ 9) + (max 5 4) + 1
16
関数適用の結合の優先度は最高なので、空白区切りでも問題なく計算式を書けます。
code:ghci.hs
Prelude> div 92 10 -- 割り算の商を求める
9
Prelude> 92 div 10
9
関数をバッククォート(`)でくくることで中置演算子にできます。
code:ghci.hs
Prelude> (+) 10 2
12
中置演算子を()でくくることで関数にできます。
ここまでのおさらい
数値リテラルが整数か浮動小数点数かは文脈から自動で判断される
真偽値はTrue False
等価判定は==、その否定は/=
関数適用は関数 引数1 引数2。結合順位は最高
関数をバッククォート(`)でくくると中置演算子になる
中置演算子を()でくくると関数になる
/vagrant
次は関数を定義してみます。お好みのエディタで次のコードをタイプしましょう。
code:foo.hs
double x = x + x
見ての通り、与えられた数を2倍する関数です。
このファイルをfoo.hsとして保存し、foo.hsがあるディレクトリでghciを起動します。
code:ghci.hs
Prelude> :load foo -- foo.hsを読み込む
1 of 1 Compiling Main ( foo.hs, interpreted ) Ok, one module loaded.
*Main> double 9
18
*Main> double 8.3
16.6
今度は2つの引数をそれぞれ2倍して足し合わせる関数を作ります。foo.hsに次のコードを追記してください。
code:foo.hs
doubles x y = x * 2 + y * 2
code:ghci.hs
Prelude> :load foo
*Main> doubles 4 9
26
doublesは次のように定義することもできます。
code:foo.hs
doubles x y = double x + double y
Haskellではこのように「基本的で明らかに正しい関数を組み合わせて大きな関数を作る」パターンが頻出します。
そろそろ制御構文の話をしましょう。条件分岐の時間です!!
code:foo.hs
doubleSmallNumber x = if x > 100
then x
else x * 2
Haskellのifのユニークなところはelse節が必須なところです。Cでいう三項演算子に相当します。
さきほどのdoubleSmallNumberの返す値に1を加えたものを返す関数が欲しいとします。その関数は次のように書けます。
code:foo.hs
doubleSmallNumber' x = (if x > 100 then x else x * 2) + 1
Haskellではアポストロフィは(')を関数名の一部として使うことができます。慣習的には、ある関数の少し変更したバージョンの末尾につけることが多いです。関数fの微分をf'と書くのと同じ雰囲気です。
ここまでのおさらい
関数宣言は関数名 引数1 引数2 ... = 本体
if式はif 条件 then 成り立つとき else 成り立たないとき。else節は必須
関数名にはアポストロフィ(')も使える
次はHaskellのデータ構造で遊んでみましょう。最初はリストです。
リストは要素をカンマ区切りで並べて、角括弧でくくったものです。
code:ghci.hs
Prelude> numbers
numbers = [4, 6, 7, 1]のように、引数が一つもない関数を定義することもできます。このような関数は普通「定義」とか「定数」と呼びます。じゃあ変数は?Haskellはちょっと変わった方法で変数を扱います。が、なんと今回は変数を使いません!変数なしでも大抵のことはできるのがHaskellの面白いところです。
閑話休題。リストの続きです。リストの連結には(<>)を使います。
code:ghci.hs
Prelude> "hello" <> "world"
"helloworld"
長いリストに(<>)を使うときには注意が必要です。Haskellのリストはいわゆる「単方向連結リスト」です。2つのリストを連結するとき、Haskellは1つ目のリストを最後まで走査して、最後の要素のポインタが指す先を2つ目のリストの先頭に置き換えます。
一方、リストの先頭に要素を追加するのは一瞬です。
code:ghci.hs
リストに異なる型の値を入れることはできません。(実際はかなりアクロバティックなことをすれば可能です。気になる人は「存在型 リスト」でググってください)
code:ghci.hs
<interactive>:6:8: error:
• No instance for (Num Char) arising from the literal ‘2’
• In the expression: 2
In the second argument of ‘(:)’, namely ‘2, 3, 4’ リストの比較は辞書順で行われます。
code:ghci.hs
True
True
True
リストを操作するための基本的な関数をいくつか試してみましょう。
code:ghci.hs
Prelude> head list -- 先頭の要素
1
Prelude> tail list -- 2つ目以降のリスト
Prelude> init list -- 最後の要素以外のリスト
Prelude> last list -- 最後の要素
4
Prelude> head [] -- 空のときは例外が吐かれる
*** Exception: Prelude.head: empty list
Prelude> length list -- リストの長さ。単方向連結リストなのでO(n)です
4
Prelude> null list -- 空かどうかを判定
False
Prelude> null []
True
Prelude> reverse list -- ひっくり返す
Prelude> take 3 list -- 先頭からn要素を取得
Prelude> drop 3 list -- 先頭からn要素を削除(これに限らず、Haskellの関数はすべて非破壊的です)
Prelude> maximum list -- 最大値
4
Prelude> minimum list -- 最小値
1
Prelude> sum list -- 総和
10
Prelude> product list -- 総積
24
Prelude> 2 elem list -- 要素を含むかどうかを判定(∈)
True
Prelude> 5 elem list
False
ぜーはーぜーはー。こんなもんでしょう。
1から20までの数のリストを作りたいとします。全部手で書いてもいいのですが、こんなふうに楽をすることもできます。
code:ghci.hs
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20 "abcdefghijklmnopqrstuvwxyz"
1から20までの偶数のリストは?
code:ghci.hs
ここまでは簡単ですね。もうちょっと変わったことはできるでしょうか。例えば1, 2, 3, 1, 2, 3, 1, 2, 3, ...と続く無限列の先頭10個のリスト、とかは?
code:ghci.hs
cycleはリストを受け取ってそのリストを無限に繰り返すリストを返す関数です。
ちょっと待って!無限だって?
そのとおり。Haskellは無限に大きなデータを扱うことができます。
正確に言うと、Haskellは本当に必要になるまで式を評価しません。これを遅延評価と言います。
(本当に必要になるとき、というのは、パターンマッチで値が分解されるとき、です。詳しくは後で聞いてください。)
扱うデータそのものが無限でも、実際に必要なデータが有限なら有限の時間で求めることができます。便利ですね。
(効率を考えるともうちょっと頭を捻らないといけません。これについてもまたいつか)
リストの書き方についてもう少し深く見ていきましょう。
code:ghci.hs
Prelude> [x * 2 | x <- 1..10] リストはこんなふうに集合の内包的記法っぽく書くことも出来ます。
気になっている人のために言っておくと、かの有名な「モナド」はこの記法の一般化です。
リスト内包記法には条件を追加することも出来ます。
code:ghci.hs
Prelude> [x * 2 | x <- 1..10, x * 2 >= 12] Prelude> [x | x <- 1 .. 20, x mod 3 == 0 || x mod 5 == 0] [x | x <- 1 .. 20, x mod 3 == 0 || x mod 5 == 0] 複数のリストを束ねて一つのリストにすることもできます。
code:ghci.hs
2,4,6,8,10,6,12,18,24,30,10,20,30,40,50,14,28,42,56,70,18,36,54,72,90 xとyのあらゆる組み合わせでx*yを計算し、その結果を集めたのがこのリストです。
どんな順番で組み合わされているか見てみましょう。
code:ghci.hs
(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3) Pythonに直すとこんな感じでしょうか。(それはそうと、実はPythonにもリスト内包記法があります。)
code:list.py
for x in range(1, 3):
for y in range(1, 3):
(x, y)
つまりリスト内包記法はfor文のようなものだと思うことができます。
ところでこの(x, y)はタプルと呼びます。(x, y, z)と書くと3要素のタプルになり、リストとは異なりタプルとタプルを連結することはできません。
2つのリストをタプルを使って1つに束ねるには普通 zip 関数を使います。
code:ghci.hs
zipはさきほどとは違い、2つのリストを同時に走査します。無限リストと組み合わせて次のように使うこともあります。
code:ghci.hs
ここまでのまとめ
[]で囲まれたカンマ区切りの列がリスト。単方向連結リスト
()で囲まれたカンマ区切りの列がタプル。要素数によって違う型を持つ
Haskellは遅延評価。必要になるまで式を評価しない
ここらで1つ問題を解いてみましょう。『すごいHaskellたのしく学ぼう!』21ページの問題です。
次のすべての条件を満たす直角三角形を見つけるプログラムを書けるでしょうか?
3辺の長さはすべて整数である
各辺の長さは10以下である
周囲の長さは24に等しい
最初の一歩は各要素が1以上10以下であるような3つ組のタプルをすべて生成することです。
code:ghci.hs
さて、一体三角形は何個あるんでしょう。
code:ghci.hs
Prelude> length triangles
1000
えーと……まずは合同な三角形を除外しましょう。aがc以下、bがa以下になるようにすると合同な三角形を除外できます。
code:ghci.hs
Prelude> triangles = [(a, b, c) | c <- 1..10, a <- 1..c, b <- 1..a] Prelude> length triangles
220
問題は条件を満たす直角三角形を見つけることでした。直角三角形はピタゴラスの定理を満たします。これでフィルタリングしましょう。
code:ghci.hs
Prelude> rightTriangles
グッと減りました。周囲の長さが24に等しいのはどちらでしょう。
code:ghci.hs
これが答えです!
こんなふうに、最初に解の候補となる集合を生成し、それから解にたどり着くまで変換とフィルタを繰り返す手法は、関数プログラミングでよく用いられるパターンです。
ちなみに、これらを一行でまとめるとこんな感じになります。
code:ghci.hs
c^2 == a^2 + b^2, a + b + c == 24]
問題をそのままコードにしただけ、という雰囲気が伝わるでしょうか。
このことから関数プログラミングは「宣言プログラミング」の1つと言われることがあります。
残念ながら、実際のプロダクトコードではここまでうまくいくとは限らないのですが……
ここまでリスト内包記法を使ってきましたが、これはある種の糖衣構文で、実際にはただの関数適用に展開されます。
さきほどのコードは次のように脱糖衣されます。(厳密には違いますが、簡単のため書き換えています。)
code:ghci.hs
Prelude> triangles = concat (map (\c -> concat (map (\a -> map (\b -> (a, b, c))
Prelude> rightTriangles = filter (\(a, b, c) -> c^2 == a^2 + b^2) triangles
Prelude> filter (\(a, b, c) -> a + b + c == 24) rightTriangles
うへぇ……って感じですね。一つ一つ追っていきましょう。
concatは入れ子になったリストを平らに潰す関数です。
code:ghci.hs
Prelude> concat 1, 2, 3], [4, 5
concatを定義してみましょう。次のコードをfoo.hsに追記してください。
code:foo.hs
concat' [] = []
concat' (x : xs) = x <> concat' xs
これがconcatの定義です!本当にconcatになっているかどうか確認してみましょう。
code:ghci.hs
Prelude> :l foo
*Main> concat' 1, 2, 3], [4, 5
どうやら正しそうです。
さて、concat'は一体何をしているのでしょう。
改めてconcat'の定義を見てみます。
code:foo.hs
concat' [] = []
concat' (x : xs) = x <> concat' xs
concat'の定義が2つあるように見えます。
一行目は引数が[]、つまり空リストのときのconcat'の定義です。空リストを潰しても空リストなので、この定義は正しそうです。
二行目は引数がx : xsの形、つまりあるリストxsの先頭に要素xを加えたリストに対するconcat'の定義です。
入れ子になったリストの要素xはリストなので、xsを潰した結果と連結すると潰されたリストになります。
xsを潰すにはconcat'に適用すればよい、つまりこれは再帰関数になっています。
このように、値の形に基づいて処理を分岐することをパターンマッチと言います。
続いて、さきほどのコードのこの部分に注目してみましょう。
code:map.hs
map (\b -> (a, b, c)) 1..a map関数は引数に関数とリストを取り、関数をリストのすべての要素に適用する関数です。
ここで第一引数に与えられている\b -> (a, b, c)は関数リテラルとか無名関数と呼ばれる式です。
こんなふうに書いたのと同じ意味です。
code:map.hs
f b = (a, b, c)
map関数で遊んでみましょう。
code:ghci.hs
Prelude> map (\x -> x mod 3 == 0) 1..10 では、mapを定義してみましょう。次のコードをfoo.hsに追記してください。
code:foo.hs
map' f [] = []
map' f (x:xs) = f x : map' f xs
これもパターンマッチを使った再帰関数ですね。
これでtrianglesの定義が読めるようになった……はずです。どうでしょうか?
code:triangles.hs
concat (map (\c -> concat (map (\a -> map (\b -> (a, b, c)) 1..a) 1..c)) 1..10) ここまでのまとめ
値の形に応じて処理を分岐するパターンマッチ
関数リテラル\ 引数1 引数2 ... -> 本体
次はrightTrianglesの定義を読んでみましょう。
code:rightTriangles.hs
filter (\(a, b, c) -> c^2 == a^2 + b^2) triangles
filterは第一引数の関数で第二引数のリストをフィルタリングする関数です。定義はこんな感じになっています。
code:foo.hs
filter' f [] = []
filter' f (x:xs) = if f x then x : filter' f xs else filter' f xs
ガードという機能を使うと、こんなふうに書くこともできます。
code:foo.hs
filter'' f [] = []
filter'' f (x:xs) | f x = x : filter'' f xs
| not (f x) = x : filter'' f xs
仮引数リストの後ろに| 条件 = 本体と書くことで、パターンマッチの詳しい条件を追記することができます。
これで先程のコードはすべて読めるようになりました!
code:ghci.hs
Prelude> triangles = concat (map (\c -> concat (map (\a -> map (\b -> (a, b, c))
Prelude> rightTriangles = filter (\(a, b, c) -> c^2 == a^2 + b^2) triangles
Prelude> filter (\(a, b, c) -> a + b + c == 24) rightTriangles
最後に、ここまでのテクニックを使って書かれたクイックソートを見てみましょう。
code:foo.hs
quicksort [] = []
quicksort (x:xs) =
in quicksort smallerOrEqual <> x <> quicksort larger 参考書籍、関連リンク
『すごいHaskellたのしく学ぼう!』ISBN978-4-274-06885-0
今回の内容はこの本の1~5章をベースにしています
『Haskell入門 関数型プログラミングの基礎と実践』ISBN978-4-7741-9237-6
実務レベルの内容に踏み込みたいならこれ