人気ブログランキング | 話題のタグを見る

RWH の読み方(29) 第4章

Real World Haskell 第4章 Functional Programming

How to Think About Loops

コンピュータのプログラムで欠かせないのが、同じ処理を繰り返すループの記述だ。しかし、Haskell には for ループも while ループもない。Haskell ではループを記述する方法は下のサブセクションに見られるように多彩だ。

Explicit Recursion
Transforming Every Piece of Input
Mapping over a List
Selecting Pieces of Input
Computing One Answer over a Collection
The Left Fold
Why Use Folds, Maps, and Filters?
Folding from the Right
Left Folds, Laziness, and Space Leaks
Further Reading

Explicit Recursion

C言語の簡単なループのプログラムをどうやって Haskell のプログラムに変換していくかということを例にとって、Haskell の基本的な繰り返しプログラムである再帰関数を解説している。

しかし、次のプログラムが数字の列を整数に変換していることが読めれば、このサブセクションはスキップできる。

import Data.Char (digitToint)

asInt :: String -> Int
asInt xs = loop 0 xs

loop acc [] = acc
loop acc (x:xs) =
  let acc' * 10 + digitToInt x
  in loop acc' xs

このプログラムの説明はRWHの本文にあるので省略するが、再帰関数について少し考えてみる。

Prelude にはリストの総和を求める関数 sum があるが、これを自分で定義して mysum を作ってみる。

まず空のリストの総和は 0 だ。

mysum [] = 0

この定義式には右側に mysum が出てこないので、このような式のことを the base case あるいは terminating case という。再帰関数はこの base case がないと展開が終了せず無限ループかエラーになってしまう。

つぎにリストのパターンが (x:xs) の場合、つまり、先頭の要素とそれ以下のリストのパターンに分けられる場合、mysum の定義は次のようになる。

mysum (x:xs) = x + mysum xs

この定義式では等号の右側にも mysum があるので、the recursive case と呼ばれる。等号の右にも左にも mysum があるが、mysum (x:xs) と mysum xs の値は違うので上のような定義をしても矛盾は起きない。

この2つの定義があればこれを適用することでたとえば mysum [1,2,3] の値を計算することができる。展開の様子をシミュレートすると次のようになる。

mysum [1,2,3]
= 1 + mysum [2,3]
= 1 + (2 + mysum [3])
= 1 + (2 + (3 + mysum []))
= 1 + (2 + (3 + 0))
= 6

手続き型の言語のように計算の途中経過をアキュームレーターに記憶させておくのではなく、次々に式を展開することによって繰り返しの計算が実現できる。

Haskell の繰り返し処理は本質的にこの単純な再帰関数と同じ形になる。上のRWHの例でも the base case の loop acc [] = acc と the recursive case の loop acc (x:xs) = ... があるのが分かる。

Haskell の繰り返し処理は手続き型のプログラムからの類推よりも再帰関数の特質をとらえてから考えるほうがかえって分かりやすい。

関数言語の繰り返し処理と手続き型言語のループとは全く別のものと区別してしまったほうがプログラムを発想しやすいような気がする。

このセクションの後に様々なライブラリ関数を利用した繰り返し処理の例が出てくるが、どのライブラリ関数もその中身は再帰的関数だ。Haskell の繰り返し処理はすべて再帰関数で行うと単純化してもかまわない。
by tnomura9 | 2012-04-08 16:10 | Haskell | Comments(0)
<< Jyunjyou☆Fighter RWH の読み方(28) 第4章 >>