|
Haskell
Haskell（ハスケル）は非正格な評価を特徴とする純粋関数型プログラミング言語である。名称は数学者であり論理学者であるハスケル・カリーに由来する。 概要Haskell は高階関数や静的多相型付け、定義可能な演算子、例外処理といった多くの言語で採用されている現代的な機能に加え、パターンマッチングやカリー化、リスト内包表記、ガードといった多くの特徴的な機能を持っている。また、遅延評価や再帰的な関数や代数的データ型もサポートしているほか、独自の概念として圏論のアイデアを利用し参照透過性を壊すことなく副作用のある操作（例えば 代入、入出力、配列など）を実現するモナドを含む。このような機能の組み合わせにより、手続き型プログラミング言語では記述が複雑になるような処理がしばしば簡潔になるばかりではなく、必要に応じて手続き型プログラミングを利用できる。 Haskell は関数型プログラミングの研究対象として人気が高い。あわせて Parallel Haskell と呼ばれるマサチューセッツ工科大学やグラスゴー大学によるものをはじめ、他にも Distributed Haskell[2] や Eden といった分散バージョン、Eager Haskell と呼ばれる投機的実行バージョン、Haskell++ や O'Haskell、Mondrian といったオブジェクト指向バージョンも複数存在しているなど、いくつもの派生形が開発されてきている。 GUI開発向けサポートの新しい方法を提供する、Concurrent Clean と呼ばれる Haskell に似た言語もある。Haskell と Concurrent Clean の最大の違いは、モナドを代用する一意型の採用である。 Haskell は比較的小規模なユーザコミュニティを持つが、その力はいくつかのプロジェクトで十分に生かされてきた。オードリー・タンによる Pugs は Perl6 のインタプリタとコンパイラの実装で、書くのにたったの数ヶ月しかかからなかったなど Haskell の有用性を証明するものである（現在は開発停止）。Darcs はさまざまな革新的な機能を含むリビジョンコントロールシステムである。Linspire Linux は Haskell をシステムツール開発に選択した。 Haskell の急速な進化は今も継続しており、Glasgow Haskell Compiler（GHC）は現在の事実上の標準の処理系であるといえる。 ICFP Programming Contestでは2001、2004、2005、2010、2013、2014、2015、2016年に最優秀賞に選ばれている。 Cabal は Haskell 用のビルドおよびパッケージングシステムである。Cabal を利用して Haskell ライブラリのアーカイブである Hackage を参照して、新たなパッケージを簡単にインストールすることもできる。しばしばパッケージの依存地獄が発生しがちだが、それらを解決するため、Stackという環境も有志によって提供されている。 歴史1985年、遅延関数言語である Miranda がリサーチ・ソフトウェア社によって発表された。1987年にはこのような非正格な純粋関数型プログラミング言語が十二以上存在していたが、そのうち最も広く使われていた Miranda はパブリックドメインではなかった。オレゴン州ポートランドで開催された Functional Programming Languages and Computer Architecture (FPCA '87) において開かれた会議中に、遅延関数型言語のオープンな標準を作成するための委員会が発足されるべき、という強い合意が参加者のあいだで形成された。委員会の目的は、関数型言語のデザインにおける将来の研究のための基礎として役立つ共通のものへと、既存の関数型言語を統合することであった[3]。 Haskell 1.0最初の版の Haskell（Haskell 1.0）は1990年に作成された[4]。委員会の活動は一連の言語仕様を結果に残し、1997年後半にそのシリーズは、安定しており小さく可搬なバージョンの言語仕様と、学習用および将来の拡張の基礎としての基本ライブラリなどを定義したHaskell 98 に到達した。実験的な機能の付加や統合を通じて Haskell98 の拡張や派生物を作成することを、委員会ははっきりと歓迎した[3]。 Haskell 981999年2月、Haskell 98 言語標準は最初に The Haskell 98 Report として発表された[3]。2003年1月、改定されたバージョンが Haskell 98 Language and Libraries: The Revised Report として発表された[5]。GHC に代表されるように、Haskell は急速に発達しつづけている。 Haskell′2006年前半、非公式に Haskell′（Haskell Prime）と呼ばれている Haskell 98 standard の後継の作成プロセスが開始された[6]。このプロセスは Haskell 98 のマイナーバージョンアップを目的としている[7]。 Haskell 2010Haskell 2010 は他のプログラミング言語とのバインディングを可能にする Foreign Function Interface（FFI）を Haskell に追加し, いくつかの構文上の問題を修正する(正式な構文を変更する)。「 主な構文ここでは以降の解説を読む上で必要な Haskell の文法規則を簡単に説明する。Haskell の構文は数学で用いられるものによく似せられていることに注意されたい。 型Haskell の型名は先頭が大文字でなければならない。標準で存在する単純なデータ型としては、 pi :: Float
pi = 3.1415926535
e = 2.7182818284 :: Float -- 式の中でその型を指定している
関数の型は、各引数の間を gcd :: Int -> Int -> Int -- 関数名 :: 引数1の型 -> 引数2の型 -> 返り値の型
型変数を使い、型を抽象化することもできる。これは C++ のテンプレートや Java のジェネリクスに相当するが、様々な種(型の型)に適用できるためより柔軟である。例えば、 id :: a -> a
id x = x
また、データ型はパラメータとして型変数を持つことができる。例えば、スタックやハッシュテーブルなどのデータ型は、その要素の型を型変数として定義する。ハッシュテーブルを実装するデータ型 hashtable :: HashMap String Int
そのほか、特殊な表記を持つ型としてリストとタプル、文字列がある。リストは Haskell で極めて頻繁に用いられるため、特別な構文が用意されている。リストは要素の型を角括弧で囲む。次は text :: [Char]
text = "Hello" -- ['H','e','l','l','o'] の糖衣構文
hello :: [Char]
hello = 'H':'e':'l':'l':'o':[]
タプルは要素の型をカンマで区切り、括弧で囲む。次は point :: (Float,Float)
point = (3, 7)
タプルは2以上ならいくつでも要素を持つことができる。1要素のタプルは優先順位の括弧と表記が衝突し、また用途がないので存在しない。要素数がゼロのタプルは特に「ユニット」(
type String = [Char]
text :: String
Haskellの型は型構築子（型コンストラクタ、type constructor）から構築される[18]。型構築子
例えば型構築子 関数と演算子関数名は先頭が小文字でなければならず、記号を含むことはできない。演算子名は記号のみで構成されていなければならない。関数の定義ではC言語のような引数を囲む括弧や区切りのカンマは使われず、単に引数を空白文字で区切って表記する。次は先程示した恒等関数 id :: a -> a
id x = x -- 関数名 仮引数1 仮引数2 … = 関数本体の式
関数の適用も同様で、単に関数に続いて空白文字で区切った引数を並べればよい。以下では上記の恒等関数 hoge = id "piyo" -- hoge == "piyo" となる。
引数がつねに2個であることや引数の間に演算子をおくことなどを除けば、演算子についても関数の定義や適用と同様である。標準で定義されている算術演算子を使って、BMIを計算する関数 bmi :: Float -> Float -> Float
bmi weight height = weight / height ^ 2
この定義では bmi :: Floating a => a -> a -> a
bmi weight height = weight / height ^ 2
このバージョンの関数 関数と演算子は新たに定義し直さなくても相互に変換可能である。関数を演算子として使うには、関数を aspectRatio = width `div` height
なお、関数適用の優先順位はすべての演算子の優先順位よりも高い。 特徴的な機能ここではあまり他の言語では見られない Haskell 特有の機能を中心に解説する。ここでは説明していないが、現代的な実用言語では常識となっているガーベジコレクション、例外処理、モジュール、外部関数の呼び出し、正規表現ライブラリなどの機能は、Haskell にも当然存在している。 遅延評価Haskell は遅延評価を基本的な評価戦略とする。ほとんどの言語では関数の呼び出しにおいて引数に与えられたすべての式を評価してから呼び出された関数に渡す先行評価を評価戦略とするが、これに対し Haskell ではあらゆる式はそれが必要になるまで評価されない。次の定数 answer = const 42 (1 `div` 0)
ここで、 型推論Haskell では関数のデータ型を明示しなくても処理系が自動的に型を推論する。以下は型の宣言を省略し、本体のみを宣言した引数の平方を返す関数 square x = x * x
この場合 square :: (Num a) => a -> a
square x = x * x
この宣言は、「 square :: Integer -> Integer
square x = x * x
型推論のため、Haskell は型安全でありながらほとんどの部分で型宣言を省略できる[23]。なお、次のコードは型宣言が必要な例である。 main = print (read "42") -- コンパイルエラー！
このコードはコンパイルエラーになる。 read :: String -> Int
という型をもつ実装の main = print ((read "42") :: Int) -- コンパイル成功！read の返り値を Int と明示している
また、そもそも printIntOnly :: Int -> IO ()
printIntOnly x = print x
main = printIntOnly (read "42") -- コンパイル成功！
他の言語、たとえば Java でこのような抽象的な関数を書こうとしても、Java では返り値の値の型によって関数を選択するようなことはできない（引数の型によって選択するメソッドのオーバーロードは存在する）。そのため、関数の実装ごとに別の名前をつけてプログラマに明示的に選択させて解決させることになる[24]。この方法は簡潔でわかりやすいが、抽象性の高さに基づく再利用性という点では Haskell のような多相には劣ってしまう。 代数的データ型Haskell のデータ型には代数的データ型[25]と呼ばれる、C言語などでいう構造体や列挙体の性質を兼ね備えたものが用いられる。次の例は二つのInt型の値をフィールドに持つ二次元の座標、 data Point2D = Point2D Int Int
origin :: Point2D
origin = Point2D 0 0 -- データコンストラクタは関数のように適用できる
データコンストラクタは値を定義するための特殊な関数といえる。データコンストラクタは後述するパターンマッチによって値を取り出す際にも用いられる。 次の例はトランプの4つのスーツを示す data Suit = Spade | Heart | Club | Diamond
次の例は data Tree = Leaf String | Branch Tree Tree
organisms :: Tree
organisms = Branch animals plants -- Branch (Branch (Branch (Leaf "Lion") (Leaf "Tiger")) (Leaf "Wolf")) (Leaf "Cherry")
animals = Branch cats (Leaf "Wolf")
cats = Branch (Leaf "Lion") (Leaf "Tiger")
plants = Leaf "Cherry"
GADTと呼ばれる機能を使うと、コンストラクタの型を明示してデータ型を定義することもできる。 {-# LANGUAGE GADTs #-}
data Male
data Female
data Person s where
Adam :: Person Male
Eve :: Person Female
Child :: Person Male -> Person Female -> Int -> Person a
無名関数Haskell は第一級関数をサポートしており、高階関数を定義することができる。つまり、関数の引数として関数を与えたり、返り値として関数を返すことができる。無名関数は sortList xs = sortBy (\as bs -> compare (length as) (length bs)) xs
関数のカリー化と部分適用Haskell において、2つの引数を持つ関数は、1つの引数をとり「1つの引数をとる関数」を返す関数と同義である。このように、関数を返すことで全ての関数を1つの引数の関数として表現することをカリー化という。(あえてタプルを使うことで複数の引数を渡すような見かけにすることもできるが。)次の例は2つの引数をとり、そのうち値が大きい値を返す関数 max a b = if a > b then a else b
この関数maxは無名関数を用いて次のように書き換えることができる。先ほどの表現とまったく同様に動作するが、この表現では関数を返す様子がより明らかになっている。 max a = \b -> if a > b then a else b
さらに、次のようにも書き換えることができる。 max = \a -> \b -> if a > b then a else b
あるいは、 カリー化によって、Haskell のあらゆる関数は引数を部分適用することができる。つまり、関数の引数の一部だけを渡すことで、一部の変数だけが適用された別の関数を作り出すことができる。また、Haskell では演算子を部分適用することすら可能であり、演算子の部分適用をとくにセクション[27]と呼ぶ。 任意のリストをとり、その要素から条件にあう要素のみを取り出す関数 filter :: (a -> Bool) -> [a] -> [a]
この関数では第一引数に残す要素を判定する関数をとるが、このときに部分適用を使えばそのような関数を簡潔に書くことができる。整数のリストから正の値のみを取り出す関数 positives :: [Int] -> [Int]
positives = filter (> 0)
ps = positives [-4, 5, 0, 3, -1, 9] -- [5, 3, 9]
ここで、 パターンマッチHaskell では関数の引数を様々な形で受け取ることができる。 次は整数の要素をもつリストの全要素の合計を返す関数 total :: [Int] -> Int
total [] = 0
total (x:xs) = x + total xs
複数の返り値を扱うのもタプルなどを利用して極めて簡明に書くことができる。 (x, y) = (10, 20)
このとき、定義される変数は リストとリスト内包表記Haskell で順序付けられた複数の値を扱うのにもっとも柔軟で簡潔な方法はリストを用いることである。次は四季の名前のリストである。 ["Spring", "Summer", "Autumn", "Winter"]
次は初項10、公差4の等差数列のリストである。このリストは無限リストであり、その長さは無限大である。 [10, 14..]
次の式は先ほどの数列の先頭20項を要素に持つリストである。 take 20 [10, 14..]
もし正格な動作を持つ言語でこのような定義をしようとすると関数 primes :: [Int]
primes = [x | x <- [2..], and [rem x y /= 0 | y <- [2 .. x - 1]]]
リストはその柔軟性から再帰的な関数での値の受け渡しに向いているが、任意の位置の要素にアクセスするためには参照を先頭からたどる必要があるのでランダムアクセスが遅い、要素を変更するたびにリストの一部を作り直さなければならないなどの欠点がある。このため Haskell にも配列が用意されており、高速な参照や更新が必要なプログラムではリストの代わりに配列を用いることでパフォーマンスを改善できる可能性がある。 型クラスとインスタンス型クラス[28]は相異なるデータ型に共通したインターフェイスを持つ関数を定義する。例えば、順序づけることができる要素をもつリストをソートできる関数 まず型クラス class Comparer a where
order :: a -> a -> Int
型クラスを実装するには、対象のデータ型に対してインスタンス宣言を行う。次は型 instance (Eq a, Enum a) => Comparer [a] where
order [] [] = 0
order _ [] = 1
order [] _ = -1
order (x:xs) (y:ys) | x /= y = fromEnum x - fromEnum y
| otherwise = order xs ys
次にリストをクイックソートする関数 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]
この関数 main = do
print (sort ["foo", "bar", "baz"]) -- ["bar", "baz", "foo"] と出力される。
print (sort [[5, 9], [1, 2], [5, 6]]) -- [[1, 2], [5, 6], [5, 9]] と出力される。
Haskell のインスタンス宣言は複数の型に共通する操作を定義するという点で Java や C# の「インターフェイス」と似ているが、Haskell では既存の任意の型についてもインスタンスを定義できる点でもインターフェイスに比べて柔軟である。 入出力すべての式が参照透過である Haskell においては、副作用を式の評価そのものでは表現できない。そのため、Haskell では圏論のアイデアを利用したモナドによって入出力が表現されており、Haskell でも最も特徴的な部分となっている。次は Haskell による Hello world の一例である。実際に単独で実行可能形式にコンパイルできる、小さいが完全なプログラムの一例にもなっている。 main :: IO ()
main = putStrLn "Hello,World!"
Haskell は純粋関数型言語であり、 main = putStrLn getLine --コンパイルエラー！
getLine :: IO String
putStrLn :: String -> IO ()
純粋関数型である Haskell では main :: IO ()
main = getLine >>= putStrLn
ここでは演算子 モナドは、Freeモナド、Operationalモナドと呼ばれる構造により、より単純なデータ型から導出することもできる。これにより、非常に強力な依存性の注入が実現できる。 実例以下の単純な例は関数型言語としての構文の実例にしばしば用いられるもので、Haskell で示された階乗関数である。 fac :: Integer -> Integer
fac 0 = 1
fac n | n > 0 = n * fac (n-1)
階乗を単一の条件による終端を伴う再帰的関数として表現している。これは数学の教科書でみられる階乗の表現に似ている。Haskell コードの大半は、その簡潔さと構文において基本的な数学的記法と似通っている。 この階乗関数の1行目は関数の型を示すもので、省略可能である。これは「関数 2行目では Haskell の重要な機能であるパターンマッチングに頼っている。関数の引数が ガードは階乗が定義されない負の値から3行目を保護している。このガードが無ければこの関数は0の終端条件に達することなく、再帰してすべての負の値を経由してしまう。実際、このパターンマッチングは完全ではない。もし関数facに負の整数が引数として渡されると、このプログラムは実行時エラーとともに落ちるであろう。 より複合的な例引数 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
空リストを初期状態とし、 次はフィボナッチ数列のリストである。ある値nに対するfib(n)は一回しか計算しないようになっており、その点ではナイーブなフィボナッチと異なる効率の良いコードとなっている。 fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
無限リストは 余再帰[31]（リストの後ろの値は要求があったときに ただし、フィボナッチ数列の生成の場合は、ある要素の値が必要であれば、その要素より前にある要素の値は全て必要である。従って、遅延させた上で結局は後から全てその値を求めることになり、むしろ無駄であるので、この場合は遅延させない組込関数seqを使用したほうが効率は良くなり[32]、fib 1000000 といったような値を計算するような場合には差が見えてくる。あるいはリストの先に出る値から順番に計算させるとそのほうが速い、といったことが起きる。（さらに、フィボナッチ数はnに対して2nと大きな値になるので、そのようなBigIntegerの加算のコストも掛かり、以前にこの場所に書かれていたような「線形時間でのフィボナッチ数列の生成」は、大きい値では不可能である） どのように評価が進行するかの例示のために、次は6つの要素の計算の後の 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で使える言語拡張で、リスト内包表記を並列的な生成を記述できるよう拡張するParallelListCompを用いて書いた同様の式である。（GHCの拡張は特別なコマンドラインフラグ、またはLANGUAGEプラグマによって有効にしなければならない。詳しくはGHCのマニュアルを参照のこと） {-# LANGUAGE ParallelListComp #-}
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
上に示されたさまざまな ここでは、後続要素の構築関数は 各|は、等号の前半の条件部分と、後半の定義部分からなるガード節を構成する。 ライブラリparsecparsec は Haskell で書かれたパーサコンビネータである。パーサの一種であるがコンパイラコンパイラとは異なり、 派生として、大幅に高速なパースが可能なattoparsec[33]、高機能でより洗練されたtrifecta[34]がある。 Template HaskellTemplate Haskell は Haskell のメタプログラミングを可能にする拡張である。Haskell ソースコードの構文木を直接 Haskell から操作することができ、C、C++ のマクロやテンプレートを上回る極めて柔軟なプログラミングを行うことができる。 QuickCheck
lenslensはアクセサの概念を一般化するライブラリであり、様々なデータ構造に対して共通のインタフェースを与える。Getter、Setterは一つの関数として表現されており、それらを合成することもできる。JSONやXMLや、JSONやXML以外の処理にも応用できる。 批判Haskell は他のプログラミング言語には見られない多くの先進的機能を持っているが、これらの機能のいくつかは言語を複雑にしすぎており、理解が困難であると批判されてきた。とりわけ、関数型プログラミング言語と主流でないプログラミング言語に対する批判は Haskell にもあてはまる。加えて、Haskell の潔癖さとその理論中心の起源に起因する不満がある。 2002年に Jan-Willem Maessen、2003年にサイモン・ペイトン・ジョーンズが遅延評価に関連するこの問題を議論し、その上でこの理論的動機を認識した。彼らは実行時のオーバーヘッドの悪化に加え、遅延はコードのパフォーマンスの推察をより困難にすると言及した。 2003年に Bastiaan Heeren と Daan Leijen、Arjan van IJzendoorn は Haskell の学習者にとってのつまづきに気がついた。これを解決するために、彼らは Helium と呼ばれる新たなインタプリタを開発し、この中でいくつかの型クラスのサポートを取り除き、Haskell の機能の一般化を制限することによってエラーメッセージのユーザ親和性を改善した。 実装以下は Haskell 98 仕様を完全に満たす、または仕様に非常に近く、オープンソースライセンスの下で配布されているものである。ここには現在のところ商用のHaskell実装は含まれない。
代表的なアプリケーション
脚注
参考文献
学習用参考図書
関連項目
外部リンク
|
||||||||||||||||||||||||||||||||||||||||||
