Haskell 言語、立木秀樹 処理系； ghc 標準的に使われているコンパイラシステム ghci ghc に付随した、インターラクティブ環境 WinHugs, および、hugs： 手軽に使えるバイトマシン WinHugs と hugs は、メディアセンタパソコンにインストールされているので、 これを用いて解説する。 Haskell の特徴： 変数がない。 変数とは値を記憶する場所のこと。値に名前をつける操作(束縛)はある が、その名前と値の対応を変化させる方法がないので、これは変数では ない。名前の意味する値は変わらないことに注意。 変数という状態を中心に考え、それを変化させることにより計算を行う という、Ｃなどの手続き的な言語と考え方が大きく異なる。 手続きではなく、関数に基づいている。 コンピュータの現在の状態というのは、メモリに記憶している値のこと。 それは、プログラミング言語では変数として扱われる。それに従ってコ ンピュータは動作するので、同じ手続きを呼び出しても、結果が異なる のが普通である。それに対して、Haskell では、変数がないので、同じ 手続きは同じ値を返す。Ｃ言語などの多くのプログラミング言語では手 続きのことを関数というが、Haskell の関数は、値を求めて返すという ことしか行わず、その値は、引数が同じなら必ず同じなので、数学でい う関数と全く同じように考えることができる。 値を変化させるものを表現する方法もあるが、中心ではない。 繰り返し文がない。 変数がないので、繰り返しもない。 繰り返し的な処理は、再帰呼び出しで実現する。 「文」がなく、あるのは式だけである。 C 言語などのプログラミング言語では、値を意味する式の他に、コン ピュータに対する命令を意味する分の概念があり、代入文、for 文、 while 文、if 文などがある。Haskell には、値を意味する式だけが存 在する。 型システムが存在する。 値は、Int, Char などの方を持っている。 型推論があるので、型を明示的に書く必要がない。 リストが使える。 リストというのは、同じ型の値を並べたもの。非常に便利なデータの表 現方法。 高階関数が使える。 関数も値である。よって、それを、関数の引数に渡すことができる。 １．インターラクティブ環境の使い方 WinHugs （あるいは hugs）を起動すると、Hugs> というプロンプトが現れる。 ここに式を打ち込むと、その値を表示してくれる。 Hugs> 1+2 「Enter」 3 Hugs> sqrt 3 関数適用の時に、括弧はいらない。 1.73205080756888 Hugs> [1,2,3] リストはこのように表記する。 [1,2,3] Hugs> [1,2,3]++[4,5,6] ++ は、リストを結合する操作である。 [1,2,3,4,5,6] Hugs> [] これは、空のリスト [] Main> (1,'a') これは、ペアー（２つ組） (1,'a') *練習*：いろんな式を入力してみよう 式には型がついている。型は、:t により表示できる。 Hugs> :t 1 1 :: Num a => a これは、1 が、Num という種類に属する型 a に対し、a という形に属すること を意味している。それぞれの式は、複数の型に属することが許される。Num に 属する型としては、Int, Integer, Float, Double などがある。Int は、Ｃ言 語などでの整数の型と同じ、32 ビットで表現できる(-2^31 から 2^31-1 まで の)整数の型である。Integer は、そのような数の制限のない整数の型である。 Float 、Double は、実数の近似値を16ビットおよび、32 ビットで表現したも のの型である。ただ単に 1 と書いたのでは、このどれに属する可能性もあるの で、Num に属するどの型にも属しているという、このような結果が出ている。 型を明示的に指定することもできる。 Hugs> 1::Int 1 Hugs> 11111111111111111111::Integer 11111111111111111111 Hugs> 11111111111111111111::Int Program error: arithmetic overflow Hugs> :t 1+2 1+2 :: Num a => a Hugs> (1::Int)+2 3 Hugs> :t (1::Int)+2 1 + 2 :: Int Hugs> :t [1,2,3] [1,2,3] :: Num a => [a] これは、[1,2,3] が、Num という種類に属する型 a に対し、[a] という型（す なわち、aのリストに属することを意味している。 Main> :t (1, 'a') (1,'a') :: Num a => (a,Char) ぺこれは、(1,2) が、Num という種類に属する型 a に対し、(a,Char) という 組の型に属するということである。このように、リストではすべての要素の型 が等しくなくてはならず、その型は、リストの長さの情報を持たない（つまり、 長さの違うものも同じ型に属する）が、ペアでは、要素の型は異なっていても よくて、その型は、それぞれの型のペアである。 Hugs> :t sqrt sqrt :: Floating a => a -> a これは、sqrt が、Floating という種類に属する型 a に対し、a -> a という 型（すなわち、aからaへの関数の型）に属することを意味している。 Floating には、Double, Float などが属する。 Hugs> 2::Float 2.0 Hugs> :t sqrt (2::Float) sqrt 2 :: Float :browse （あるいは、:b）で、今定義されている関数の一覧が表示される。 Hugs.Prelude というモジュールに、標準的な関数が定義されている。 その一覧は、 Hugs> :browse Hugs.Prelude で見ることができる。 :t, :browse などの Hugs システムに対するコマンドの一覧（ヘルプ）は、 :? で得られる。 *練習*：hugs の終了方法を調べよ。 ２関数定義 関数は、インターラクティブ環境で定義できない。エディタで制作してファイ ルに保存して、:l で読み込む。（あるいは、メニューでオープンで読み込む） 必要がある。 :cd でディレクトリの移動 !pwd で現在のディレクトリの表示 (!... でシェルコマンドを起動できる) ただし、! は、WinHugs では使えないかもしれない。 プログラムファイルは、.hs という拡張子をつける。 ファイル（名前は何でもよい。lesson1.hs など) を用意して、 square x = x * x とだけ書いて、保存しよう。そして、それを読み込もう。読み込むには、 :l lesson1.hs あるいは、メニューから読み込む。 プロンプトが Main （Main モジュールに読み込まれた。モジュールについては 省略）に変わるはずである。読み込んだのちに、:b をしてみよう。 Main> :b module Main where square :: Num a => a -> a Main> square 5 25 Main> square 4.5 20.25 square 5 と 入力したら、Haskell は、square の定義に従い、 式の変形をしていくことで計算を行う。定義で x を 5 に置き換えると square 5 = 5 * 5 となるので、5 * 5 を計算しようとして、25 を得る。 以下の説明の中で、プログラムファイルに書く内容と、Haskell での実行とを 区別しながら読んでほしい。Haskell での実行は、Main> といったプロンプト がついている。 square の型は、Num に属する型 a に対し、a -> a であるということである。 つまり、Int -> Int でもあるし、Float->Float でもあるということだ。Ｃな どの言語では、Int 用の関数と Float 用の関数は別に書かなくてはならなかっ た。それに対し、このように、一つの式がたくさんの型をとれることを、多相型 とよんでいる。 関数は、再帰的に書くことができる。 fac1 n = if (n == 0) then 1 else (fac1 (n-1)) * n これを lesson1.hs に追加して、読み込んで、fac1 10 を実行してみよう。 if は、if *** then *A* else *B* の形で用いる。*A* と *B* は同じ型でないといけない。 *** が True の時には *A*, False の時には *B* だということを意味している。 (a == b) というのは、a と b が等しい時 True, それ以外の時 False である。 fac1 5 は、次のような等式変形に従い計算が行われると考えればよい。 （実際の計算過程は微妙に違う。それについては後述）。 fac1 5 = if (5 == 0) then 1 else (fac1 (5-1)) * 5 = if False then 1 else (fac1 (5-1)) * 5 = (fac1 (5-1)) * 5 = (fac1 4) * 5 = (if (4 == 0) then 1 else (fac1 (4-1)) * 4) * 5 = ((fac1 3) * 4) * 5 = ((if (3 == 0) then 1 else (fac1 (3-1)) * 3) * 4) * 5 = (((fac1 2) * 3) * 4) * 5 = (((if (2 == 0) then 1 else (fac1 (2-1)) * 2) * 3) * 4) * 5 = ((((fac1 1) * 2) * 3) * 4) * 5 = ((((if (1 == 0) then 1 else (fac1 (1-1)) * 1)* 2) * 3) * 4) * 5 = (((((fac1 0) * 1) * 2) * 3) * 4) * 5 = (((((if (0 == 0) then 1 else (fac1 (0-1)) * 0) 1)* 2) * 3) * 4) * 5 = ((((1 * 1)* 2) * 3) * 4) * 5 = (((1 * 2) * 3) * 4) * 5 = ((2 * 3) * 4) * 5 = (6 * 4) * 5 = 24 * 5 = 120 同じ関数は、次のように書いてもよい（引数のパターンマッチ） fac 0 = 1 fac n = n * fac (n-1) 引数のパターンマッチは、上から順に調べて、引数にマッチするものが見つか ればそれを採用する。よって、この二行の順番を変えると、正しく動かない。 また、次のようにすれば、後ろの定義は、n>0の時だけ有効になる。 このように、| の後、= の前に条件（ガードという）を書くことにより、 ガードの条件が満たされる時のみ、この定義を採用することになる。 fact 0 = 1 fact n | n > 0 = n * fact (n-1) この両者の違いは、引数が負の数の時に現れる。 Main> fac (-1) ERROR - C stack overflow Main> fact (-1) Program error: pattern match failure: fact (-1) fac -1 と書くと、(fac -) 1 と解釈されてしまうので、fac (-1) と書く必要 がある。両方ともエラーであるが、前者のスタックオーバーフローは、fac (-1) から fac (-2) が呼ばれ、... と、再起呼び出しがあまりに深く行われて、 スタック領域がなくなってしまったというエラーである。Ｃ言語などだと、無 限ループに入ってしまい実行が止まらないというのに対応している。それに対 して後者は、 fact (-1) に対応する定義がありませんというものである。後者 の書き方だと、fact の２つの行の順番を逆にしても、プログラムは正しく動作 する。 Main> fact 100 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 このように、Haskell では、無限多倍長計算が実行され、いくらでも大きな数 が表現されるが、そのぶん、実行は遅い。無限多倍長で表現された整数の型は、 Integer である。通常の32ビットの整数の型は Int である。Int として計算を させたければ、fact の定義のところに そのようなfact の型をプログラムに書 けばよい。 factint:: Int -> Int factint 0 = 1 factint n | n > 0 = n * factint (n-1) Main> factint 100 0 Main> :t factint fact :: Int -> Int -- フィボナッチ関数 fib 0 = 1 fib 1 = 1 fib n = (fib (n-1)) + (fib (n-2)) これは、フィボナッチ数を求めるプログラムである。しかし、これは明らかに 効率が悪い。fib 40 を求めることも不可能だろう。これを効率よく書き換える ことを考えよう。 まず、let という、値に名前をつける方法を説明する。(fib 10) * 3 を計算す るのに、「fib 10 を y とおいて、y * 3」と、途中の計算結果に名前をつける ような書き方もできる。それが、let ... in ... である。 Main> let y = fib 10 in y * 3 267 また、Haskell では、ペアを帰すことができる。ペアは、let (y,z) = ... in ... という具合に、名前のペアにパターンマッチさせることにより、要素ごと に名前をつけることができる。これを用いて、fibf という、fib n-1 と fib n のペアを返す関数を再帰的に書き、それを用いて fib (fibb と名前にした) を定義しよう。 fibf 0 = (1,1) fibf n = let (y,z) = fibf (n-1) in (z, y+z) fibb n = let (y,z) = fibf n in y ３ 高階関数 ちょっとした関数は、名前をつけていちいち定義するのは面倒である。それに 対し、関数を 名前をつけずに(\x -> ...) という記法で書くことができる（無 名関数）。\ は、バックスラッシュ文字として表示されることもある。 Main> (\x -> x * x) 4 16 プログラムファイルは、値に名前をつけた定義をしている。モジュールとは、 このような名前付けの環境である。たとえば、プログラムファイルに zz = 10 と書けば、10 という値に zz という名前がつけられる。関数定義も同じである。 関数に名前をつけているにすぎない。よって、square は、次のように書いてもよい。 square = \x -> x * x 次のように書いたのは、その略記法である。 square x = x*x 関数は、関数を引数としてとったり関数を値として返すことができる。たとえ ば、関数をもらい、それを2回繰り返し適用する関数を返す関数を考える。 twice f = \x -> f (f x) Main> :t twice twice :: (a -> a) -> a -> a -> において括弧は右に結合する。よって、これは、(a -> a) -> (a -> a) の 意味である。ここでは、a は、どんな型でも構わないので、a に対する条件が ついていないことに注意。 Main> :t factint factint :: Int -> Int Main> :t twice factint twice factint :: Int -> Int Main> :t twice factint 3 twice factint 3 :: Int Main> twice factint 3 720 これは、(twice factint) 3 の意味である。 (twice factint) 3 = (\x -> factint (factint x)) 3 = factint (factint 3) = factint 6 = 720 もちろん、twice は、 twice = \f -> (\x -> f (f x)) と書いても同じである。また、逆に、 twice f x = f (f x) と書いても同じである。このように見れば、twice というのは、２つ引数をと る関数と考えることができる。twice fact 3 というのは、(twice fact) 3 で あるが、twice という関数に fact と 3 という２つのものを適用していると考 えることもできる。 このように、２つ引数をとる関数は、関数を返す関数と考えることができる （これを、2引数関数のカリー化という）。実際、Haskell は、2引数の関数は、 それをカリー化した関数を返す関数として扱う。 *, +, -, / などの演算記号のことをオペレータという。オペレータは、2引数 の関数であるが、我々が普通に式を書くように、引数の間に演算記号を書く。 (*), (+) などと括弧をつけると、オペレータの意味する関数を意味することになる。 Main> 2+3 5 Main> (+) 2 3 5 Main> :t (+) (+) :: Num a => a -> a -> a 括弧をつける時に、片方の引数だけを渡すことができる。 これにより、1引数の関数ができる。 Main> (* 2) 3 6 Main> (/ 2) 3 1.5 Main> (2 /) 3 0.666666666666667 大小比較の > などのオペレータも同様である。これは、数を２つもらい、真偽値 (True か False) を返す関数である。 Main> :t (>) (>) :: Ord a => a -> a -> Bool 真偽値は Bool という型に属する。Ord は、大小比較ができるような型の属す る種類である。 Main> 3 > 2 True Main> (> 2) 3 True Main> (2 >) 3 False Main> twice (* 2) 3 12 Main> twice (twice (* 2)) 3 48 *練習*：これらが、なぜこうなるのか、考えてみよう。