より複合的な例

ウィキペディア小見出し辞書

より複合的な例

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/11/20 02:06 UTC 版)

「Haskell」の記事における「より複合的な例」の解説

引数 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) 無限リストは 余再帰（リストの後ろの値は要求があったときに 0 と 1 の二つの初期要素から開始され算出される）によって実現される。このような定義は遅延評価の実例で、Haskell プログラミングでも重要な部分である。 ただし、フィボナッチ数列の生成の場合は、ある要素の値が必要であれば、その要素より前にある要素の値は全て必要である。従って、遅延させた上で結局は後から全てその値を求めることになり、むしろ無駄であるので、この場合は遅延させない組込関数seqを使用したほうが効率は良くなり、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 | xy = y : xxs # ys 上に示されたさまざまな fibs の定義のように、これはオンデマンドに数のリストを実現するために無限リストを使っており、1 という先頭要素から後続の要素を生成している。 ここでは、後続要素の構築関数は where 節内の記号 # で表現された中置演算子で定義されている。 各|は、等号の前半の条件部分と、後半の定義部分からなるガード節を構成する。