Loading article…
この記事では、プログラミング言語Haskellの機能について説明します。
関数型言語の構文を説明する際によく用いられる簡単な例として、非負整数の階乗関数をHaskellで示します。
factorial :: Integer -> Integer factorial 0 = 1 factorial n = n * factorial ( n - 1 )または一行で表すと：
nの階乗= n > 1の場合、n * n - 1 の階乗、それ以外の場合は1これは階乗を再帰関数として記述し、終了する基本ケースを1つ持つことを示しています。これは数学の教科書に見られる階乗の説明と似ています。Haskellのコードの多くは、使いやすさと構文において標準的な数学記号と類似しています。
階乗関数の最初の行は、この関数の型を記述しています。これは省略可能ですが、含めるのが良いスタイルとされています[ 1 ] 。これは、 「関数 factorial ( factorial)は整数から整数( ) への型( )を持つ」と読むことができます。つまり、整数を引数として受け取り、別の整数を返します。型注釈が指定されていない場合、定義の型は自動的に推論されます。::Integer -> Integer
2行目は、Haskellの重要な機能であるパターンマッチングを利用しています。関数の引数は括弧ではなくスペースで区切られていることに注意してください。関数の引数が0（ゼロ）の場合、整数1（イチ）が返されます。それ以外の場合は、3行目が実行されます。これは再帰であり、基本ケースに到達するまで関数を繰り返し実行します。
Preludeの関数、 C言語の標準ライブラリproductに類似した多数の小さな関数、および算術数列のためのHaskell構文を使用すると、階乗関数はHaskellで次のように表現できます。
nの階乗=積[ 1 .. n ]ここで は、[1..n]等差数列1, 2, …, n をリスト形式で表したものです。Prelude 関数 を使用するとenumFromTo、式[1..n]は と書くことができenumFromTo 1 n、階乗関数は次のように表すことができます。
階乗n =積( enumFromTo 1 n )これは、関数合成演算子（Haskellではドットで表現される）を使用して、積関数とカリー化された列挙関数を合成することで、ポイントフリーのスタイルで書き直すことができます。[ 2 ]
階乗= product.enumFromTo 1Hugsインタープリタでは、関数を定義して同じ行で使用する場合、多くの場合、awhereまたはlet..で区切る必要がありますin。たとえば、上記の例をテストして出力を確認するには、次のようにします120。
let { factorial n | n > 0 = n * factorial ( n - 1 ); factorial _ = 1 } in factorial 5または
階乗5 （階乗= product . enumFromTo 1 の場合）GHCiインタープリタにはこの制限がなく、関数定義を1行で入力でき（let構文は一部省略in）、後で参照できます。
すぐ下の Haskell ソースでは、::は「型を持つ」と読むことができ、a -> bは「a から b への関数である」と読むことができます。（したがって、Haskell は「文字列から浮動小数点数のリストへの関数の型を持つ」と読むことができます。）2 行目の等号は「である可能性がある」と読むことができ、したがって、 を含む複数の行は、各行で詳述されている状況に応じて、の複数の可能な値として読むことができます。calc :: String -> [Float]calccalc = ...calc = ...calc
パターンマッチングと型クラスReadを使用したwhere句で引数fが定義されている高階関数で表現されたシンプルな逆ポーランド記法計算機:foldl
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 ( x : y : zs ) "FLIP" = y : x : zs f zs w = read w : zs空のリストは初期状態であり、f は 一度に 1 つの単語を解釈します。解釈されるのは、関数名として解釈し、リストの先頭から 2 つの数値を取得して結果をリストに戻す場合と、単語を浮動小数点数として解析し、リストの先頭に追加する場合があります。
以下の定義は、フィボナッチ数列を線形時間で生成します。
fibs = 0 : 1 : zipWith ( + ) fibs ( tail fibs )無限リストは共再帰によって生成されます。リストの後半の値は、最初の2つの項目0と1から始めて、必要に応じて計算されます。このような定義は、Haskellプログラミングの重要な機能である遅延評価に依存しています。評価がどのように進化するかの例として、次の例では、6つの項目を計算した後のfibsとtail fibsの値を示し、 zipWith(+)が4つの項目を生成し、次の項目を生成する様子を示します。
fibs = 0 : 1 : 1 : 2 : 3 : 5 : ... + + + + + + 尾部線維 = 1 : 1 : 2 : 3 : 5 : ... = = = = = = zipWith ... = 1 : 2 : 3 : 5 : 8 : ... fibs = 0 : 1 : 1 : 2 : 3 : 5 : 8 : ...
同じ関数を、グラスゴーハスケルコンパイラの並列リスト内包表記構文を使用して記述します（GHC拡張機能は、特別なコマンドラインフラグ（ここでは-XParallelListComp ）を使用するか、ソースファイルを次のように開始することで有効にする必要があります）。{-# LANGUAGE ParallelListComp #-}
fibs = 0 : 1 : [ a + b | a <- fibs | b <- tail fibs ]または通常のリスト内包表記を使用する場合：
fibs = 0 : 1 : [ a + b | ( a , b ) <- zip fibs ( tail fibs ) ]または直接自己参照：
fibs = 0 : 1 : next fibs where next ( a : t @ ( b : _ )) = ( a + b ) : next tfibs = next ( 0 , 1 ) where next ( a , b ) = a : next ( b , a + b )または以下でunfoldr：
fibs = unfoldr ( \ ( a , b ) -> Just ( a , ( b , a + b ))) ( 0 , 1 )またはscanl：
fibs = 0 : scanl ( + ) 1 fibsHaskellの事前定義された不動点コンビネータを使用したデータ再帰の使用：
fibs = fix ( \ xs -> 0 : 1 : zipWith ( + ) xs ( tail xs )) -- zipWith バージョン= fix (( 0 : ) . ( 1 : ) . ( zipWith ( + ) <*> tail )) -- 上記と同じ、 pointfree = fix (( 0 : ) . scanl ( + ) 1 ) -- scanl バージョン先に見た階乗は、一連の関数として表すことができます。
factorial n = foldr (( . ) . ( * )) id [ 1 .. n ] $ 1 -- factorial 5 == ((1*) .) ( ((2*) .) ( ((3*) .) ( ((4*) .) ( ((5*) .) id )))) 1 -- == (1*) . (2*) . (3*) . (4*) . (5*) . id $ 1 -- == 1* ( 2* ( 3* ( 4* ( 5* ( id 1 )))))factorial n = foldr (( . ) . ( * )) ( const 1 ) [ 1 .. n ] $ () -- factorial 5 == ((1*) .) ( ((2*) .) ( ((3*) .) ( ((4*) .) ( ((5*) .) (const 1) )))) () -- == (1*) . (2*) . (3*) . (4*) . (5*) . const 1 $ () -- == 1* ( 2* ( 3* ( 4* ( 5* ( const 1 () )))))階乗n = foldr (( $ ) . ( * )) 1 [ 1 .. n ] = foldr ( $ ) 1 $ map ( * ) [ 1 .. n ] -- 階乗 5 == ((1*) $) ( ((2*) $) ( ((3*) $) ( ((4*) $) ( ((5*) $) 1 )))) -- == (1*) $ (2*) $ (3*) $ (4*) $ (5*) $ 1 -- == 1* ( 2* ( 3* ( 4* ( 5* 1 ))))ハミング数のリストを順番に返す、非常に簡潔な関数です。
ハミング= 1 : map ( 2 * )ハミング` union ` map ( 3 * )ハミング` union ` map ( 5 * )ハミング上記で紹介した様々なfibs解決策と同様に、この方法も共再帰を用いて、基本ケースである1から始めて、リストの前の要素に基づいて新しい項目を構築することで、必要に応じて数値のリストを生成します。
ここでは、関数をunionバッククォートで囲むことで演算子として使用されます。その句は、重複する項目なしに2つの昇順リストを1つの昇順リストにマージするcase方法を定義し、セットを順序付きリストとして表現します 。その関連関数は、セットの差分を実装します。minus
より効率的な処理のために、一意の倍数のみを生成することが可能です。重複がないため、それらを削除する必要はありません。
smooth235 = 1 : foldr ( \ p s -> fix $ mergeBy ( < ) s . map ( p * ) . ( 1 : )) [] [ 2 , 3 , 5 ] where fix f = x where x = f x -- 不動点コンビネータ、共有ありこれは、重複を考慮しない、より効率的な関数を使用しますmerge（次の関数でも使用されますmergesort）。
mergeBy less xs ys = merge xs ys where merge xs [] = xs merge [] ys = ys merge ( x : xs ) ( y : ys ) | less y x = y : merge ( x : xs ) ys | otherwise = x : merge xs ( y : ys )各縦棒（|）は、ガード句を開始し、その記号の前にガード式=、その後に対応する定義が記述されます。定義は、ガードが真である場合に評価されます。
以下は、高階関数を使用して定義されたボトムアップマージソートです。until
mergesortBy less [] = [] mergesortBy less xs = head $ until ( null . tail ) ( pairwise $ mergeBy less ) [[ x ] | x <- xs ]ペアワイズf ( a : b : t ) = f a b :ペアワイズf tペアワイズf t = t素数の数学的な定義は、ほぼそのままHaskellに翻訳できます。
-- "1より大きい整数で割り切れない整数" -- primes = { n ∈ [2..] | ~ ∃ d ∈ [2..n-1] ⇒ rem nd = 0 } -- = { n ∈ [2..] | ∀ d ∈ [2..n-1] ⇒ rem nd ≠ 0 }primes = [ n | n <- [ 2 .. ], all ( \ d -> rem n d /= 0 ) [ 2 .. ( n - 1 )] ]これは試行除算によって素数を見つけます。効率が最適化されておらず、パフォーマンスが非常に悪いことに注意してください。少し速い（ただし、それでも非常に遅い）[ 3 ]のが、 David Turnerによるこのコードです。
primes = sieve [ 2 .. ] where sieve ( p : xs ) = p : sieve [ x | x <- xs , rem x p /= 0 ]最適な試行分割アルゴリズムははるかに高速です
primes = 2 : [ n | n <- [ 3 .. ], all (( > 0 ) . rem n ) $ takeWhile (( <= n ) . ( ^ 2 )) primes ]またはエラトステネスの無限の篩で、段階的に篩分けを延期する[ 4 ]
primes = 2 : sieve primes [ 3 .. ] where sieve ( p : ps ) ( span ( < p * p ) -> ( h , t )) = h ++ sieve ps ( minus t [ p * p , p * p + p .. ])-- "合成数を含まない 1 より大きい整数で、各素数の倍数を列挙することによって見つかるもの" primes = 2 : minus [ 3 .. ] ( foldr ( \ ( m : ms ) r -> m : union ms r ) [] [[ p * p , p * p + p .. ] | p <- primes ])あるいは、素数の多段階再帰生成を伸縮させることで、ほぼ最適な（リストベースのコードとしては）時間計算量と非常に低い空間計算量を実現する、さらに高速なツリー状の折りたたみバリアント[ 6 ]：
primes = 2 : _Y (( 3 : ) . minus [ 5 , 7 .. ] . _U . map ( \ p -> [ p * p , p * p + 2 * p .. ])) where -- 非共有 Y コンビネータ: _Y g = g ( _Y g ) -- (g (g (g (g (...))))) -- 大きなユニオン ~= nub.sort.concat _U (( x : xs ) : t ) = x : ( union xs . _U . pairwise union ) t素数の連続する平方間のセグメントで配列を操作すると、
import Data.Array import Data.List ( tails , inits )primes = 2 : [ n | ( r : q : _ , px ) <- zip ( tails ( 2 : [ p * p | p <- primes ])) ( inits primes ), ( n , True ) <- assocs ( accumArray ( \ _ _ -> False ) True ( r + 1 , q - 1 ) [ ( m , () ) | p <- px , s <- [ div ( r + p ) p * p ] , m <- [ s , s + p .. q - 1 ] ] ) ]おそらく最短のコードは でしょう。かなり遅いです。 nubBy (((>1) .) . gcd) [2..]
Haskellでは、インデントを使って新しい宣言の開始を示すことができます。例えば、where句では次のように記述します。
product xs = prod xs 1 where prod [] a = a prod ( x : xs ) a = prod xs ( a * x )入れ子になった関数 の 2 つの式はprod垂直方向に揃えられているため、セミコロン区切り文字を省略できます。Haskell では、インデントはdo、、、、、、およびを含むいくつかの構文構造で使用できます。letcaseclassinstance
プログラム構造を示すためにインデントを使用する方法は、ピーター・J・ランディンのISWIM言語に由来し、そこでは「オフサイドルール」と呼ばれていました。これは後にミランダに採用され、ハスケルはミランダのオフサイドルールの類似した（ただし、より複雑な）バージョンである「レイアウト」を採用しました。空白文字を区別する構文を採用した他の言語には、 PythonやF#などがあります。
Haskellにおけるレイアウトの使用は任意です。例えば、product上記の関数は次のように記述することもできます。
product xs = prod xs 1 where { prod [] a = a ; prod ( x : xs ) a = prod xs ( a * x ) }キーワードの後に明示的に開いた中括弧whereがあると、個々の宣言には明示的なセミコロンが使用され、宣言リストは明示的な閉じ中括弧で終了することを示します。明示的な区切り文字のサポートが求められる理由の一つは、Haskellソースコードの自動生成が容易になることです。
Haskellのレイアウト規則は、その複雑さゆえに批判されてきた。具体的には、この規則では、パーサーがレイアウトセクションの処理中に構文エラーに遭遇した場合、閉じ括弧を挿入するように試みるべきであると規定されている（「構文エラー」規則）。この規則を従来の構文解析と字句解析の組み合わせで実装するには、パーサーと字句解析器の双方向の連携が必要となるが、ほとんどの言語では、これら2つの段階は独立して考えることができる。
f値に関数を適用することはx、単純に と表されますf x。
Haskellでは、関数呼び出しと中置演算子は構文的には区別されますが、意味的には区別されません。句読点文字で構成された関数名は演算子として使用でき、バッククォートで囲まれた他の関数名も同様です。また、演算子は括弧で囲まれた前置表記でも使用できます。
この例は、関数を呼び出す方法を示しています。
a + bを加える= a + bten1 = 5 + 5 ten2 = ( + ) 5 5 ten3 = add 5 5 ten4 = 5 ` add ` 5複数の引数を取るように定義された関数は、常に部分適用が可能です。二項演算子は、セクション表記を使用して部分適用できます。
ten5 = ( + 5 ) 5 ten6 = ( 5 + ) 5 addfive = ( 5 + ) ten7 = addfive 5Haskellの例については、「リスト内包表記の概要」を参照してください。
パターンマッチングは、代数的データ型のさまざまなコンストラクタを照合するために使用されます。以下に、各型に対してパターンマッチングを使用する関数をいくつか示します。
-- この型シグネチャは、empty が任意の型を含むリストを受け取り、Bool を返すことを示しています。empty :: [ a ] -> Bool empty ( x : xs ) = False empty [] = True-- Maybe a から値を返します。Nothing が見つかった場合はデフォルト値が与えられます。fromMaybe :: a -> Maybe a -> a fromMaybe x ( Just y ) = y fromMaybe x Nothing = xisRight ::どちらかa b -> Bool isRight ( Right _ ) = True isRight ( Left _ ) = FalsegetName :: Person - > String getName ( Person name __ ) = namegetSex :: Person -> Sex getSex ( Person _ sex _ ) = sexgetAge :: Person - > Int getAge ( Person __ age ) = age上記の関数と、別mapの関数を組み合わせることで、リストの各要素にこれらの関数を適用し、その結果を確認できます。
map empty [[ 1 , 2 , 3 ], [] ,[ 2 ],[ 1 .. ]] -- [False,True,False,False] を返しますmap ( fromMaybe 0 ) [ Just 2 , Nothing , Just 109238 , Nothing ] -- [2,0,109238,0] を返しますmap isRight [ Left "hello" , Right 6 , Right 23 , Left "world" ] -- 戻り値: [False, True, True, False]map getName [ Person "Sarah" Female 20 , Person "Alex" Male 20 , tom ] -- 上記の tom の定義を使用して、["Sarah", "Alex", "Tom"] を返しますHaskellのタプルは、固定数の要素を保持するために使用できます。タプルは、異なる型のデータをグループ化するために使用されます。
account :: ( String , Integer , Double ) --名前、残高、金利を表す 3 つのタプルの型account = ( "John Smith" , 102894 , 5.25 )タプルは、zip* 関数でよく使用され、別々のリストにある隣接する要素をタプルにまとめます（zip4 から zip7 は Data.List モジュールで提供されています）。
-- zip 関数の定義。他の zip* 関数も同様に定義されます。zip :: [ x ] -> [ y ] -> [( x , y )] zip ( x : xs ) ( y : ys ) = ( x , y ) : zip xs ys zip _ _ = []zip [ 1 .. 5 ] "hello" -- [(1,'h'),(2,'e'),(3,'l'),(4,'l'),(5,'o')] を返します -- 型は [(Integer, Char)] ですzip3 [ 1 .. 5 ] "hello" [ False , True , False , False , True ] -- 戻り値 [(1,'h',False),(2,'e',True),(3,'l',False),(4,'l',False),(5,'o',True)] -- 型は [(Integer,Char,Bool)] ですGHCコンパイラでは、タプルは2要素から最大62要素までのサイズで定義されます。
上記の「§ より複雑な例」のセクションでは、calcは2つの意味で使用されており、Haskellの型クラスの名前空間と値の名前空間が存在することを示しています。
Haskellでは代数的データ型が広く使われています。その例としては、組み込みのリストMaybeやEither型などがあります。
-- a のリスト ([a]) は、別の a のリストに consed (:) された a か、空のリスト ([]) のいずれかです。data [ a ] = a : [ a ] | [] -- Maybe 型の何か a は Just something または Nothingのいずれかです。 data Maybe a = Just a | Nothing -- Either atype btype 型の何か a は Left atype または Right btype のいずれかです。data Either a b = Left a | Right b言語のユーザーは、独自の抽象データ型を定義することもできます。人の名前、性別、年齢を表すために使用される抽象データ型の例は次のようになります。
data Sex = Male | Female data Person = Person String Sex Int -- Person はコンストラクタと型の両方であることに注意してください-- Person tom型のオブジェクトを作成する例: Person tom = Person "Tom" Male 27STモナドは、可変変数（STRef）と可変配列（STArrayおよびSTUArray）を用いて、Haskellで命令型プログラミングアルゴリズムを記述することを可能にします。STモナドの利点は、可変変数や配列を破壊的に更新するなど、内部に副作用を持つコードを記述しながら、これらの副作用をモナド内部に閉じ込めることができる点です。その結果、STモナドを用いて記述された関数は、プログラムの他の部分からは純粋な関数として認識されます。これにより、関数型コードを書くことが現実的でない場合でも、命令型コードを使用しながら、純粋コードが提供する安全性をすべて維持することが可能になります。
以下は、数値のリストを受け取り、可変変数を使用してそれらを合計するプログラムの例です（HaskellのSTモナドに関するwikiページから引用）。
import Control.Monad.ST import Data.STRef import Control.MonadsumST :: Num a => [ a ] -> a sumST xs = runST $ do -- runST はステートフル ST コードを純粋なものにします。summed <- newSTRef 0 -- STRef (可変変数) を作成しますforM_ xs $ \ x -> do -- 引数リスト xs の各要素について .. modifySTRef summed ( + x ) -- n にあるものに加算します。readSTRef summed -- 上記のrunSTによって返されるnの値を読み取ります。STMモナドは、Haskellにおけるソフトウェアトランザクショナルメモリの実装です。GHCコンパイラに実装されており、トランザクション内で可変変数を変更することを可能にします。
Haskellは純粋関数型言語であるため、関数は副作用を持つことができません。また、厳密な型ではないため、評価順序も明確に定義されていません。これは、環境とのやり取りを必要とする実際のプログラムにとって課題となります。Haskellは、型システムを活用して命令型構造の適切な順序付けを保証するモナド型によってこの問題を解決します。典型的な例は入出力（I/O）ですが、モナドは可変状態、並行処理とトランザクションメモリ、例外処理、エラー伝播など、他の多くの用途にも役立ちます。
Haskellはモナド式のための特別な構文を提供しており、副作用のあるプログラムを現在の命令型プログラミング言語と同様のスタイルで記述できます。これにはモナド入出力の背後にある数学的な知識は必要ありません。次のプログラムは、コマンドラインから名前を読み込み、挨拶メッセージを出力します。
main = do putStrLn "あなたの名前は何ですか？" name <- getLine putStr ( "こんにちは、" ++ name ++ "! \n " )do 表記法はモナドの扱いを容易にします。この do 式は、モナド演算子を直接使用する糖衣を取り除いたバージョンと同等ですが、（おそらく）記述しやすく理解しやすいでしょう。
main = putStrLn "お名前は何ですか？" >> getLine >>= \ name -> putStr ( "こんにちは、" ++ name ++ "! \n " )Haskell言語の定義には並行処理も並列処理も含まれていないが、GHCは両方をサポートしている。
Concurrent Haskellは、スレッドと同期をサポートする Haskell の拡張です。[ 7 ] GHC の Concurrent Haskell の実装は、軽量な Haskell スレッドを少数の重量級オペレーティングシステム(OS) スレッドに多重化することに基づいています。[ 8 ]これにより、Concurrent Haskell プログラムは対称マルチプロセッシングを介して並列に実行されます。ランタイムは数百万の同時スレッドをサポートできます。[ 9 ]
GHCの実装では、OSスレッドの動的プールが採用されており、Haskellスレッドが他の実行中のHaskellスレッドをブロックすることなくブロッキングシステムコールを実行できるようになっています。[ 10 ] そのため、軽量なHaskellスレッドは重量級のOSスレッドのような特性を持ち、プログラマーは実装の詳細を意識する必要がありません。
最近、 Concurrent Haskell は、共有データに対する複合操作をトランザクションとしてアトミックに実行する並行性抽象化であるソフトウェア トランザクショナル メモリ(STM)のサポートで拡張されました。 [ 11 ] GHC の STM 実装は、トランザクション内で非トランザクション操作が実行されないように静的コンパイル時保証を提供する、現在までの唯一の STM 実装です。Haskell STM ライブラリは、他の STM にはない 2 つの操作 と も提供しており、これらを組み合わせることで、ブロッキング操作をモジュール式かつ構成可能な方法で定義できます。retryorElse