Haskell

出典: フリー百科事典『ウィキペディア（Wikipedia）』

Haskell
パラダイム 関数型言語
型付け 強い静的型付け
主な処理系 ghc、Hugs
影響を受けた言語 Miranda
影響を与えた言語 Factor
 表・話・編・歴 

■カテゴリ / ■テンプレート

Haskell（ハスケル）は非正格な評価を特徴とする純粋関数型プログラミング言語である。名称は論理学者であるハスケル・カリー(Haskell B. Curry)に由来する。

目次

[編集] 概要

Haskellは高階関数や静的多相型付け、定義可能な演算子、例外処理といった多くの言語で採用されている現代的な機能に加え、パターンマッチングやカリー化、リスト内包表記、ガードといった多くの特徴的な機能を持っている。また、遅延評価や再帰的な関数や代数的データ型もサポートしているほか、独自の概念として圏論のアイデアを利用し参照透過性を壊すことなく副作用のある操作(例えば 代入、入出力、配列など)を実現するモナドを含む。このような機能の組み合わせにより、手続き型プログラミング言語では記述が複雑になる関数でもHaskellではたいていは実装が容易になる。

Haskellは遅延関数言語として多くの研究が実施されている。あわせてParallel Haskellと呼ばれるMITやGlasgowによるものをはじめ、他にもDistributed Haskell(かつてはGoffinと呼ばれていた)やEdenといった配布バージョン、Eager Haskellと呼ばれる投機的実行バージョン、Haskell++やO'Haskell、Mondrianといったオブジェクト指向バージョンも複数存在しているなど、いくつもの派生形が開発されてきている。

GUI開発向けサポートの新しい方法を提供する、Concurrent Cleanと呼ばれるHaskellに似た言語もある。Haskellと Concurrent Clean の最大の違いは、モナドを代用する一意型の採用である。

Haskellは比較的小規模なユーザコミュニティを持つが、その力はいくつかのプロジェクトで十分に生かされてきた。Audrey TangによるPugsはPerl 6のインタプリタとコンパイラを含む率直な実装で、書くのにたったの数ヶ月しかかからなかったなどHaskellの有用性を証明するものである。Darcsはさまざまな革新的な機能を含むリビジョンコントロールシステムである。Linspire Linux はHaskellをシステムツール開発に選択した。

Haskellの急速な進化は今も継続しており、HugsやGHCは現在の事実上の標準の処理系であるといえる。

ICFP Programming Contestでは2001年、2004年、2005年で First prize に選ばれている。

[編集] 歴史

1985年の Research Software による Miranda の発表のあと、遅延関数言語におけるその影響は高まった。[要出典]1987年には非正格で純粋関数型プログラミング言語が1ダース以上存在していた。このうち、Mirandaが最も広く使われていたが、これはパブリックドメインではなかった。オレゴン州ポートランドで開催された Functional Programming Languages and Computer Architecture (FPCA '87) のカンファレンスにおいて、コミュニティは　そのような言語のためのオープン標準を作成するコミュニティが発足されるべき、という強い合意が参加者のあいだで形成されたときに会議が開かれた。 関数型言語のデザインにおける将来の研究のための基礎として役立つ、ひとつの共通の言語へと既存の関数型言語を統合することが、コミュニティの目的であった。[1]

最初のバージョンの Haskell ("Haskell 1.0") は1990年に作成された。[2]コミュニティの活動は一連の言語仕様を結果に残した。1997年後半、シリーズは、安定して小さく過般なバージョンの言語と付属の教育のための基本ライブラリ、将来の拡張の基礎などを定義した、Haskell 98 に到達した。実験的な機能の付加や統合を通じての拡張の作成や Haskell98 の派生物を、コミュニティは明らかに歓迎した。[1]1990年2月、 Haskell98 言語標準は最初に "The Haskell 98 Report" として発表された。[1]2003年1月、改定されたバージョンが "Haskell 98 Language and Libraries: The Revised Report" として発表された。[3]GHC に代表されるように、Haskell は急速な発達が継続している。2006年前半、非公式に Haskell′ ("Haskell Prime") と呼ばれている Haskell 98 standard の後継の作成プロセスが開始された。[4]このプロセスは Haskell 98 のマイナーバージョンアップを目的としている。[5]

[編集] 特徴的な機能

[編集] 遅延評価

Haskellは遅延評価を評価戦略とする。ほとんどの言語では関数の呼び出しにおいて引数に与えられたすべての式を評価してから、呼び出された関数に渡す先行評価をする。これに対し、Haskell ではあらゆる式はそれが必要になるまで評価されない。次のHaskellのコードは、評価できない未定義の式を含む。

 main = print (const 42 (1 `div` 0))

`div` は整数の除算を行う演算子である。1 / 0 は未定義であり、評価すればエラーになる。しかし上記のコードは Haskell において正常に実行される。const は常に第一引数を返す定数関数であり、第二引数は無視されるので評価されない。このため、(1 `div` 0) は評価されず、エラーにはならない。正格評価をする言語では、このような式はゼロ除算によるエラーになるであろう。遅延評価がデフォルトで行われることにより、不要な計算は省かれ、参照透過性により同じ式を複数回評価する必要もなくなるため、Haskell では計算効率の向上が期待できる。ただし必要に応じて正格評価もできる。

[編集] 型推論

Haskellでは関数の型を明示しなくても処理系が自動的に型を推論する。以下は型の宣言を省略し、本体のみを宣言した平方を返す関数squareである。

 square x = x * x

この場合squareの型は型推論され、次のように明示的に型を宣言したのと同じになる。

 square :: (Num a) => a -> a
 square x = x * x

この宣言は、「Numのインスタンス[6]である a の型の値を引数にとり、a の型の値を返す」と読める。ここでは「*」演算子が適用可能な最も広い型である Num a が選択されており、整数や不動小数点数、有理数のような Num のインスタンスであるあらゆる型の値を渡すことができる。また、次のように宣言すれば Integer　(整数)のみが渡せる関数になる。

 square :: Integer -> Integer
 square x = x * x

型推論のため、Haskellは型安全でありながらほとんどの部分で型宣言を省略できる。[7]

[編集] 代数的データ型

Haskellのデータ型には「代数的データ型(algebraic data type)」と呼ばれるC言語などでいう構造体や列挙体の性質を兼ね備えたものが用いられる。次の例は二つのInt型の値をフィールドに持つ二次元の座標、Point2D型を定義したもので、これは代数的データ型の構造体的な性質を示す。先頭のトークン「data」は代数的データ型の宣言であることを示す予約語である。ここで最初のPoint2Dはデータ型名を表し、次のPoint2Dはデータコンストラクタ名を示す(データ型名とデータコンストラクタ名は同じでも構わない)。データコンストラクタは値を定義するための特殊な関数といえる。

 data Point2D = Point2D Int Int

次の例はトランプの4つのスーツを示すSuit型を定義したものである。Spade、Heart、Club、Diamondの4つのデータコンストラクタが定義されており、Suit型の式はSpade、Heart、Club、Diamondのいずれかの値をとる。

 data Suit = Spade | Heart | Club | Diamond

次の例はInt型の値を格納する二分木の型である。Leaf(葉)はInt型の値を持ち、Branch(枝)はLeafもしくはBranchであるTree型の変数を二つ持つ。これは代数的データ型の構造体的な性質と列挙体的な性質の両方が現れている。

 data Tree = Leaf Int | Branch Tree Tree

[編集] 関数の部分適用

Haskellでは2つの引数を持つ関数は、1つの引数をとり「1つの引数をとる関数」を返す関数と同義である。このように、関数を返すことで全ての関数を1つの引数の関数として表現することをカリー化という。次の例は2つの引数をとり、そのうち値が大きい値を返す関数maxである。

 max a b = if a > b then a else b

この関数maxは無名関数を用いて次のように書き換えることができる。先ほどの表現とまったく同様に動作するが、この表現では関数を返す様子がよりわかりやすく現れている。

 max a = (\b -> if a > b then a else b)

このような性質のため、Haskellのあらゆる関数は引数を部分適用することができる。関数の引数を全て与えないことで、一部の変数だけが渡された別の関数を作り出すことができる。次の例は引数が10以下の場合は10を返す関数greaterThan10を関数maxの部分適用を用いて定義したものである。

 greaterThan10 = max 10

また、Haskellでは演算子を部分適用することすら可能である。次の例は引数に20を加える関数である。

 plus20 = (+ 20)

このような演算子の部分適用をとくにセクション(section)と呼ぶ。

[編集] 型クラス

型クラス(type class)は異なるデータ型に共通する操作を定義する。以下の型クラスComparerは値の順序を調べる関数orderを定義する型クラスで、order x y はx yが昇順のときは負の値、降順の時は正の値、xとyが等しいときは0を返すものとする。ここでclassは型クラスの宣言であることを示す予約語である。

 class Comparer a where
     order :: a -> a -> Int

型クラスを実装するには、対象のデータ型に対してインスタンス宣言を行う。 次は型 [a] の型クラスComparerに対するインスタンスを宣言したものである。このインスタンスでは、文字列を辞書順に比較している。ここで関数fromEnum cは文字cを数値に変換する関数である。

 instance Enum a => Comparer [a] where
     order [] [] = 0
     order _ [] = 1
     order [] _ = -1
     order (x:xs) (y:ys) = let s = fromEnum x - fromEnum y in if s /= 0 then s else order xs ys

次にリストをソートする関数sortを示す。この関数は型クラスComparerのインスタンスを持つ全ての型の値に適用できる、一般化された関数である。

 sort :: Comparer a => [a] -> [a]
 sort [] = []
 sort (x:xs) = sort [e | e <- xs, order e x < 0] ++ [x] ++ sort [e | e <- xs, order e x >=  0]

[編集] リストとリスト内包表記

Haskellで順序付けられた複数の値を扱うのにもっとも柔軟で簡潔な方法はリストを用いることである。次は四季の名前のリストである。

 ["Spring", "Summer", "Autumn", "Winter"]

次は初項10、公差4の等差数列のリストである。このリストは無限リストであり、その長さは無限大である。

 [10, 14..]

次の式は先ほどの数列の先頭20項を要素に持つリストである。take n l はリストlの先頭n個の項を要素に持つリストを返す関数である。

 take 20 [10, 14..]

もし正格な動作を持つ言語でこのような定義をしようとすると関数takeに値を渡す前に無限リストを生成することになるが、長さが無限のため無限リストの生成が終わることはなく関数takeがいつまでも呼び出されなくなってしまう。Haskellは遅延評価されるため、このようなリストを定義しても必要になるまで必要な項の値の生成は遅延される。このように無限リストを扱えるのはHaskellの大きな強みである。次は素数列をリスト内包表記を用いて定義した一例である。

 primes :: [Int]
 primes = [x | x <- [2..], and [rem x y /= 0 | y <- [2 .. x - 1]]]

リストはその柔軟性から再帰的な関数での値の受け渡しに向いているが、任意の位置の要素にアクセスするためには参照を先頭からたどる必要があったり、要素を変更するたびにリストの一部を作り直さなければならないことから、ランダムアクセスが遅い欠点がある。このためHaskellにも配列が用意されており、高速な参照や更新が必要なプログラムではリストの代わりに配列を用いることでパフォーマンスを改善できる可能性がある。

[編集] 入出力

副作用のある処理の扱いはHaskellでも最も特徴的な部分であり、入出力ではそれが最も頻繁に現れる。次はHaskellによるHello worldの一例である。

 main :: IO ()
 main = putStrLn "Hello,World!"

Haskellは純粋関数型言語であり、mainもやはり参照透過である(副作用はない)。しかし処理系はmainとして定義された IO a 型の値をそのプログラムの動作を示す値として特別に扱う。putStrLn は標準出力に文字列を出力する動作を表す IO a 型の値を返す関数であり、実行すると引数として渡された "Hello,World!" を出力する。次に標準出力から一行読み込み、そのまま標準出力に出力するechoプログラムを考える。次のような、C言語等などのような表記はできない。getLine 関数は標準入力から一行読み取る関数である。

 main = putStrLn getLine --コンパイルエラー！

getLine と putStrLn はそれぞれ次のような型を持っている。

 getLine :: IO String
 
 putStrLn :: String -> IO ()

純粋関数型である Haskell では getLine もやはり副作用はなく、getLine は一行読み込むという動作を表す値を常に返す。このように入出力の動作を表す値をアクション(action)と呼ぶ。getLine が返すのは String そのものではなくあくまで IO String という型を持ったアクションであって 、それを putStrLn の引数に与えることはできない。正しいEchoプログラムの一例は次のようになる。

 main :: IO ()
 main = getLine >>= putStrLn

ここでは演算子 >>= によってふたつのアクションを連結している。このとき、main は一行読み込みそれを出力するというアクションとなり、このプログラムを実行すると処理系は main が持つアクションの内容を実行する。

[編集] 実例

以下の単純な例は関数型言語としての構文の実例にしばしば用いられるもので、Haskellで示された階乗関数である。

 fac :: Integer -> Integer
 fac 0 = 1
 fac n | n > 0 = n * fac (n-1)

階乗を単一の条件による終端を伴う再帰的関数として表現している。これは数学の教科書でみられる階乗の表現に似ている。haskellコードの大半は、その簡潔さと構文において基本的な数学的記法と似通っている。

階乗関数に示されている1行目は省略可能であり、この関数の型を示す。これは「関数fac(fac)はIntegerからIntegerへ(Integer -> Integer)の型を持つ(::)」と読める。これは整数を引数としてとり、別の整数を返す。もしプログラマが型注釈を与えない場合、この定義の型は自動的に推測される。

2行目ではHaskellの重要な機能であるパターンマッチングに頼っている。関数のパラメータが丸括弧で囲まれておらず、しかし空白で区切られていることに注意されたい。関数の引数が0であれば、これは整数1を返す。その他の場合は3行目が試される。これは再帰的な呼び出しで、基準となる場合に達するまで繰り返し関数が実行される。

ガードは階乗が定義されない負の値から3行目を保護している。このガードが無ければこの関数は0の終端条件に達することなく、再帰してすべての負の値を経由してしまう。実際、このパターンマッチングは完全ではない。もし関数facに負の整数が引数として渡されると、このプログラムは実行時エラーとともに落ちるであろう。最後のケースではエラー条件がチェックされ、代わりに適切なエラーメッセージを出力することができる。

[編集] より複合的な例

引数fを伴う高階関数で表現された単純な逆ポーランド記法評価器が、パターンマッチングと型クラスReadを用いたwhere節で定義されている。

 calc :: String -> [Float]
 calc = foldl f [] . words
   where 
     f (x:y:zs) "+" = y+x:zs
     f (x:y:zs) "-" = y-x:zs
     f (x:y:zs) "*" = y*x:zs
     f (x:y:zs) "/" = y/x:zs
     f xs y = read y : xs

空リストを初期状態とし、fを使って一語ずつ文字列を解釈していく。fは、注目している語が演算子ならばその演算を実行し、それ以外ならば浮動小数点として計算スタックに積んでいる。

次の定義は線形時間でフィボナッチ数列のリストを生成する。

 fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

無限リストはcorecursion――リストの後ろの値は要求があったときに0と1の二つの初期要素から開始され算出される――によって実現される。このような定義は遅延評価の実例で、Haskellプログラミングでも重要な部分である。

どのように評価が解決されるかの例示のために、次は6つの要素の計算の後のfibsとtail fibsの値と、どのようにzipWith (+)が4つの要素を生成し、次の値を生成し続けるかを図示したものである。

 fibs         = 0 : 1 : 1 : 2 : 3 : 5 : ...
                +   +   +   +   +   +
 tail fibs    = 1 : 1 : 2 : 3 : 5 : ...
                =   =   =   =   =   =
 zipWith ...  = 1 : 2 : 3 : 5 : '''8''' : ...
 fibs = 0 : 1 : 1 : 2 : 3 : 5 : '''8''' : ...

次はGHCの拡張で、リストの並列内包表記(GHCの拡張は特別なコマンドラインフラグによって有効にしなければならない。詳しくはGHCのマニュアルを参照のこと)を用いて書かれた同様の関数である。

 fibs = 0 : 1 : [ a+b | a <- fibs | b <- tail fibs ]

先に見た階乗の定義は、次のように関数の列を内包表記で生成して書く事もできる。

 fac n = (foldl (.) id [(*k) | k <- [1..n]]) 1

特に簡潔に書ける例として、ハミング数が順番に並ぶリストを返す以下のような関数がある。

 hamming = 1 : map (*2) hamming # map (*3) hamming # map (*5) hamming
     where xxs@(x:xs) # yys@(y:ys)
               | x==y = x : xs#ys
               | x<y  = x : xs#yys
               | x>y  = y : xxs#ys

上に示されたさまざまなfibsの定義のように、これはオンデマンドに数のリストを実現するために無限リストを使っており、1という先頭要素から後続の要素を生成している。

ここでは、後続要素の構築関数はwhere節内の記号#で表現された中置演算子で定義されている。適用の構文は異なるが、演算子は識別子が記号からなる関数である。

各|は、等号の前半の条件部分と、後半の定義部分からなるガード節を構成する。

文字列を出力する例については「Hello worldプログラムの一覧#Haskell」を参照

[編集] 批判

Haskellは他のプログラミング言語には見られない多くの先進的機能を持っているが、これらの機能のいくつかは言語を複雑にしすぎており、理解が困難であると批判されてきた。とりわけ、関数型プログラミング言語と主流でないプログラミング言語に対する批判はHaskellにもあてはまる。加えて、Haskellの潔癖さとその理論中心の起源に起因する不満がある。

2002年にJan-Willem Maessen、2003年にSimon Peyton Jonesが遅延評価に関連するこの問題を議論し、その上でこの理論的動機を認識した。彼らは実行時のオーバーヘッドの悪化に加え、遅延はコードのパフォーマンスの推察をより困難にすると言及した。

2003年にBastiaan HeerenとDaan Leijen、Arjan van IJzendoornはHaskellの学習者にとってのつまづきに気がついた。これを解決するために、彼らはHeliumと呼ばれる新たなインタプリタを開発し、この中でいくつかの型クラスのサポートを取り除き、Haskellの機能の一般化を制限することによってエラーメッセージのユーザ親和性を改善した。

[編集] 実装

以下はHaskell 98仕様を完全に満たす、または仕様に非常に近く、オープンソースライセンスの下で配布されているものである。ここには現在のところ商用のHaskell実装は含まれない。

  • Glasgow Haskell Compiler [1]. The Glasgow Haskell Compiler は異なる複数のアーキテクチャのネイティブコードへコンパイルできるほか、C言語へコンパイルすることもできる。おそらくGHCは最も知られたHaskellコンパイラで、現在のところGHCのみで動くかなり便利ないくつかのライブラリ(たとえはOpenGLのバインディングなど)を含む。
  • Gofer Haskellの教育的バージョン。 GoferはMark Jonesにより開発された。これはHugsに取って代わられた。
  • HBC [2] は別のネイティブコードHaskellコンパイラ。これはしばらくの間開発が活発ではなくなっているが、未だに利用可能である。
  • Helium [3] は新しいHaskellの方言である。開発の際の焦点は、明瞭なエラーメッセージを提供し学習を容易にすることである。Heliumは型クラスをサポートせず、多くのHaskellプログラムとは互換性のない実装である。
  • Hugs [4] はバイトコードインタプリタ。これは速いプログラム編集とそれなりの実行スピードを提供する。これは単純なグラフィックスライブラリを含む。多くの人がHaskellの基本を学ぶのによいが、これはオモチャ的な実装であるということではない。これは最も可搬で軽量なHaskell実装である。
  • Jhc [5] は新しいプログラム変換の研究用としてのみならず、スピードと生成されるプログラムの効率を重視したJohn Meachamによって書かれたHaskellコンパイラである。
  • nhc98 [6] は別のバイトコードコンパイラであるが、そのバイトコードはHugsより顕著に速く走る。Nhc98は省メモリ使用に焦点を絞っており、古いマシンや遅いマシンにはとりわけよい選択肢となる。
  • yhc [7] はnhc98のフォークで、単純かつ可搬で効率的、integrating Hatのサポートを目標とする。

[編集] 関連

  • en:O'Haskellはオブジェクト指向と並列プログラミングを提供するHaskellの拡張である。

[編集] 参照

[編集] 外部リンク

[編集] 脚注

  1. ^ a b c "Preface". Haskell 98 Language and Libraries: The Revised Report (December 2002). "2009-06-23" 閲覧。
  2. ^ "The History of Haskell". "2009-06-23" 閲覧。
  3. ^ Simon Peyton Jones (editor) (December 2002). "Haskell 98 Language and Libraries: The Revised Report". "2009-06-23" 閲覧。
  4. ^ "Future development of Haskell". "2009-06-23" 閲覧。
  5. ^ "Welcome to Haskell'". The Haskell' Wiki. "2009-06-23" 閲覧。
  6. ^ Haskellの型システムにおける汎用型が実体化されたもの。オブジェクト指向における『インスタンス』とは異なる。
  7. ^ ただし、型を明示することは可読性を向上したり問題の発見に役立つため、常に省略するのがよいとは限らない。
"http://ja.wikipedia.org/wiki/Haskell" より作成