Haskell
Haskellのロゴ | |
パラダイム |
関数型プログラミング、純粋関数型言語、非正格プログラミング言語 |
---|---|
登場時期 | |
開発者 |
ポール・ヒューダック、レナート・オーガストソン、John Hughes、サイモン・ペイトン・ジョーンズ、エリック・マイヤー、Philip Wadler |
最新リリース | Haskell 2010 / 2010年6月[1] |
型付け | 強い静的型付け |
主な処理系 | GHC、Hugs、NHC、JHC、Yhc |
影響を受けた言語 |
LISP、ML、Miranda、Orwell、Lazy ML、Clean |
影響を与えた言語 | Factor |
プラットフォーム |
Microsoft Windows、Unix系 |
ウェブサイト |
www |
拡張子 |
hs、lhs |
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 98
[編集]1999年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 2010
[編集]Haskell 2010 は他のプログラミング言語とのバインディングを可能にする Foreign Function Interface(FFI)を Haskell に追加し, いくつかの構文上の問題を修正する(正式な構文を変更する)。「n + k
パターン」と呼ばれる構文を削除し, fak (n+1) = (n+1) * fak n
というような形式の定義はもはや許されない。Haskell に Haskell 2010 のソースかどうかや, いくつかの必要な拡張の指定を可能にする言語プラグマ構文拡張[8]を導入する。Haskell 2010 に導入された拡張の名前は, DoAndIfThenElse
, HierarchicalModules
(階層化ライブラリ), EmptyDataDeclarations
, FixityResolution
, ForeignFunctionInterface
, LineCommentSyntax
, PatternGuards
, RelaxedDependencyAnalysis
, LanguagePragma
, NoNPlusKPatterns
である。
主な構文
[編集]ここでは以降の解説を読む上で必要な Haskell の文法規則を簡単に説明する。Haskell の構文は数学で用いられるものによく似せられていることに注意されたい。
型
[編集]Haskell の型名は先頭が大文字でなければならない。標準で存在する単純なデータ型としては、Bool
(真偽値)型、Int
(整数)型、Float
(単精度浮動小数点数)型、Char
(文字)型、String
(文字列)型などが予め定義されている。任意の式の型を定義するには、式と型の間に ::
記号をおく。また、変数などのシンボル[9]を定義する際に変数名を式に指定して書くことで、その変数の型を指定することができる。例えば、次は円周率およびネイピア数を定数として定義し、さらにその型も浮動小数点型として指定している。[10]
pi :: Float
pi = 3.1415926535
e = 2.7182818284 :: Float -- 式の中でその型を指定している
関数の型は、各引数の間を ->
記号で区切って表記する。関数は引数をひとつ適用するたびに、その型は ->
で区切られたうちの一番左が消えた型となると考えればよい。[11]例えば、ふたつの整数を引数にとりその最大公約数を返す関数 gcd
の型は次のように定義される。[12]
gcd :: Int -> Int -> Int -- 関数名 :: 引数1の型 -> 引数2の型 -> 返り値の型
型変数を使い、型を抽象化することもできる。これは C++ のテンプレートや Java のジェネリクスに相当するが、様々な種(型の型)に適用できるためより柔軟である。例えば、a
型の値をとり、それをそのまま返す恒等関数 id
を型の指定とともに定義すると以下のようになる。ここで任意の型を示す型名 a
が定義に使われているが、このように先頭が小文字で始まっている型名は具体的な型名ではなく型変数である。この関数はあらゆる型の値を引数にとることができる。
id :: a -> a
id x = x
また、データ型はパラメータとして型変数を持つことができる。例えば、スタックやハッシュテーブルなどのデータ型は、その要素の型を型変数として定義する。ハッシュテーブルを実装するデータ型 HashMap :: * -> * -> *
があり、キーに文字列(String
)、値に整数(Int
)を持つハッシュテーブル hashtable
の型は次のようになる。[13]
hashtable :: HashMap String Int
そのほか、特殊な表記を持つ型としてリストとタプル、文字列がある。リストは Haskell で極めて頻繁に用いられるため、特別な構文が用意されている。リストは要素の型を角括弧で囲む。次は Char
(文字)のリストを束縛する変数 text
の定義である。[14]文字のリストは文字列と等価である。2行目にあるように、文字列は殆どのプログラミング言語と同じように二重引用符で囲む。コメントにHaskellでのリストの表記を添えた。最後にデシュガー(糖衣構文を元の表記に戻すこと)したリストの表記法を示した。textもhelloも等価である。
text :: [Char]
text = "Hello" -- ['H','e','l','l','o'] の糖衣構文
hello :: [Char]
hello = 'H':'e':'l':'l':'o':[]
タプルは要素の型をカンマで区切り、括弧で囲む。次は Float
(浮動小数点数)の値をもつ2次元座標のタプルが束縛される変数 point
の定義である。
point :: (Float,Float)
point = (3, 7)
タプルは2以上ならいくつでも要素を持つことができる。1要素のタプルは優先順位の括弧と表記が衝突し、また用途がないので存在しない。要素数がゼロのタプルは特に「ユニット」(Unit
) と呼ばれ、有効な値を持たないなどの時に使われる。[15]
type
キーワードを用いて、型に別名をつけることができる。[16]次は [Char]
に String
という別名をつけている。[17]
type String = [Char]
text :: String
Haskellの型は型構築子(型コンストラクタ、type constructor)から構築される[18]。型構築子T
に型変数(Type variables)v1 v2 vN
を与え型式(type expression)T v1 v2 vN
として評価することで型が構築される。型構築子の例には以下が挙げられる。
カインド | 総称 | 例 | 出典 |
---|---|---|---|
* | nullary type constructors, type constants | Int , Bool
|
[19] |
* -> * | unary type constructors | Maybe , IO
|
[20] |
* -> * -> * | binary type constructors | Either
|
例えば型構築子Maybe
に型変数Int
を渡し、Maybe Int
とすることで型が構築される。
関数と演算子
[編集]関数名は先頭が小文字でなければならず、記号を含むことはできない。演算子名は記号のみで構成されていなければならない。関数の定義ではC言語のような引数を囲む括弧や区切りのカンマは使われず、単に引数を空白文字で区切って表記する。次は先程示した恒等関数 id
に、型の定義に加えて本体の定義もした例である。
id :: a -> a
id x = x -- 関数名 仮引数1 仮引数2 … = 関数本体の式
関数の適用も同様で、単に関数に続いて空白文字で区切った引数を並べればよい。以下では上記の恒等関数 id
を(ここでは使う必要はないが)適用して、別の変数を定義した例である。
hoge = id "piyo" -- hoge == "piyo" となる。
引数がつねに2個であることや引数の間に演算子をおくことなどを除けば、演算子についても関数の定義や適用と同様である。標準で定義されている算術演算子を使って、BMIを計算する関数 bmi
を定義してみる。
bmi :: Float -> Float -> Float
bmi weight height = weight / height ^ 2
この定義では Float
を引数にとり Float
で結果を返すが、この関数では Double
を引数に使うことはできない。どの浮動小数点数型でも扱えるような関数にするには、次のように型変数を使えばよい。
bmi :: Floating a => a -> a -> a
bmi weight height = weight / height ^ 2
このバージョンの関数 bmi
では引数や返り値の型が a
とされているが、これにさらに a
は Floating
であるとの制約をつけている。Floating
は Float
や Double
を抽象化する型クラスであり /
や ^
といった演算子を適用できるので、bmi
の定義においてこれらの演算子を使うことができている。また、整数などの値は引数に取れないし、返り値は引数に与えた型で戻ってくる。
関数と演算子は新たに定義し直さなくても相互に変換可能である。関数を演算子として使うには、関数を `
(バッククォート)で囲む。逆に、演算子を関数として使うには括弧で囲む。例えば、整数を除算する関数 div
はよく演算子として使われる[21]。
aspectRatio = width `div` height
なお、関数適用の優先順位はすべての演算子の優先順位よりも高い。
特徴的な機能
[編集]ここではあまり他の言語では見られない Haskell 特有の機能を中心に解説する。ここでは説明していないが、現代的な実用言語では常識となっているガーベジコレクション、例外処理、モジュール、外部関数の呼び出し、正規表現ライブラリなどの機能は、Haskell にも当然存在している。
遅延評価
[編集]Haskell は遅延評価を基本的な評価戦略とする。ほとんどの言語では関数の呼び出しにおいて引数に与えられたすべての式を評価してから呼び出された関数に渡す先行評価を評価戦略とするが、これに対し Haskell ではあらゆる式はそれが必要になるまで評価されない。次の定数 answer
は評価すると常に 42
を返すが、その定義には未定義の式を含む。
answer = const 42 (1 `div` 0)
ここで、const
は常に第1引数を返す定数関数である。また、`div`
は整数の除算を行う演算子であり、1 `div` 0
は 1 / 0
に相当し、この値は未定義であり、この部分を評価すればエラーになる。正格評価をする言語でこのような式を評価しようとすると、ゼロ除算によるエラーになるであろう。しかし 上記の定数 answer
を評価してもエラーにはならない。const
は第1引数をつねに返すので第2引数を評価する必要はなく、第2引数に与えられた式 1 `div` 0
は無視されるので評価されないからである。遅延評価がデフォルトで行われることにより、不要な計算は省かれ、参照透過性により同じ式を複数回評価する必要もなくなるため、Haskell では最適化によって計算効率の向上が期待できる場合がある。ただし、頻繁に新たな値を計算する場合は正格評価のほうが効率がよく、必要に応じてseq
関数やBangPatterns拡張による明示により正格評価もできる。
型推論
[編集]Haskell では関数のデータ型を明示しなくても処理系が自動的に型を推論する。以下は型の宣言を省略し、本体のみを宣言した引数の平方を返す関数 square
である。
square x = x * x
この場合 square
の型は型推論され、次のように明示的に型を宣言したのと同じになる。
square :: (Num a) => a -> a
square x = x * x
この宣言は、「Num
のインスタンス[22]である a
の型の値を引数にとり、a
の型の値を返す」と読める。ここでは「*
」演算子が適用可能な最も広い型である Num a
が選択されており、整数や浮動小数点数、有理数のような Num
のインスタンスであるあらゆる型の値を渡すことができる。外部に公開するような関数を定義するときは、型推論によって自動的に選択される最も広い型では適用可能な範囲が広すぎる場合もある。Integer
のみを渡せるように制限する場合は、次のように明示的に型を宣言すればよい。
square :: Integer -> Integer
square x = x * x
型推論のため、Haskell は型安全でありながらほとんどの部分で型宣言を省略できる[23]。なお、次のコードは型宣言が必要な例である。read
は文字列をその文字列があらわすデータ型に変換する抽象化された関数である。
main = print (read "42") -- コンパイルエラー!
このコードはコンパイルエラーになる。read
は複数のインスタンスで実装されており、数値なら数値型に変換する read
、リストならリストに変換する read
というように型ごとに実装が存在する。Haskell の型は総て静的に決定されなければならない。このコード場合、プログラマは
read :: String -> Int
という型をもつ実装の read
が選択されると期待しているであろうが、これはコンパイラによる静的な型検査では決定できない。つまり、Haskell コンパイラは read
の返り値を受け取っている関数 print
の型を検査し多数の実装の中から適切な read
を選択しようとするが、print
は Show
のインスタンスが存在するあらゆる型を引数にとるため、型推論によっても read
の型を一意に決定できない。これを解消するひとつの方法は、::
によって型を明示することである。
main = print ((read "42") :: Int) -- コンパイル成功!read の返り値を Int と明示している
また、そもそも read
の返り値を整数型しか取らない関数に与えていればあいまいさは生じず、型推論は成功する。
printIntOnly :: Int -> IO ()
printIntOnly x = print x
main = printIntOnly (read "42") -- コンパイル成功!
他の言語、たとえば Java でこのような抽象的な関数を書こうとしても、Java では返り値の値の型によって関数を選択するようなことはできない(引数の型によって選択するメソッドのオーバーロードは存在する)。そのため、関数の実装ごとに別の名前をつけてプログラマに明示的に選択させて解決させることになる[24]。この方法は簡潔でわかりやすいが、抽象性の高さに基づく再利用性という点では Haskell のような多相には劣ってしまう。
代数的データ型
[編集]Haskell のデータ型には代数的データ型[25]と呼ばれる、C言語などでいう構造体や列挙体の性質を兼ね備えたものが用いられる。次の例は二つのInt型の値をフィールドに持つ二次元の座標、Point2D
型を定義したもので、これは代数的データ型の構造体的な性質を示す。先頭のトークン「data
」は代数的データ型の宣言であることを示す予約語である。ここで最初の Point2D
はデータ型名を表し、次の Point2D
はデータコンストラクタ名を示す[26]。
data Point2D = Point2D Int Int
origin :: Point2D
origin = Point2D 0 0 -- データコンストラクタは関数のように適用できる
データコンストラクタは値を定義するための特殊な関数といえる。データコンストラクタは後述するパターンマッチによって値を取り出す際にも用いられる。
次の例はトランプの4つのスーツを示す Suit
型を定義したものである。Spade
、Heart
、Club
、Diamond
の4つのデータコンストラクタが定義されており、Suit
型の式は Spade
、Heart
、Club
、Diamond
のいずれかの値をとる。
data Suit = Spade | Heart | Club | Diamond
次の例は String
型の値を格納する二分木の型である。Leaf
(葉)は String
型の値を持ち、Branch
(枝)は Leaf
もしくは Branch
である Tree
型の変数を二つ持つ。これは代数的データ型の構造体的な性質と列挙体的な性質の両方が現れている。
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 は第一級関数をサポートしており、高階関数を定義することができる。つまり、関数の引数として関数を与えたり、返り値として関数を返すことができる。無名関数は \
(バックスラッシュ)から始まり、それに続いて引数となる変数、引数と本体のあいだに ->
記号をおく。List
モジュールに定義されているリストのソートを行う関数 sortBy
は、二つの要素に大小関係を与える関数を引数にとるが、無名関数を使うと例えばリストをその長さの短い順にソートする関数 sortList
は次のように定義できる。
sortList xs = sortBy (\as bs -> compare (length as) (length bs)) xs
関数のカリー化と部分適用
[編集]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
さらに、次のようにも書き換えることができる。
max = \a -> \b -> if a > b then a else b
あるいは、f x = ... x ...
は、 f = (\x -> ... x ...)
の糖衣構文であるとも言える。このため、Haskell の定義は変数に束縛するのが定数であるか関数であるかにかかわらず、「変数 = 値」という一貫した形でも定義できる。
カリー化によって、Haskell のあらゆる関数は引数を部分適用することができる。つまり、関数の引数の一部だけを渡すことで、一部の変数だけが適用された別の関数を作り出すことができる。また、Haskell では演算子を部分適用することすら可能であり、演算子の部分適用をとくにセクション[27]と呼ぶ。
任意のリストをとり、その要素から条件にあう要素のみを取り出す関数 filter
が標準ライブラリに定義されている。
filter :: (a -> Bool) -> [a] -> [a]
この関数では第一引数に残す要素を判定する関数をとるが、このときに部分適用を使えばそのような関数を簡潔に書くことができる。整数のリストから正の値のみを取り出す関数 positives
は次のように定義できる。
positives :: [Int] -> [Int]
positives = filter (> 0)
ps = positives [-4, 5, 0, 3, -1, 9] -- [5, 3, 9]
ここで、positives
および filter
の第2引数はソースコード上に現れずに記述できているが、このように単純に書けるのもカリー化の恩恵によるものである。
パターンマッチ
[編集]Haskell では関数の引数を様々な形で受け取ることができる。
次は整数の要素をもつリストの全要素の合計を返す関数 total
である。
total :: [Int] -> Int
total [] = 0
total (x:xs) = x + total xs
total
の関数本体の定義がふたつあるが、このうち引数の実行時の値と適合する本体が選択され呼び出される。上の本体定義では、引数が空のリストであるときのみ適合し、呼び出される。下の本体定義では、引数が少なくともひとつの要素を持つとき適合し、x
に先頭の要素が束縛され、xs
に残りのリストが束縛される。この例の場合はパターンに漏れはないが、もし適合するパターンが見つからない場合はエラーになる。
複数の返り値を扱うのもタプルなどを利用して極めて簡明に書くことができる。
(x, y) = (10, 20)
このとき、定義される変数は x
および y
で、それぞれ x
は 10
に、y
は 20
に定義される。
リストとリスト内包表記
[編集]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 にも配列が用意されており、高速な参照や更新が必要なプログラムではリストの代わりに配列を用いることでパフォーマンスを改善できる可能性がある。
型クラスとインスタンス
[編集]型クラス[28]は相異なるデータ型に共通したインターフェイスを持つ関数を定義する。例えば、順序づけることができる要素をもつリストをソートできる関数 sort
を定義することを考える。リストの要素のデータ型は関数 sort
を定義するときには不明であり、その要素をどのように順序付けるかを予め決定しておくことはできない。数値型も文字列型もそれぞれのデータを順序付けることができるであろうが、共通してデータの順序を返す抽象的な関数 order
を定義することができれば、それを用いてソートすることができる。
まず型クラス Comparer
を定義して、順序付ける関数 order
の形式を定義する。値の順序を調べる関数 order x y
は x
→ y
が昇順のときは負の値、降順の時は正の値、x
と y
が等しいときは 0
を返すものとする。ここで class
は型クラスの宣言であることを示す予約語である。
class Comparer a where
order :: a -> a -> Int
型クラスを実装するには、対象のデータ型に対してインスタンス宣言を行う。次は型 a
の型クラス Comparer
に対するインスタンスを宣言したものである。このインスタンス宣言により、Enum
のインスタンスである任意の型のリストを辞書順に比較できる。例えば、文字列 Char
は Enum
のインスタンスの Char
のリストであり、このインスタンス定義により order
を適用することができるようになる。ここで関数 fromEnum c
は文字 c
を数値に変換する関数である。Comparer
のインスタンスを定義する型 a
を Eq
および Enum
のインスタンスを持つものに限定しているので((Eq a, Enum a) =>
の部分)、インスタンス定義の内部で Eq
の関数である (/=)
や Enum
の関数である fromEnum
を使うことができている。
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
を示す。型クラスを用いて順序付ける関数 order
を抽象化したため、このように型クラス 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]
この関数 sort
は次のように使う。
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
もやはり参照透過である(副作用はない)。しかし処理系は main
として定義された IO ()
型の値をそのプログラムの動作を示す値として特別に扱う。putStrLn
は標準出力に文字列を出力する動作を表す IO ()
型の値を返す関数であり、実行すると引数として渡された Hello,World!
を出力する。次に標準入力から一行読み込み、そのまま標準出力に出力するエコープログラムを考える。次のような、C言語などのような表記はできない。getLine
関数は標準入力から一行読み取る関数である。
main = putStrLn getLine --コンパイルエラー!
getLine
と putStrLn
はそれぞれ次のような型を持っている。
getLine :: IO String
putStrLn :: String -> IO ()
純粋関数型である Haskell では getLine
もやはり副作用はなく、getLine
は一行読み込むという動作を表す値を常に返す。このように入出力の動作を表す値をアクション[29]と呼ぶ。getLine
が返すのは String
そのものではなくあくまで IO String
という型を持ったアクションであって、それを putStrLn
の引数に与えることはできない。正しいエコープログラムの一例は次のようになる。
main :: IO ()
main = getLine >>= putStrLn
ここでは演算子 >>=
によってふたつのアクションを連結している。このとき、main
は一行読み込みそれを出力するというアクションとなり、このプログラムを実行すると処理系は main
が持つアクションの内容を実行する。このアクションを実行すると、getLine
は一行読み込み、それを putStrLn
に渡す。このとき、読み込まれたデータにこれらのアクションの外側からアクセスすることはできない。このため、この式は参照透過性を保つことができる。[30]
モナドは、Freeモナド、Operationalモナドと呼ばれる構造により、より単純なデータ型から導出することもできる。これにより、非常に強力な依存性の注入が実現できる。
実例
[編集]以下の単純な例は関数型言語としての構文の実例にしばしば用いられるもので、Haskell で示された階乗関数である。
fac :: Integer -> Integer
fac 0 = 1
fac n | n > 0 = n * fac (n-1)
階乗を単一の条件による終端を伴う再帰的関数として表現している。これは数学の教科書でみられる階乗の表現に似ている。Haskell コードの大半は、その簡潔さと構文において基本的な数学的記法と似通っている。
この階乗関数の1行目は関数の型を示すもので、省略可能である。これは「関数 fac
は Integer
から Integer
へ(Integer -> Integer
)の型を持つ(::
)」と読める。これは整数を引数としてとり、別の整数を返す。もしプログラマが型注釈を与えない場合、この定義の型は自動的に推測される。
2行目では Haskell の重要な機能であるパターンマッチングに頼っている。関数の引数が 0
であれば、これは 1
を返す。その他の場合は3行目が試される。これは再帰的な呼び出しで、nが0に達するまで繰り返し関数が実行される。
ガードは階乗が定義されない負の値から3行目を保護している。このガードが無ければこの関数は0の終端条件に達することなく、再帰してすべての負の値を経由してしまう。実際、このパターンマッチングは完全ではない。もし関数facに負の整数が引数として渡されると、このプログラムは実行時エラーとともに落ちるであろう。fac _ = error "negative value"
のように定義を追加すれば適切なエラーメッセージを出力することができる。
より複合的な例
[編集]引数 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
は、注目している語が演算子ならばその演算を実行し、それ以外ならば浮動小数点として計算スタックに積んでいる。
次はフィボナッチ数列のリストである。ある値nに対するfib(n)は一回しか計算しないようになっており、その点ではナイーブなフィボナッチと異なる効率の良いコードとなっている。
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
無限リストは 余再帰[31](リストの後ろの値は要求があったときに 0
と 1
の二つの初期要素から開始され算出される)によって実現される。このような定義は遅延評価の実例で、Haskell プログラミングでも重要な部分である。
ただし、フィボナッチ数列の生成の場合は、ある要素の値が必要であれば、その要素より前にある要素の値は全て必要である。従って、遅延させた上で結局は後から全てその値を求めることになり、むしろ無駄であるので、この場合は遅延させない組込関数seqを使用したほうが効率は良くなり[32]、fib 1000000 といったような値を計算するような場合には差が見えてくる。あるいはリストの先に出る値から順番に計算させるとそのほうが速い、といったことが起きる。(さらに、フィボナッチ数はnに対して2nと大きな値になるので、そのようなBigIntegerの加算のコストも掛かり、以前にこの場所に書かれていたような「線形時間でのフィボナッチ数列の生成」は、大きい値では不可能である)
どのように評価が進行するかの例示のために、次は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で使える言語拡張で、リスト内包表記を並列的な生成を記述できるよう拡張する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
上に示されたさまざまな fibs
の定義のように、これはオンデマンドに数のリストを実現するために無限リストを使っており、1
という先頭要素から後続の要素を生成している。
ここでは、後続要素の構築関数は where
節内の記号 #
で表現された中置演算子で定義されている。
各|は、等号の前半の条件部分と、後半の定義部分からなるガード節を構成する。
ライブラリ
[編集]parsec
[編集]parsec は Haskell で書かれたパーサコンビネータである。パーサの一種であるがコンパイラコンパイラとは異なり、Parsec
はパーサのソースコードを出力するのではなく、純粋に Haskell の関数としてパーサを構成する。yacc のようにプログラミング言語と異なる言語を新たに習得する必要がなく、高速でかつ堅牢で、型安全で、演算子の結合性や優先順位を考慮したパーサを自動的に構成したり、動的にパーサを変更することすらできる。
派生として、大幅に高速なパースが可能なattoparsec[33]、高機能でより洗練されたtrifecta[34]がある。
Template Haskell
[編集]Template Haskell は Haskell のメタプログラミングを可能にする拡張である。Haskell ソースコードの構文木を直接 Haskell から操作することができ、C、C++ のマクロやテンプレートを上回る極めて柔軟なプログラミングを行うことができる。
QuickCheck
[編集]QuickCheck
はデータ駆動型のテストを行うモジュールである。自動的にテストデータを作成してプログラムの正当性をテストすることができる。
lens
[編集]lensはアクセサの概念を一般化するライブラリであり、様々なデータ構造に対して共通のインタフェースを与える。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実装は含まれない。
- Glasgow Haskell Compiler
- The Glasgow Haskell Compiler は異なる複数のアーキテクチャのネイティブコードにコンパイルできるほか、C言語にコンパイルすることもできる。おそらくGHCは最も知られた Haskell コンパイラで、現在のところGHCのみで動く言語拡張が実装されており、かなり便利ないくつかのライブラリはGHCのみで動作する(たとえは OpenGL のバインディングなど)。[35]
- Gofer
- 初期(Haskell 1.2)の仕様をベースとした、等式推論に向いた[36]方言およびインタプリタの実装。当時の Haskell より Miranda に似た構文、標準の機能をいくつか満たさない、逆に標準にないいくつかの機能の追加、などの特徴があった。マーク・ジョーンズにより開発された。その役割の多くは Hugs に譲られた。Hugs の「g」は Gofer に由来する。
- HBC
- これは別のネイティブコード Haskell コンパイラ。これはしばらくの間開発が活発ではなくなっているが、未だに利用可能である。[要出典][37]
- Helium
- これは新しい Haskell の方言である。開発の際の焦点は、明瞭なエラーメッセージを提供し学習を容易にすることである。Heliumは型クラスをサポートせず、多くのHaskellプログラムとは互換性のない実装である。[38]
- Hugs
- これはバイトコードインタプリタである。これは速いプログラム編集とそれなりの実行スピードを提供する。これは単純なグラフィックスライブラリを含む。多くの人が Haskell の基本を学ぶのによいが、これはオモチャ的な実装であるということではない。これは最も可搬で軽量な Haskell 実装である。[39]
- jhc
- これは新しいプログラム変換の研究用としてのみならず、スピードと生成されるプログラムの効率を重視した John Meacham によって書かれた Haskell コンパイラである。[40]
- nhc98
- これは別のバイトコードコンパイラであるが、そのバイトコードは Hugs より顕著に速く走る。Nhc98は省メモリ使用に焦点を絞っており、古いマシンや遅いマシンにはとりわけよい選択肢となる。[41]
- yhc
- これはnhc98の派生物で、単純かつ可搬で効率的、integrating Hat のサポートを目標とする。[42]
代表的なアプリケーション
[編集]- Darcs - 分散バージョン管理システム。
- Monadius - グラディウス・クローンのシューティングゲーム。
- Pandoc - Markdownなどを変換するドキュメント・コンバータ。
- xmonad - X Window Systemのウィンドウマネージャ。
- Yesod - Webアプリケーションフレームワーク。
脚注
[編集]- ^ 出典URL: https://mail.haskell.org/pipermail/haskell/2009-November/021750.html, 閲覧日: 2023年1月11日, 題名: [Haskell] Announcing Haskell 2010, 出版日: 2009年11月24日
- ^ かつては Goffin と呼ばれていた。
- ^ a b c “Preface”. Haskell 98 Language and Libraries: The Revised Report (2002年12月). 2009年6月23日閲覧。
- ^ “The History of Haskell”. 2009年6月23日閲覧。
- ^ Simon Peyton Jones (編) (2002年12月). “Haskell 98 Language and Libraries: The Revised Report”. 2009年6月23日閲覧。
- ^ “Future development of Haskell”. 2009年6月23日閲覧。
- ^ “Welcome to Haskell'”. The Haskell' Wiki. 2009年6月23日閲覧。
- ^ 英: language-pragma-syntax-extension
- ^ 「変数」は実際にはその値を動的に変更することはできないなど、C言語など手続き型言語の変数とは明らかに異なるものである。
- ^ ここでは説明のため単に Float としているが、標準ライブラリで定義されている円周率
pi
は浮動小数点数型の抽象的な型クラスであるFloating a
で定義されており、Float
のみならず 倍精度浮動小数点数型Double
の値としても取得できる。 - ^ Haskell はカリー化によりすべての関数を 1 引数の関数として表現できるが、これにしたがって
->
は右結合であるとして読むこともできる。上記の関数の型の定義は、括弧を明示した次の定義と同等である。gcd :: Int -> (Int -> Int)
関数を引数にとる関数は、引数の型を括弧で囲んで -> 記号の優先順位を指定すればよい。次は関数を二つとり、その合成関数を返す演算子 . の定義である。
(.) :: (b -> c) -> (a -> b) -> a -> c
- ^ 式の外で演算子の型を指定するときは、演算子を括弧で囲めばよい。以下の関数と演算子の相互変換を参照のこと。
- ^
これは、C++ や Java のような言語では次のようなコードに相当する。
Hashtable<String,Int> hashtable;
- ^ 当然ながら、リストの要素としてリストを持つこともできる。例えば、文字リスト(文字列)のリストの型は
[[Char]]
となるであろう。 - ^ ユニットはC言語や Java などでいう
void
のような使われ方をする。 - ^ 言い換えれば、単純な型名に見えても何か複雑な別の型の別名である可能性がある。
- ^ 実際に標準ライブラリでは
String
は[Char]
の別名であり、String
にはあらゆるリストの操作が可能である。 - ^ type values are built from type constructors. haskell2010
- ^ Char, Int, Integer, Float, Double and Bool are type constants with kind ∗. haskell2010
- ^ Maybe and IO are unary type constructors, and treated as types with kind ∗→∗. haskell2010
- ^ 除算する演算子
/
は存在するが、これはFloat
などを除算する演算子であり整数ではない。他の言語のように自動的に値を変換する(int → float など)ような動作は Haskell では意図的に排除されている。 - ^ Haskell の型システムにおける汎用型が実体化されたもの。オブジェクト指向におけるインスタンスとは異なる。
- ^ ただし、型を明示することは可読性を向上したり問題の発見に役立つため、常に省略するのがよいとは限らない。
- ^
java.lang.Integer.parseInt
、java.lang.Double.parseDouble
など - ^ 英: algebraic data type
- ^ データ型名とデータコンストラクタ名は同じでも構わない。このような単純な代数的データ型であれば型名とデータコンストラクタ名を同じにすることも多い。
- ^ 英: section
- ^ 英: type class
- ^ 英: action
- ^ GHC には
System.IO.Unsafe
モジュールにunsafePerformIO
という関数があり、副作用を持ちながらアクションでない型を返すことができる。これは参照透過性に対するバックドアであり、Haskell の参照透過性を破壊する恐れがあるので、注意深く使わなければならない。 - ^ 英: corecursion
- ^ Haskellの神話 - あどけない話
- ^ attoparsec: Fast combinator parsing for bytestrings and text
- ^ trifecta: A modern parser combinator library with convenient diagnostics
- ^ Home — The Glasgow Haskell Compiler
- ^ 英: good for equational reasoning
- ^ http://www.cs.chalmers.se/~augustss/hbc/hbc.html (リンク切れ)
- ^ http://foswiki.cs.uu.nl/foswiki/Helium
- ^ Hugs 98
- ^ jhc
- ^ nhc98
- ^ Yhc - HaskellWiki
参考文献
[編集]- Simon Peyton Jones. Wearing the hair shirt: a retrospective on Haskell 2003年のen:POPLでの招待演説。
- Jan-Willem Maessen. Eager Haskell: Resource-bounded execution yields efficient iteration. 2002年のACM SIGPLAN workshopでのHaskellの記録。
- Bastiaan Heeren, Daan Leijen, Arjan van IJzendoorn. Helium, for learning Haskell. 2003年の ACM SIGPLAN workshop でのHaskellの記録。
学習用参考図書
[編集]- 向井淳:「入門Haskell―はじめて学ぶ関数型言語」、毎日コミュニケーションズ、 ISBN 978-4839919627(2006年3月1日)。
- 青木 峰郎, 山下 伸夫 (監修):「ふつうのHaskellプログラミング ふつうのプログラマのための関数型言語入門」、 ソフトバンククリエイティブ、ISBN 978-4797336023(2006年6月1日)。
- Bryan O'Sullivan, John Goerzen, Don Stewart:「Real World Haskell―実戦で学ぶ関数型言語プログラミング」、オライリージャパン、ISBN 978-4873114231 (2009年10月26日)。
- Grahum Hutton、山本和彦 (訳):「プログラミングHaskell」、オーム社、ISBN 978-4274067815(2009年11月11日)※第2版が2019年に出版。
- Miran Lipovača、田中英行 (訳), 村主崇行 (訳):「すごいHaskellたのしく学ぼう!」、オーム社、ISBN 978-4274068850(2012年5月23日)。
- Richard Bird、山下伸夫(訳):「関数プログラミング入門 ―Haskellで学ぶ原理と技法―」、オーム社、ISBN 978-4274068966 (2012年10月26日)。
- Richard Bird、山下伸夫 (訳):「Haskellによる関数プログラミングの思考法」、KADOKAWA、 ISBN 978-4048930536(2017年2月27日)。
- 重城良国:「Haskell 教養としての関数型プログラミング」、秀和システム、ISBN 978-4798048062(2017年4月15日)。
- Will Kurt、株式会社クイープ (監訳):「入門Haskellプログラミング」、翔泳社、ISBN 978-4798158662(2019年7月31日)。
- Grahum Hutton、山本和彦 (訳):「プログラミングHaskell 第2版」、ラムダノート、ISBN 978-4908686078(2019年8月2日)。
- 本間雅洋、類地孝介、逢坂時響:「Haskell入門 関数型プログラミング言語の基礎と実践」、技術評論社、ISBN 978-4774192376(2017年9月27日)。
関連項目
[編集]- Atom - Haskell言語ベースのハードウェア記述言語
- Bluespec - Haskell言語ベースのハードウェア記述言語
- Hydra - Haskell言語ベースのハードウェア記述言語
- Idris - Haskellに似た構文を持つ、依存型を持つ、正格な純粋関数型言語
- Elm - JavaScriptのコードを生成するリアクティブなプログラミング言語
- Fay - JavaScriptのコードを生成するHaskellのサブセット
- オフサイドルール
外部リンク
[編集]- 公式ウェブサイト
- Old HaWiki - Haskellのいくつかの古い話題の議論
- Haskell Humor
- Haskell Tutorial for C Programmers by Eric Etheridge
- A Gentle Introduction to Haskell 98 - ([1])
- Haskell vs. Ada vs. C++ vs. Awk vs. ... An Experiment in Software Prototyping Productivity - (PDFファイル)
- Yet Another Haskell Tutorial - Hal Daume IIIによるよいHaskellチュートリアル。公式チュートリアルに先立つより厳選された知識。
- The Evolution of a Haskell Programmer - Haskellで使える異なるプログラミングスタイルのちょっとユーモラスな概説。
- An Online Bibliography of Haskell Research