7つの言語 7つの世界 ~第8章 Haskell 1日目~

はじめに

　最近関数型プログラミングが流行していることと色々な言語に触れてみたいことから「7つの言語　7つの世界 -オーム社-」を読んでみることにした。
　本書では最初から読み進めることを推奨しているが、私は第6章のErlangから読み進め、今日からはHaskellに進む。
　Haskellは本書の中では、唯一の「純粋関数型言語」である。これを2つ目に選んだ理由としては、最近自分の友人が使っていたことと、下記の記事でPythonからの移行としても取り上げられていたことを発見したことである。

Haskellで生産性を高める-Pythonからの移行 | プログラミング | POSTD

環境構築

　Haskellにはコンパイラが必要なので、コンパイラの定番GHCとパッケージ管理ツールのCabalをbrewでインストールした。

brew install ghc cabal-install

　これだけで環境構築は終わり。使い方はまたやりながら試すけど、色んなオプションがあるから参考HPを随時見る。

Mac OS XのためのHaskell開発環境 - プログラミング芸術論

Haskellの特徴

1. 強い静的型付け言語

• これは、Scalaと同様らしい。

1. 多言語の概念をサポートしている。
   • Eralng方式のパターンマッチングとガード
   • Clojure方式の遅延評価
   • Clojure, Erlangのリスト内包表記

　きっと、このように多言語の概念が組み合わさってできているので本書でも最後の章で紹介されているのだろう。幸い、Erlangについては勉強したので半分ぐらいはわかりやすいだろう。
　本書の読み進め方を守ればもっとわかりやすいと思う。笑

1日目本編「論理的」

　まず、コンパイラのパッケージをロードする。

ghci

　これで、ロードが完了し、コマンドを入力できるようになる。

式とプリミティブ型

数値

Prelude> 4
4
Prelude> 4 + 1
5
Prelude> 4 + 1.0
5.0
Prelude> 4 + 2.0 * 5
14.0
Prelude> 4 * (5 + 1)
24

　このように、演算の優先順は、期待通りに動作する。最後にピリオドを打たなくて済むので楽だ。笑

文字データ

Prelude> "Hello"
"Hello"
Prelude> "Hello" + "world"

<interactive>:9:9:
    No instance for (Num [Char]) arising from a use of ‘+’
    In the expression: "Hello" + "world"
    In an equation for ‘it’: it = "Hello" + "world"
Prelude> "Hello" ++ " world"
"Hello world"
Prelude> 'a'
'a'
Prelude> "a"
"a"
Prelude> ['a', 'b']
"ab"

　文字列の連結演算子は++のようだ。また、1つの文字はシングルクォートで囲んで指定する。
　そして、文字列というのは単なる文字のリストのようだ。

ブール値

Prelude> (4 + 5) == 9
True
Prelude> (5 + 5) /= 10
False
Prelude> if (5 == 5) then "true"

<interactive>:17:24:
    parse error (possibly incorrect indentation or mismatched brackets)
Prelude> if (5 == 5) then "true" else "false"
"true"

　3行目のエラーは、後続の行が正しくインデントされていないという意味である。Pythonのようにインデントが重要な意味をなすようである。
　そして、4行目のようにelseを加えると完全なif/then/else文になるようだ。どうやら、Haskellでのifは制御構文ではなく関数らしい。ただ、だからと言ってなぜelseを加えると大丈夫なのかはよくわかっていない。python3系でprint文が関数になったみたいなモノなのか？？
　また、関数なので、値を返すことも可能らしい。

Prelude> if 1 then "true" else "false"

<interactive>:19:4:
    No instance for (Num Bool) arising from the literal ‘1’
    In the expression: 1
    In the expression: if 1 then "true" else "false"
    In an equation for ‘it’: it = if 1 then "true" else "false"
Prelude> "one" + 1

<interactive>:20:7:
    No instance for (Num [Char]) arising from a use of ‘+’
    In the expression: "one" + 1
    In an equation for ‘it’: it = "one" + 1

　上記の例は、型衝突である。Haskellは強く型付けされた言語なので、ifは厳密にブール型の値をとる。
　2つ目の例のエラーメッセージでは、「Num引数の後に文字のリスト[Char]が来る関数 + は存在しない」と言っている。Haskellでは様々なヒントによって型推論をしているみたいだ。どのように型推論しているかは:tと指定するか、tオプションをオンすれば良いらしい。

Prelude> :set +t
Prelude> 5
5
it :: Num a => a
Prelude> 5.0
5.0
it :: Fractional a => a
Prelude> "hello"
"hello"
it :: [Char]
Prelude> (5 == (2 + 3))
True
it :: Bool

　上記のように、1行目でtオプションをオンにすると、式を評価するたびに、式が返す型を確認できる。
　ただし、:tを数値と一緒に使うと数値を出来る限り総称的に処理しようとして混乱するので注意が必要である。下記の例を示すが、このようにすると、クラスが返されるようになる。

Prelude> :t 5
5 :: Num a => a

　本書では、Num t => tとなっていたのだが、自分で試したらaが出てきたのはなぜだろう？？

関数

　ここからは、Haskellの中心である関数の説明だ。各関数は、型指定（省略可能）と実装の2つの部分に分けて指定する。

基本的な関数の定義

　Haskellの関数は、従来より、型宣言と関数宣言の2つの部分からなる。
　最初はコンソール内で関数を定義する。let文を使って値を実装にバインドする。まずは、関数を定義する前にletを試してみる。Lispと同様で、コーかるスコープ内で変数を関数にバインドするらしい。

Prelude> let x = 10
Prelude> x
10
Prelude> let double x = x * 2
Prelude> double 2
4

　Haskellのモジュールをコーディングするときには、double x = x * 2のように関数を宣言する。letを使ってローカルスコープ内に関数を割り当てると使えるようになる。上記の例では、引数を倍にして返す簡単な関数doubleを示している。

　ここから、ファイルにプログラムを保存する方法に切り替える。これにより、複数行の定義が書けるようになる。GHCでは、完全なdoubleの定義は次のようになる。

double.hs

module Main where
        double x = x + x

　Mainという名前のモジュールを追加している。Haskellでは、モジュールとは関連するコードを同じスコープ内に集めたものである。Mainモジュールはトップレベルのモジュールである。Mainをコンソールにロードして次のように使う。

Prelude> :load double.hs
[1 of 1] Compiling Main             ( double.hs, interpreted )
Ok, modules loaded: Main.
*Main> double 5
10

　この例では、型を指定していない。そこで、次は型記述を明示的に指定した関数の例を示す。

double_with_type.hs

module Main where
        double :: Integer -> Integer
        double x = x + x

　先ほどと同じようにロードして使用する。

Prelude> :load double_with_type.hs
[1 of 1] Compiling Main             ( double_with_type.hs, interpreted )
Ok, modules loaded: Main.
*Main> double 5
10
*Main> :t double
double :: Integer -> Integer

　新しい関数に関連付けられている型は:tで確認できる。
　この定義は、関数doubleはInteger型の引数(最初のInteger)をとり、Integer値を返すことを意味している。
　この方記述は制限的であるので、先ほどのdouble.hsのように定義した型のないdoubleを実行すると、全く異なる結果になる。

Prelude> :load double.hs 
[1 of 1] Compiling Main             ( double.hs, interpreted )
Ok, modules loaded: Main.
*Main> :t double
double :: Num a => a -> a

　aは型変数である。この定義は、「関数doubleは、ある型の1の引数を1つとり、同じ型の1の値を返す」ということである。double_with_type.hsのように制限的な定義を改善したこの定義により、この関数は、+関数をサポートする任意の型に適用できるようになる。

再帰

　コンソール内で階乗計算を行う再帰的なワンライナー(1行プログラム)を以下に示す。

Prelude> let fact x = if x == 0 then 1 else fact (x - 1) * x
Prelude> fact 3
6

　これを文章にすると、「xの階乗は、xが0の時1、それ以外の時はfact(x - 1) * xである」となる。これから、このコードをパターンマッチングを利用して改良していく。このシンタックスは、見かけも動作もErlangと非常に似ているらしい。

factorial.hs

module Main where
        factorial :: Integer -> Integer
        factorial 0 = 1
        factorial x = x * factorial (x - 1)

　定義は3行である。1行目で、引数と、返す結果の型を宣言している。2行目と3行目は、入力された引数とのパターンマッチングの結果に応じて呼び出される異なる関数定義である。0のfactorialは1であり、nのfactrialはx = x * factorial(x - 1)である。この定義の仕方は、数学の階乗定義とほぼ一致している。この例では、パターンの指定順序が重要になる。最初にマッチした関数定義が呼ばれるからである。順序を変更する場合は、ガードを使用する必要がある。Haskellでは、ガードは引数の値を制限する条件として使われる。
　次に例を示す。

fact_with_guard.hs

module Main where
        factrial :: Integer -> Integer
        factorial x
                | x > 1 = x * factorial (x - 1)
                | otherwise = 1

　この例のガードでは、左側にブール値を、右側に適用される関数を指定している。ガードが満たされると、対応する関数が呼び出される。ガードはよくパターンマッチングの代わりに使用される。ここでは、再帰の基本条件(終了条件)を起動するために使用している。

タプルとリスト

　多言語と同じように、Haskellは末尾再帰最適化によって再帰を効率的に処理している。Haskellでフィボナッチ数列を生成するコードをいくつかの方法で記述してみる。

fib.hs

module Main where
        fib :: Integer -> Integer
        fib 0 = 1
        fib 1 = 1
        fib x = fib (x - 1) + fib (x - 2)

　最初は最も簡単な例である。これを効率化していく。

タプルを使ったプログラミング

　処理効率を上げるにはタプルを用いる。Haskellでは、カンマで区切られた要素を括弧で囲むことによってタプルを示す。次の実装では、連続するフィボナッチ数からなるタプルを作成する。その際、再帰の終了条件にカウンタを使用する。

fib_tuple.hs

module Main where
        fibTuple :: (Integer, Integer, Integer) -> (Integer, Integer, Integer)
        fibTuple (x, y, 0) = (x, y, 0)
        fibTuple (x, y, index) = fibTuple ( y, x + y, index -1 )

　figTupleは3要素のタプルを引数として受け取り、3要素のタプルを返す。この関数は、カウンタをカウントダウンするたびに、最初の2つの要素に、フィボナッチ数列内の連続する数値が入っていく。
　これを実行すると、

Prelude> :load fib_tuple.hs 
[1 of 1] Compiling Main             ( fib_tuple.hs, interpreted )
Ok, modules loaded: Main.
*Main> fibTuple(0, 1, 4)
(3,5,0)

　これの内部の動きは以下のようになっている。

fibTuple (0, 1, 4)
fibTuple (1, 1, 3)
fibTuple (2, 2, 2)
fibTuple (2, 3, 1)
fibTuple (3, 5, 0)

　また、答えとなる1番目の要素だけを取り出したいときには次のようにする。

fib_tuple.hs

module Main where
        fibTuple :: (Integer, Integer, Integer) -> (Integer, Integer, Integer)
        fibTuple (x, y, 0) = (x, y, 0)
        fibTuple (x, y, index) = fibTuple ( y, x + y, index -1 )

        fibResult :: (Integer, Integer, Integer) -> Integer
        fibResult (x, y, z) = x

        fib :: Integer -> Integer
        fib x = fibResult (fibTuple (0, 1, x))

　fibResultのところ(6,7行目)では、パターンマッチングを用いて1番目の要素(答え)を取り出しており、fibのところ(9,10行目)では、呼び出し形式を単純化している。
　これを実行する。fib関数は2つのヘルパー関数を使用して、非常に高速なフィボナッチ数列ジェネレータを構築しているので、求める桁数を大きくしても答えが一瞬で出る(計測はしていないので体感速度)。

Prelude> :load fib_tuple.hs 
[1 of 1] Compiling Main             ( fib_tuple.hs, interpreted )
Ok, modules loaded: Main.
*Main> fib 100
354224848179261915075
*Main> fib 1000
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875

タプルと合成

　ある関数の結果を別の関数に渡して関数をつなげることによって関数を組み合わせる必要がある場合がある。以下に、リストのtailとheadをマッチングさせることによってリストの2番目の要素を取り出す例を示す。先ほどの計算結果の続きに書く。

*Main> let second = head . tail
*Main> second [1, 2]
2
*Main> second [3, 4, 5]
4

　ここでは、コンソール内で関数を定義している。second = head . tailは、second lst = head (tail lst)と等価であるようだ。ある関数の結果を別の関数に渡すということらしい。この機能を用いて、別の方法でフィボナッチ数列を生成する。同様に1組のペアを計算する。ただし、今回はカウンタは使用しない。

fib_pair.hs

module Main where
        fibNextPair :: (Integer, Integer) -> (Integer, Integer)
        fibNextPair (x, y) = (y, x + y)

        fibNthPair :: Integer -> (Integer, Integer)
        fibNthPair 1 = (1, 1)
        fibNthPair n = fibNextPair (fibNthPair (n - 1))

        fib :: Integer -> Integer
        fib = fst . fibNthPair

　最初のブロックでは、2つの数を与えることで、常に、その次の数を計算している。2つ目のブロックでは、直前の項に基いて数列の次の項を再帰的に計算している。こうして求めた数列内の任意の1組のペアの最初の項を取り出しているのが最後のブロックである。
　このプログラムは別の言い方をすると、n番目のタプルの最初の要素を取り出したということになる。
　実行結果は以下のようになる。

Prelude> :load fib_pair.hs 
[1 of 1] Compiling Main             ( fib_pair.hs, interpreted )
Ok, modules loaded: Main.
*Main> fib 8
21
*Main> fib 4
3

リストの探索

　リストについての説明は割愛し、リストをヘッドとテールに分割する方法を説明する。

Prelude> let (h:t) = [1, 2, 3, 4]
Prelude> h
1
Prelude> t
[2,3,4]

　この例では、リスト[1, 2, 3, 4]を(h:t)にバインドしている。この構文はElangにも出てきたhead|tail構文と同じと考えて良いだろう(Scala, Prologも同じらしい)。この構文を使用することで、いくつかの簡単な再帰定義を行うことが出来る。
　以下に、リストのsizeとprod(面積)を求める関数を示す。

lists.hs

module Main where
        size [] = 0
        size (h:t) = 1 + size t

        prod [] = 1
        prod (h:t) = h * prod t

　リストのサイズは1にテールのサイズを加えたものである。これを実行すると、

Prelude> :load lists.hs 
[1 of 1] Compiling Main             ( lists.hs, interpreted )
Ok, modules loaded: Main.
*Main> size "Fascinating"
11

　リストのサイズなのに文字列を引数として与えているのはおかしいと感じるかもしれないが、Haskellでの文字列は単なる文字のリストだということを思い出してほしい。

　本書では、この後にリストを組み合わせるzipの説明をしているのだが、同じように実行してみても上手くいかなかった。ヴァージョンの関係だろうか？
　本書では、下記のように書いてある。

Prelude> zip "kirk" "spock"
[('kirk','spock')]
Prelude> zip ["kirk", "spock"]
[("kirk","spock")]

　しかし、実行してみると、

Prelude> zip "kirk" "spock"
[('k','s'),('i','p'),('r','o'),('k','c')]
Prelude> zip ["kirk", "spock"]

<interactive>:3:1:
    No instance for (Show ([b0] -> [([Char], b0)]))
      arising from a use of ‘print’
    In a stmt of an interactive GHCi command: print it

　ちなみに、エラーメッセージでググったら諦める or 関数適用した結果を表示するようにするというのが解決法みたいです。ghciで対話式にやろうとすると出来ないのか？

• GHCによるHaskellの3つの実行方法とHello World - Cutting-Edge Programming
• Haskell初心者が直面するghciで起こしがちなエラー4選とその対処法 - Qiita

リストなどを作り出す

　ここまで、リストを再帰的に処理する方法についていくつか見てきた。1日目最後のセクションでは、新しいリストを作り出す方法を勉強する。

再帰

　リストを構成する最も基本的な部品は:演算子である。この演算子によって、ヘッドとテールを結合してリストを作る。再帰関数を呼び出した時には、パターンマッチングで、この演算子を逆方向に使用した。次の例では、letの左辺に:を使用している。

Prelude> let h:t = [1, 2, 3]
Prelude> h
1
Prelude> t
[2,3]
Prelude> 1:[2, 3]
[1,2,3]
Prelude> [1]:[2, 3]

<interactive>:6:1:
    No instance for (Num [t0]) arising from a use of ‘it’
    In a stmt of an interactive GHCi command: print it
Prelude> [1]:[[2], [3, 4]]
[[1],[2],[3,4]]
Prelude> [1]:[]
[[1]]

　1行目では、リストを分解している。:演算子リストをリストを構築する際には、4行目のようにして使用する。
　また、リストには異なる型を混在させることは出来ないので、5行目ではエラーが発生している。
　しかし、6,7行目のように、リストをリストのリストにしたり、空リストに追加することは可能である。

　以下に、リストを構築する例を示す。リストから偶数を取り出して返す関数を作成したい場合に、リストの構築を使って書くことができる。

all_even.hs

module Main where
        allEven :: [Integer] -> [Integer]
        allEven [] = []
        allEven (h:t) = if even h then h:allEven t else allEven t

　この関数は、整数のリストを引数にとり、偶数のリストを返す。allEvenに空リストを渡すと、空のリストが返される。ヘッドが偶数のリストの場合は、そのヘッドと、テールにallEvenを適用した結果を連結する。ヘッドが奇数の場合は、それを破棄し、テールにallEvenを適用した結果のみを返す。

範囲と合成

　Haskellにはファーストクラスの範囲とそれらをサポートいくつかのシンタックスシュガーが用意されている。これは、RubyやScalaと同様らしい。Haskellの範囲は、次のように範囲の両端を指定する簡単な形式で表現する。

Prelude> [1..2]
[1,2]
Prelude> [1..4]
[1,2,3,4]

　両端を指定すると、範囲が計算される。デフォルトの増分は1である。デフォルトの増分では、終点に到達できない場合は空リストが返され、デフォルトの増分を指定するには、リスト内の2番目の要素も指定する。

Prelude> [1..2]
[1,2]
Prelude> [1..4]
[1,2,3,4]
Prelude> [12..4]
[]
Prelude> [10, 8 .. 4]
[10,8,6,4]
Prelude> [10, 9.5 .. 4]
[10.0,9.5,9.0,8.5,8.0,7.5,7.0,6.5,6.0,5.5,5.0,4.5,4.0]

　範囲は、数列を作成するためのシンタックスシュガーである。数列には終点はなくてもよいので、数列の一部の項を抜き出すことも可能である。これは、Clojureと同様らしい。

Prelude> take 5 [1 ..]
[1,2,3,4,5]
Prelude> take 5 [0, 2..]
[0,2,4,6,8]

リスト内包表記

　Haskellでも、Erlangと同じように動作する。左側には式を書き、右側には、ジェネレータやフィルタを書く。例として、リスト内のすべての要素を2倍してみる。

Prelude> [x * 2 | x <- [1, 2, 3]]
[2,4,6]

　これを文章にすると、「[1, 2, 3]から取り出した各要素xに対してx * 2を計算した結果をリストとして返せ」ということである。
　Erlangと同様、リスト内包表記でパターンマッチングを使用可能である。例えば、多角形を表す点のリストがある時、その多角形を対角線を対称軸として対称移動したいとする。それには、次のようにxとyを入れ替えれば良い。

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

　2行目では、4からxを引いて水平方向に反転している。

　組み合わせを計算することもできる。カーク、スポック、マッコイの3人のクルーから2人を上陸隊員として選ぶ時、可能な組み合わせをすべて見つけるという例で試してみる。

Prelude> let crew = ["kick", "Spock", "McCoy"]
Prelude> [(a, b) | a <- crew, b <- crew]
[("kick","kick"),("kick","Spock"),("kick","McCoy"),("Spock","kick"),("Spock","Spock"),("Spock","McCoy"),("McCoy","kick"),("McCoy","Spock"),("McCoy","McCoy")]
Prelude> [(a, b) | a <- crew, b <- crew, a /= b]
[("kick","Spock"),("kick","McCoy"),("Spock","kick"),("Spock","McCoy"),("McCoy","kick"),("McCoy","Spock")]
Prelude> [(a, b) | a <- crew, b <- crew, a < b]
[("Spock","kick"),("McCoy","kick"),("McCoy","Spock")]

　2行目では、重複要素が排除されていない。そこで、3行目では、フィルタリング要素を追加している。また、順序も関係ないので、ソートされた組だけを残し残りを無視するフィルタリング条件を追加する。

　このようにリスト内包表記で、リストを迅速に作成及び変換することができた。

1日目で学んだこと

　1日目では、Haskellの基本的なことを勉強した。