第2章　関数プログラミングのパラダイム―命令プログラミングと何が違うのか

この章では、命令プログラミングと関数プログラミングのパラダイムの違いを理解するために、簡単な計算問題を取り上げます。

命令プログラミングと関数プログラミング

当たり前過ぎて意識されていないかもしれませんが、改めて命令プログラミングのパラダイム（以下「命令型」と略記）を説明すると、次のようになります。

命令を列挙する（典型的には命令である文をセミコロンで区切って並べる）
状態がある（状態とは再代入可能な変数のこと）
再代入を使って状態を変化させる

一方、関数プログラミングのパラダイム（以下「関数型」と略記）は次のようになります。

関数を引数に適用する
状態はない
（値を破壊したくなったら）新たな値を作る

状態がないので、変数の値は変わりません。これが関数プログラミングを永続データプログラミングと定義した理由です。しかし、関数型で本当に問題が解けるのか疑問だと思います。これから簡単な計算問題を使って、両パラダイムの違いを浮き彫りにします。

パラダイムの違いがわかる例題

次のような問題を解く関数calcを定義することを考えます。

入力として整数の配列あるいはリストが与えられる（たとえば[10,20,30,40,50]）
0から数えてn番目の要素にはnを掛ける
それらすべてを足し合わせて出力として返す

つまり、次のような計算をします。

10 * 0 + 20 * 1 + 30 * 2 + 40 * 3 + 50 * 4

簡単ですね。

命令的なfor文による問題解決

命令プログラマであれば、この問題をfor文か類似のループで解くでしょう。実際にJavaScriptで関数calcを書いてみます。for文を使うと、次のように実装できます。

calc.js

function calc(ar) {
    var ret = 0;
    for (var i=0; i < ar.length; i++) {
        ret = ret + ar[i]*i;
    }
    return ret;
}

このcalcは、命令型の特徴を備えています。

セミコロンで区切って命令を列挙している
状態retとiがある
retとiはループが回るたびに再代入されている

実際に動かしてみましょう。次のコードはRhinoを使い、入力として配列[10,20,30,40,50]を与える例です。

% rhino
js> load("calc.js")
js> calc([10,20,30,40,50]);
400

正しい答え400が出てきました。

命令プログラマであれば、これとはまったく異なる解決方法があるとは想像もできないかもしれません。また、このプログラムは十分に簡潔で、これ以上分割はできないと思うでしょう。しかし、関数プログラマから見ると、この関数は仕事のやり過ぎに見えます。

少し話がそれますが、筆者がJavaScriptを勉強していたころ、JavaScriptの神様であるDouglas Crockford氏のエッセイをよく読んでいました。エッセイの一つに「JavaScript：世界で最も誤解されたプログラミング言語」があります。このエッセイで筆者が衝撃を受けたのは、「⁠不格好なforステートメント」という言葉でした。for文とは不格好なのでしょうか？この疑問は、関数プログラミングを習得することでようやく氷解しました。

関数的なMapReduceによる問題解決

関数プログラミングでは、MapReduceという方法で解きます。MapReduceと言うと、Googleの分散処理フレームワークが有名ですが、このシステムのアイデアの根源は関数型のmapとreduceを使う手法です。さっそく、対話環境でMapReduceを試してみましょう。

リストをまとめる

Haskellでは、リストのリテラルが用意されており、角括弧の中に要素をカンマで区切って書きます。同じ表記がJavaScriptでは配列でしたが、Haskellではリストを意味します。整数のリストのリテラルを評価してみましょう（プロンプトPrelude>は>と略記します⁠）⁠。

> [10,20,30,40,50]
[10,20,30,40,50]

整数のリストそのものが返ってきました。次に、このリストの要素と掛け合わせるカウンタを用意しなくてはいけません。Haskellでは、[はじめ..おわり]と書くと、値を増やしながら列挙してくれます。

> [0..4]
[0,1,2,3,4]

リストが2つあると扱いづらいので、常套手段である関数zipで1つにまとめましょう。

Haskellでは、関数を呼び出す際に、関数のあとの引数を丸括弧で囲む必要はありません。引数はカンマではなく、空白で区切って列挙します。

> zip [0..] [10,20,30,40,50]
[(0,10),(1,20),(2,30),(3,40),(4,50)]

リストが1つ新たに生成されました。この要素は(0,10)のように、カウンタと整数の組になっています。このように表記される組は、無名の構造体であると理解するとよいでしょう。

zipの第一引数であるリストには「おわり」が指定されていません。この場合、必要なだけ生成することを意味します。zipは、短いほうのリストに合わせて組のリストを生成しますので、実際に第一引数は第二引数の長さ分だけカウンタを生成します。

あとで利用しやすいように、上記の結果にret1という名前を付けておきましょう。対話環境では、変数を定義する場合にletを使います。

> let ret1 = zip [0..] [10,20,30,40,50]

念のため、ret1自体を評価することで、ret1の中身を調べてみましょう。

> ret1
[(0,10),(1,20),(2,30),(3,40),(4,50)]

mapを使う

いよいよmapを使ってみましょう。mapとは、第一引数に関数を、第二引数にリストを取ります。そして、その関数をリストの要素それぞれに適用します。関数を引数に取る関数は、高階関数と呼ばれるのでした。mapは、最も基本的で最も有名な高階関数です。

今やりたいことは、カウンタと整数を掛け合わせることです。そこでまず、カウンタと整数の組を取り、互いを掛け合わせる関数mulを定義してみましょう。対話環境では、関数を定義する場合もletを使います[1]⁠。

let mul (i,x) = x * i

この定義には、第3章で説明するパターンマッチが使われています。今は単にこのように書くと思って進んでください。

そして、mapを使ってmulをret1の各要素に適用してみます。

> map mul ret1
[0,20,60,120,200]

整数のリストが新たに生成されました。だんだん答えに近づいてきましたね。これにもret2という名前を付けておきましょう。

> let ret2 = map mul ret1

reduceを使う

次にreduceを使います。reduceとは、リストの要素を何らかの方法で1つの値に集約することです。関数プログラミングでは、これを「畳み込み」と呼びます。畳み込みの関数としてreduceが使われるのはCommon Lispで、ほかの言語ではfoldと呼ばれることが多いようです。

今やりたいことは、整数のリストの要素すべてを足し合わせることです。これを畳み込みで実現するには、次のような計算をすることになります。

((((0 + 0) + 20) + 60) + 120) + 200

つまり、初期値0に対して、要素を順に足していくのです。Haskellの畳み込み関数foldlは、第一引数に演算子、第二引数に初期値、第三引数にリストを取ります。foldlも高階関数です。Haskellの文法では、演算子を引数に指定する場合、次のように丸括弧で囲む必要があるので注意してください。

> foldl (+) 0 ret2
400

答えが出てきました！

プログラムにまとめる

では、以上の結果をまとめて関数calcを定義してみましょう。

> let mul (i,x) = x * i
> let calc xs = foldl (+) 0 (map mul (zip [0..] xs))

Haskellでは、リストを表す変数名を複数形にする習慣があります。上記では、変数xsがその例になります。リスト [10,20,30,40,50] を与えて実行してみます。

> calc [10,20,30,40,50]
400

再代入なしに問題が解けました！

このように関数型言語では、式と式とをつないでより大きな式を作っていきます。筆者が関数プログラミングを勉強したときに難しいと感じたのは、プログラム全体を1つの式で表現するという制約でした。文を列挙することに慣れていた頭には、大きな発想の転換が必要だったのです。

ファイルに書き出す

これまで対話環境でプログラムを作成してきましたが、これをファイルに書き出しましょう。Haskellプログラムの拡張子は「.hs」です。今回は、次のプログラムをcalc.hsとして保存します。

mul (i,x) = x * i
calc xs = foldl (+) 0 (map mul (zip [0..] xs))

対話環境ではないので、letを削る必要があります。このファイルを対話環境に読み込ませるには、コマンドghciの引数としてファイルcalc.hsを指定します。

% ghci calc.hs
Main>

ファイルを読み込むとプロンプトがPrelude>から変化します。以降はこちらも>と略記します。

calcを使ってみましょう。

> calc [10,20,30,40,50]
400

calc.hsから読み込んだ、関数calcを評価できました。

繰り返しと再帰との関係

再代入なしでも、値を新しく作り出せば問題が解けることがわかったと思います。ただ、まだすっきりしていないところがあるかもしれません。for文がないのに、繰り返しはどうやって実現したのでしょうか？

リストを走査するという繰り返しの機能は、zip、map、そしてfoldl自体が備えていて、それは再帰で実現されています。次にmapの実装を示します。

map f [] = []
-- mapがmap自身を呼び出している
map f (x:xs) = f x : map f xs

このプログラムの意味を理解する必要はありません。mapがmap自身を呼び出しているのがわかれば十分です。このように関数プログラミングでは、繰り返しを再帰で実現します。ただ、再帰を使うよりも、適切な高階関数を利用するほうが良いプログラミングスタイルだとされています。

関数プログラミングの特徴：部品プログラミング

関数型言語では、関数に一部の引数を与えることで、カスタマイズした関数を作り出す機能があります。これは「部分適用」と呼ばれています。

例として、mapとmulを取り上げましょう。mapは汎用的な関数ですが、これにmulを与えて、mulをmapする専用の関数mapMulを作り出したいとします。calc.hsを対話環境に読み込ませた状態で、次のように入力してください。

> let mapMul = map mul

mapは二引数の関数でしたが、引数1つは埋まったので、mapMulは一引数の関数です。mapMulを使ってみましょう。

> mapMul [(0,10),(1,20),(2,30)]
[0,20,60]

また、Haskell特有の話になりますが、関数合成の演算子「.」が用意されています。これは、一引数の関数を連結していける演算子です。calcの実装を関数の連鎖に変えてみましょう。高階関数に部分適用することで専用の一引数関数を作り、それを「.」で連結するのです。次のようになります。

let calc = foldl (+) 0 . map mul . zip [0..]

このプログラムの意味が正確にわからなくてもかまいません。ただ、図1のように、小さな部品から大きな部品が組み立てられていることがわかれば十分です。図1からわかるように、関数型ではデータが流れる信号処理回路のようなイメージでプログラムを書いていきます。

関数プログラミングでは、関数自体が部品だと言われる所以（ゆえん）をまとめます。

汎用の部品である高階関数を部分適用でカスタマイズして新たな部品を作る
それらをつなぎ合わせてさらに大きな部品を作る

ここで、JavaScriptで実現したcalcをもう一度見てください。仕事をやり過ぎているように思えてきませんか？

関数プログラミングの特徴：高いエラー検出率

ここで高いエラー検出率について説明しましょう。そのためには、どうしても型の表記について説明する必要があります。

関数の型を書く方法

Haskellでは、関数や変数の型を、定義の上の行に書きます。例として、次のコードを見てください。

isDigit :: Char -> Bool
isDigit c = c >= '0' && c <= '9'

isDigitは引数に文字を取り、真理値を返す関数です。文字が数字の場合は真を、そうでなければ偽を返します。文字の型はChar、真理値の型はBoolと表記します。このように、Haskellでは（具体的な）型の名前は大文字で始めます。::は「の型は」という意味です。->は「左の型の値を取って右の型の値を返す」ことを意味します。isDigitの定義のほうは、特に問題なく理解できるでしょう。

このコードをたとえばchar.hsというファイルとして保存し、GHCiに読み込ませて使ってみましょう。

% ghci char.hs
> isDigit '0'
True
> isDigit 'a'
False

Haskellでは真がTrue、偽がFalseと表記されます。

複数の引数を取る関数の型

isDigitは一引数の関数でした。次に二引数の関数の例として、makeStringを見てみましょう。

makeString :: Char -> Int -> [Char]
makeString c 0 = []
makeString c n = c : makeString c (n - 1)

makeStringは第一引数に文字（Char⁠）⁠、第二引数に整数（Int）を取り、文字のリスト（[Char]）を返します。型においても角括弧はリストを意味します。この例からわかるように、N個の引数を取る場合は、->をN個使って表現します。makeStringはどういう文字のリストを返すのか実際に使ってみましょう。上記のコードをファイルstring.hsとして保存し、対話環境に読み込ませてから次のように入力してください。

> makeString 'w' 5
"wwwww"

文字列が返ってきました。このようにHaskellでは、文字列は文字のリストとして実現されています。たとえば、文字列"wwwww"は['w','w','w','w','w']の別表現です。makeStringは、与えられた文字を与えられた数だけ列挙したリストを返す関数だとわかりました。

型変数

たとえば、リストの長さを返す関数を考えましょう。もし、リストにある要素の長さを測る関数を型ごとに定義しないといけないとしたらとても面倒です。関数型言語では、型変数を使って要素の型をパラメータ化することで、要素の型に依存しない関数を定義できます。次は基本関数lengthの型です。

length :: [a] -> Int

aが型変数です。このようにHaskellでは型変数を小文字で書きます[2]⁠。型変数aは、具体的な型がなんであろうとも、lengthの計算には影響しないことを表しています。具体的な型が必要であれば、それはコンパイル時に推論されます。実際にlengthを使ってみましょう。

> length "Hello"
5
> length [1..10]
10

高階関数の型

高階関数mapの型は次の通りです。

map :: (a -> b) -> [a] -> [b]

第一引数に「a->b」という型を持つ関数、第二引数に[a]という型のリストを取り、[b]という型のリストを返します。先ほど作成したchar.hsを対話環境に読み込ませた状態で使ってみましょう。

> map isDigit "H2O"
[False,True,False]

isDigitの型は「Char->Bool」でした。よって、aがChar、bがBoolになります。このことから、第二引数の型は[Char]、結果の型は[Bool]に決まります。

型推論と型検査

先ほどHaskellで実装したcalcに型を書いてみましょう。

calc :: [Int] -> Int
calc = foldl (+) 0 . map mul . zip [0..]

そして、このcalcをコンパイルするときに何が起きるか考えてみます。コンパイラがわかるのは、プログラマが指示したcalcの型と基本関数の型です。

たとえば、「⁠foldl(+)0」の部分について考えてみましょう。foldlの型は次の通りです。

foldl :: (a -> b -> a) -> a -> [b] -> a

foldlの結果がcalcの結果になるわけですから、aはIntになります。また、演算子+の型は「a->a->a」なので、foldlのaとbは同じ型になります。よって、foldlの具体的な型は次のように推論されます。

foldl :: (Int -> Int -> Int) -> Int -> [Int] -> Int

ここで、第二引数まで部分適用された「foldl(+)0」の型は、次のようになります。

foldl (+) 0 :: [Int] -> Int

同様に、その他の部品の型は、次のように推論されます。

map mul :: [(Int,Int)] -> [Int]
zip [0..] :: [Int] -> [(Int,Int)]

中にカンマのある丸括弧は、組の型です。最後のピースである、関数結合の演算子「.」の型を見てみましょう（演算子の型を書く場合は、演算子を丸括弧で囲む必要があります⁠）⁠。

(.) :: (b -> c) -> (a -> b) -> a -> c

この型を字面から理解するのは難しいので、もう一度図1を見てください。演算子「.」は、部品を並べてつなげる役割を果たしています。演算子「.」が要求するのは、ある部品の出力の型が次の部品の入力の型と一致することです。calcの場合は、一致していることが図1から読み取れると思います。どこか1つでも型の矛盾があれば、コンパイル時にエラーとなります。

エラー検出の例

具体的に、エラーが報告される例を見てみましょう。かなり恣意（しい）的な例で恐縮ですが、calcの実装を変えてみます。図1で示されているように、calcは3つの部品から構成されていました。ここで、真ん中の部品であるmap mulを取り除いてみます。

calcErr.hsというファイルに次のコードを書き込んでください。

mul (i,x) = x * i

calc :: [Int] -> Int
calc xs = foldl (+) 0 . zip [0..]

GHCiに読み込ませてみます（図2⁠）⁠。

図2　エラー検出の例

% ghci calcErr.hs
 略 
calcErr.hs:4:11:
    Couldn't match expected type `Int' with actual type `a0 -> c0'
    In the expression: foldl (+) 0 . zip [0 .. ]
    In an equation for `calc': calc xs = foldl (+) 0 . zip [0 .. ]
 略

エラーの意味はわからなくてかまいません。エラーを発見できたことがわかれば十分です。

zip [0..]の出力の型は[(Int,Int)]であり、foldl(+)0の入力の型は[Int]ですから型が合いません。このエラーを発見できたのです。エラーが見つけられたのは、プログラムをすべて式で構成したからです。

このように関数型言語では、式と式との型の関係が厳密に検査されます。このおかげで静的型付きの関数型言語では、たくさんのエラーをコンパイル時に発見でき、コンパイルに通ればおおむね意図通りに動く感覚が味わえます。もちろん、型に関するエラーがないだけで、値に関するエラーは残る可能性はあるので、テストをおろそかにしてはいけません。