第4回　再帰とデータ型の話をしよう

山下 伸夫
株式会社タイムインターメディア

2009/2/16

計算の効率

　stepWaysは最初の0段目と1段目を除くと、

stepWays n = stepWays (n-1) + stepWays (n-2)

という定義になっている。右辺の+の第1オペランドの部分を1段階展開すると、

stepWays n = (stepWays (n-2) + stepWays (n-3)) + stepWays (n-2)

となっている。stepWays (n-2)の項が2カ所に現れているが、それぞれ別々に計算することになるので冗長で効率の悪い計算になる。実際、階段が50段もあれば待てなくなる。

　stepWays nの定義の右辺で、stepWays (n-1)とstepWays (n-2)を独立に計算しているのが敗因なのである。少し工夫をしてみよう。

stepWays2 n ≡ (stepWays (n+1), stepWays n)

となるstepWays2という関数を考える。まず、

stepWays2 0 ≡ (stepWays 1, stepWays 0)
            ≡ (1, 1)

である。次に、stepWays2 nの右辺を考える。これはタプルの1番目の要素と2番目の要素に計算が分岐しているので改善されるわけではない。そこで、タプルの第1要素を1段展開する。

stepWays2 n ≡ (stepWays (n+1), stepWays n)
            ≡ (stepWays n + stepWays (n-1), stepWays n)

　ここで、1つ前の段階stepWays2 (n-1)を考えると、

stepWays2 (n-1) ≡ (stepWay n, stepWay (n-1))

である。そうすると、stepWays nは以下のように定義できる。

stepWays2 n = (a+b, a) where (a,b) = stepWays2 (n-1)

　これで計算の分岐がなくなった。あらためて、stepWaysをstepWays2を使って定義すると、

stepWays = snd . stepWays2

となる。.は関数合成であり、sndはタプルの第2要素を取り出す関数である。これなら、100段の階段でもあっさり求められる。

　もともとの素朴な定義は、重複があるにもかかわらず複数独立に再帰計算が行われるために、非効率であった。このような再帰関数を、タプルを使って複雑な問題にしてから解くと効率が改善されるというと、なんだか少しだまされたような感じはする。しかし、確かに速くなっている。

データ型の話をしよう

　ここまでは組み込みの論理値型Bool、数値型である倍精度浮動小数点数Double、任意倍長整数Integerとタプルというデータ構造、それに前回自前で定義したBMICategoryという型しか使っていない。リストの話をする前に、Haskellの標準ライブラリPreludeで定義されている具体的な基本データ型について少しだけ触れておく。

論理値型

　論理値型Boolには、FalseおよびTrueの2つの値しかない。if式の条件部分やガードに現れる式の値は必ず論理値型でなければならない。

Prelude> if True then "True" else "False"
"True"
Prelude> if 't' then 1 else 0

<interactive>:1:3:
Couldn't match expected type `Bool' against inferred type `Char'
    In the expression: 't'
    In the expression: if 't' then 1 else 0
    In the definition of `it': it = if 't' then 1 else 0
Prelude> if otherwise then True else False
True

　このエラーメッセージは、if式の条件節はBool型の値（を表す式）でなければならないのに文字Bool型の値（を表す式）になっていると推論したと文句をいっているのである。

数値型

　Preludeで定義されているのは、以下の4つである。

型 説明
Float 単精度浮動小数点数
Double 倍精度浮動小数点数
Int 固定倍長符号付き整数
Integer 任意倍長符号付き整数

　浮動小数点数は2種類あり、単精度のものがFloatで、倍精度のものがDoubleである。浮動小数点数を扱うとき、GHCではDoubleを使うべきである。それは、コンパイラはDoubleに最適化されていて、Floatの計算はむしろ遅いからである。

　整数も2種類あり、固定倍長のIntと、任意倍長のIntegerがある。Intの幅は計算機システムに依存しており、たいていそのシステムでのナイーブに表現できるintと同じ幅である。すなわち、32bitマシンならIntも32bit幅である。Haskell 98の標準では29bit以上の幅であることが規定されている。自分のシステムでのIntの最大値と最小値は、ghciを使って以下のようにして調べることができる。

Prelude> minBound :: Int
-2147483648
Prelude> maxBound :: Int
2147483647

　Integerは任意倍長の符号付き整数で、Intの範囲で収まらない整数を扱わなければならないときに必要になる。Integerの計算は、Intに比較するとかなり高価なので、Intの範囲を超えないことがはっきりしている場合には使うべきではない。

2/3

Index
再帰とデータ型の話をしよう
  Page1
階乗を計算する関数
階段の昇り方
Page2
計算の効率
データ型の話をしよう
論理値型
数値型
  Page3
文字と文字列
リスト
文字列は文字のリスト

のんびりHaskell
　Coding Edgeお勧め記事
いまさらアルゴリズムを学ぶ意味
コーディングに役立つ！ アルゴリズムの基本（1）　コンピュータに「3の倍数と3の付く数字」を判断させるにはどうしたらいいか。発想力を鍛えよう
Zope 3の魅力に迫る
Zope 3とは何ぞや？（1）　Pythonで書かれたWebアプリケーションフレームワーク「Zope 3」。ほかのソフトウェアとは一体何が違っているのか？
貧弱環境プログラミングのススメ
柴田 淳のコーディング天国　高性能なIT機器に囲まれた環境でコンピュータの動作原理に触れることは可能だろうか。貧弱なPC上にビットマップの直線をどうやって引く？
Haskellプログラミングの楽しみ方
のんびりHaskell（1）　関数型言語に分類されるHaskell。C言語などの手続き型言語とまったく異なるプログラミングの世界に踏み出してみよう
ちょっと変わったLisp入門
Gaucheでメタプログラミング（1）　Lispの一種であるScheme。いくつかある処理系の中でも気軽にスクリプトを書けるGaucheでLispの世界を体験してみよう
　　Coding Edgeフォーラムフィード　 2.0／1.0／0.91


Coding Edge フォーラム 新着記事
＠ITメールマガジン　新着情報やスタッフのコラムがメールで届きます（無料）

注目のテーマ

>

Coding Edge 記事ランキング

本日 月間
＠IT