Rubyによる関数型プログラミング

Functional programming with Ruby

Arnau Sanchez

Revision History
Jul 10, 2012
Last updated.

概要

この文書は、 Functional programming with Ruby を 「勝手に」翻訳したものです。 従って、著作権は Arnau Sanchez 氏が所有していることに 注意してください。

Table of Contents

はじめに
理論
Rubyにおける関数型プログラミング
変数を更新してはいけない
高階関数としてのブロック
OOPと関数型プログラミング
あらゆるすべてが式である
再帰
遅延列挙オブジェクト
実践的な例題
おわりに
プレゼンテーション
興味を持った読者へ

はじめに


- 命令型言語って強いの?
- イヤ、イヤ、イヤ。速くて、お手軽で、いくらか目立ってるだけさ

x = x + 1

古き良き小学校の時代、この行には困惑させられたものだった。 魔術的な x が、加算されたのに等しいままでいる事に。 どういうわけか、プログラミングを始めると、それに構わなくなる。 「やれやれ、それは重大な事柄じゃないし、プログラミングとは現実のビジネス行為なんだから、 数学的な純粋さについてあら探しなんて必要無い (その議論なら、大学にいる狂った髭面野郎どもにさせておけばいい)」と思っていた。 けれども、ただ知らなかっただけで、我々が間違っていて高い代償を支払っていたのは 明らかである。

理論

Wikipedia によれば、「関数型プログラミング(functional programming, FP)とは、 計算を数学的な関数の評価とみなし、 状態や可変データを避けるプログラミングパラダイム」である。 言い換えると、関数型プログラミングは、 副作用が無く変数の値を変化させないコードを推奨する。 状態の変更を強調する命令型プログラミング(imperative programming)とは対照的である。

驚くなかれ、(関数型プログラミングとは)単にそれだけのことでしかない。 では、その長所とは何か?

より明解なコード(cleaner code):

「変数」は一度定義されれば変更されないのだから、 プロジェクトの活動全体を通して、関数、メソッド、クラスを理解するために 状態の変化を追いかけなくてもよい。

参照透明性(referential transparency):

式は値で置き換えることができる。 もし同じパラメタで関数をコールすれば、出力が同じになるのは確かである (変化するかもしれない状態がどこにも存在しないのだから)。 かのアインシュタインが 狂気 を 「同じ事を繰り返し行い、違う結果を期待すること」と定義したのには 理由があるのだ。

参照透明性は、以下に示す素敵な世界への扉を開く。

並列化(parallelization):

もし関数のコールが相互依存しないのであれば、 競合条件(race-condition)の問題を無視して、 異なるプロセスあるいは異なるマシンでそれらを実行できる。 関数型パラダイムであれば、「正常な」並行コードに関する (ロック、セマフォ、...といった)厄介な詳細は、すべて消え失せる。

メモ化(memoization):

関数コールとリターン値が等しいのだから、 それをキャッシュしてもかまわない。

モジュール化(modularization):

コード全体の一面に広がる状態を持たないのだから、 小さなプロジェクトを束ねたブラックボックスで組立てることによって、 ボトムアッププログラミングを推進する。

容易なデバッグ(ease of debugging):

関数は(相互に)分離され、入力と出力だけに依存するのだから、 デバッグはとても容易である。

Rubyにおける関数型プログラミング

これが実に素晴らしいとしても、どうやれば(実際に関数型言語ではない)Rubyにおける 日常のプログラミングに応用できるのだろうか? 一般的な感覚であれば関数型プログラミングとはスタイルであり、 どのような言語で用いられてもかまわない。 もちろんこのパラダイム向けに特別に設計された言語上では より自然な作法であるけれど、 いくつかの拡張を加える事で どんな言語にも適用できる。

それでは、このガイドでは「理論的な関数型の純粋性を信奉する風変わりなスタイルを 布教するつもりがない」ことを明らかにしていこう。 逆に、私の試みのポイントは、 コードの品質を向上させたいときはいつでも関数型プログラミングを使用 すべきであるけれど、 それ以外のときには(関数型プログラミングは)まさに誤った解決手段である、というものである。

変数を更新してはいけない

変数を更新するくらいなら、新しく生成しなさい。

配列や文字列に追記してはいけない

No:

indexes = [1, 2, 3]
indexes << 4
indexes # [1, 2, 3, 4]

Yes:

indexes = [1, 2, 3]
all_indexes = indexes + [4] # => [1, 2, 3, 4]

ハッシュを更新してはいけない

No:

hash = {:a => 1, :b => 2}
hash[:c] = 3
hash

Yes:

hash = {:a => 1, :b => 2}
new_hash = hash.merge(:c => 3)

その場で更新する破壊的メソッドを使用してはいけない

No:

string = "hello"
string.gsub!(/l/, 'z')
string # => "hezzo"

Yes:

string = "hello"
new_string = string.gsub(/l/, 'z') # => "hezzo"

値を累積させる方法

No:

output = []
output << 1
output << 2 if i_have_to_add_two
output << 3

Yes:

output = [1, (2 if i_have_to_add_two), 3].compact

高階関数としてのブロック

ある言語が関数型を利用するのであれば、高階関数(higher-order function)が必要だ。 まさしく関数はパラメタとして他の関数を受け取ることができるし、 他の関数を返すこともできる。

Ruby(およびSmalltalkや他のいくつか)ではこの配慮は特別であり、 その仕掛けである ブロック は言語内に組み込まれている。 ブロックは、思うままに渡したり実行したりできる名前の無いコードの断片である。 では、関数コンストラクタを組立てる ブロックの典型的な使用方法を見ていくことにしよう。

空リスト + each + push = map

No:

dogs = []
["milu", "rantanplan"].each do |name|
  dogs << name.upcase
end
dogs # => ["MILU", "RANTANPLAN"]

Yes:

dogs = ["milu", "rantanplan"].map do |name|
  name.upcase
end # => ["MILU", "RANTANPLAN"]

空リスト + each + 条件付き push -> select/reject

No:

dogs = []
["milu", "rantanplan"].each do |name|
  if name.size == 4
    dogs << name
  end
end
dogs # => ["milu"]

Yes:

dogs = ["milu", "rantanplan"].select do |name|
  name.size == 4
end # => ["milu"]

初期値 + each + 累積 -> inject

No:

length = 0
["milu", "rantanplan"].each do |dog_name|
  length += dog_name.length
end
length # => 15

Yes:

length = ["milu", "rantanplan"].inject(0) do |accumulator, dog_name|
  accumulator + dog_name.length
end # => 15

このコードの場合には累積子と要素との間に単純な演算子があるから、 ブロックを書かなくても、その演算子のシンボルを渡すだけで済む。

length = ["milu", "rantanplan"].map(&:length).inject(0, :+) # => 15

初期値 + each + 累積 + push -> scan

畳み込みの最終結果だけでなく(以前に見た inject)、部分的な値も欲しいケースを想像してみよう。 命令型コードでは、以下のように書く。

lengths = []
total_length = 0
["milu", "rantanplan"].each do |dog_name|
  lengths << total_length
  total_length += dog_name.length
end
lengths # => [0, 4, 15]

関数型の世界だと、 Haskell は scan と呼び、 C++ は partial_sum と呼び、 Clojure は reductions と呼ぶ。 残念なことに、Rubyにはそのような関数が存在しないので、自分で書いてみよう。 以下のようになる。

lengths = ["milu", "rantanplan"].partial_inject(0) do |dog_name|
  dog_name.length
end # => [0, 4, 15]

Enumerable#partial_inject は、以下のように書ける。

module Enumerable
  def partial_inject(initial_value, &block)
    self.inject([initial_value, [initial_value]]) do |(accumulated, output), element|
      new_value = yield(accumulated, element)
      [new_value, output << new_value]
    end[1]
  end
end

実装の詳細は重要ではなく、それよりも、抽象化の興味深いパターンを認識する時には 分離したライブラリ内にコードを書き、文書化し、テストを実施していたことが大切である。 さて、現実のニーズに沿って、(コードの)拡張を洗練させていくことにしよう。

最初の代入 + 条件付き代入 + 条件付き代入 + ...

以下のようなコードはよく見かける。

name = obj1.name
name = obj2.name if !name
name = ask_name if !name

このようなコードを目にすれば、瞬間的に容易ではないと感じるに違いない (変数はこの値を持ち次には別の値を持ち、その変数名はいたるところで繰り返されている)。 関数型アプローチは、より短くより明解だ。

name = obj1.name || obj2.name || ask_name

以下に示すより複合的な条件を伴うもう一つの例は、

def get_best_object(obj1, obj2, obj3)
  return obj1 if obj1.price < 20
  return obj2 if obj2.quality > 3
  obj3
end

以下のような現実の式として書くことができる。

def get_best_object(obj1, obj2, obj3)
  if obj1.price < 20
    obj1
  elsif obj2.quality > 3
    obj2
  else
    obj3
  end
end

実際、わずかに騒がしいけれど、 その論理は後置 if/unless の一味よりもはるかに明解だ。 経験則として、副作用(side-effect)の実行が目的である場合に限れば 後置条件節を使用すべきであるが、変数への代入や(関数の)リターンには当てはまらない。

country = Country.find(1)
country.invade if country.has_oil?
# more code here

列挙オブジェクトからハッシュを生成する方法

ありきたりの Ruby は列挙オブジェクト(Enumerable)から ハッシュ(Hash)への直接的な変換手段を持たない (個人的見解では、悲しい欠陥だ)。 なぜだろうか、初心者は、以下に示すような実にひどいパターンで書き続けている (そして、どうしてそれを非難できよう)。

hash = {}
input.each do |item|
  hash[item] = process(item)
end
hash

これはひどい、ひどすぎる。でも、これの手短な改良には何があるだろうか? 過去にはHashコンストラクタは、 key/value ペアが連続する平坦な配列を必要としていた (げげっ、平坦な配列の写像(map)を記述するのか? Lispなら普通だけど、それでもまだ格好悪いよ)。 幸いにも、最新版の Ruby では、 (hash.to_a の逆演算として)ずっと直感的に key/value のペアを(直に)受け取ることもできるから、 以下のように書ける。

Hash[input.map do |item|
  [item, process(item)]
end]

悪くはないが、自然なコーディングという方向性からはやや外れている。 Ruby ではオブジェクトへのメソッド呼び出しを右から左へと書くことを期待する。 そして「好ましい」関数型の道とは、 inject を使うことである。

input.inject({}) do |hash, item|
  hash.merge(item => process(item))
end

これがまだ騒がしすぎることは誰もが認めるが、 それゆえモジュール Hash 内のメソッドとして (その騒がしいコードを)移動するのが望ましく、 以下に示すように、まさしくそれを Facets で実践している。

module Enumerable
  def mash(&block)
    self.inject({}) do |output, item|
      key, value = block_given? ? yield(item) : item
      output.merge(key => value)
    end
  end
end

["functional", "programming", "rules"].map { |s| [s, s.length] }.mash
# {"rules"=>5, "programming"=>11, "functional"=>10}

あるいは、ブロックを伴う mash を使っても一行で書ける。

["functional", "programming", "rules"].mash { |s| [s, s.length] }
# {"rules"=>5, "programming"=>11, "functional"=>10}

OOPと関数型プログラミング

(Erlang の作者である) Joe Armstrong は、 オブジェクト指向プログラミング(object-oriented programming, OOP)の再利用性について 書籍「Coders at Work プログラミングの技をめぐる探求」の中で 以下のように論じている。

「再利用性の欠落はオブジェクト指向言語では起こるけれど、関数型言語では起きない。 なぜかといえば、オブジェクト指向言語に伴う問題とは、 オブジェクトがオブジェクトを保持するという、 暗黙の環境とやらを得たことに起因するからだ。 あなたはバナナが欲しかったけれど、実際に手にしたのが何かといえば バナナを抱えたゴリラとジャングル全体だった。」

公平を期していえば、個人的見解では、それはOOPの本質的な問題ではない。 関数型でもあるOOPコードを書くことは可能であっても、以下の事柄に間違いは無い。

  • 典型的なOOPは、オブジェクト内部にある状態の変更を強調する傾向がある。

  • 典型的なOOPは、(モジュール化を妨げる)レイヤー間の密結合を強いる傾向がある。

  • 典型的なOOPは、一意性(identity)の概念と状態をごっちゃにする。

  • データとコードの混合は、概念的および実践的な問題の両者を引き起こす。

Closure(JVM向け関数型Lisp方言)の作者である Rich Hickey は、この 洗練された講演 の中で、状態、値、そして一意性について論じている。

あらゆるすべてが式である

以下のコードは間違いではない。

if found_dog == our_dog 
  name = found_dog.name
  message = "We found our dog #{name}!"
else
  message = "No luck"
end

けれども、 (if, while, case といった) 制御構造は式を返すのだから、以下のように正しく書こう。

message = if found_dog == my_dog
  name = found_dog.name
  "We found our dog #{name}!"
else
  "No luck"
end

変数名 message を繰り返さないだけでなく、 コードの一群(そして気にかけなくてもいい他の大量の変数)が大きくなるにつれて、 その意図もよりいっそう明確となり、 何をするのか(メッセージを返す)に精神を集中できる。 式であるというFPコードのもう一つの利点は、以下に示すような データの組み立てにも適用できる。

{
  :name => "M.Cassatt",
  :paintings => paintings.select { |p| p.author == "M.Cassatt" },
  :birth => painters.detect { |p| p.name == "M.Cassatt" }.birth.year,
  ...
}

再帰

明示的な状態を持たない純粋関数型言語は、再帰(recursion)を多用する。

無限スタックを回避するため、関数型言語は 末尾再帰最適化(tail-recursion optimization, TCO)と呼ばれる仕掛けを持つ。 Ruby 1.9 はこの仕掛けを装備しているけれど、デフォルトでは無効化されているから、 もしどこでも動くコードを想定しているなら使用できない。

けれども、たとえスタックが再帰のたびに深くなるとしても、 一定の環境下であれば再帰は有効であり利用可能である。 再帰の用途のいくつかは(Enumerable#inject のような)畳み込みで 達成できることに注目しなさい。

MRI-1.9 で TCO を有効化するには、以下のようになる。

RubyVM::InstructionSequence.compile_option = {
  :tailcall_optimization => true,
  :trace_instruction => false,
}

単純な例を以下に示す。

module Math
  def self.factorial_tco(n, acc=1)
    n < 1 ? acc : factorial_tco(n-1, n*acc)
  end
end

さらには、再帰があまりに深くなりすぎないと見込まれる時にも利用できる。

class Node
  has_many :children, :class_name => "Node"

  def all_children
    self.children.flat_map do |child|
      [child] + child.all_children
    end
  end
end

遅延列挙オブジェクト

貪欲評価(eager evaluation)との対比として、 遅延評価(lazy evaluation)は必要になるまで式の評価を遅らせ、 式がたとえどこで使われていても、変数が代入されたり関数がコールされた等々の時点で 計算される。 遅延はFPにとって必須条件ではないが、関数型パラダイムにうまく適合する戦略である (Haskell は、遅延が言語の全体に行き渡る、おそらく最良の例である)。

基本的に Ruby は貪欲評価を使う (多くの他の言語がそうであるように、到達しなかった 条件分岐や論理演算子 &&, ||, 等々に含まれる式は評価されない)。 けれども、高階関数を伴う言語と同様に、いつブロックが呼ばれるかを プログラマが決定するのだから、遅延評価は明示的にサポートされる。

さらに、Ruby 1.9 からは列挙オブジェクト(enumerator)が利用できるし (1.8 には backports を使いなさい)、 それらは遅延列挙を定義する明解なインターフェイスを提供する。 以下の古典的な例は、すべての自然数を返す計算機を組み立てる。

require 'backports' # needed only for 1.8
natural_numbers = Enumerator.new do |yielder|
  number = 1
  loop do
    yielder.yield number
    number += 1
  end
end

これは、より関数型の精神に乗っ取って書き直すことができる。

natural_numbers = Enumerator.new do |yielder|
  (1..1.0/0).each do |number|
    yielder.yield number
  end
end

>natural_numbers.take(10)
# => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

さて、natural_numbers 上での map を 試すと何が起きるかというと、(map は)決して終了しない。 標準の Enumerable のメソッド(mapselect、等々)は配列を返すのだから、 もし入力が無限ストリームであれば動作しなくなる。 この遅延 Enumerator#map を伴う例題向けに、 Enumerator クラスを拡張してみよう。

class Enumerator
  def map(&block)
    Enumerator.new do |yielder|
      self.each do |value|
        yielder.yield(block.call(value))
      end
    end
  end
end

さて、すべての自然数に関するストリーム上の map は、 以下のように評価できる。

natural_numbers.map { |x| 2*x }.take(10)
# => [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]

列挙オブジェクトは遅延的に振る舞うブロックの構築として優れているが、 すべての列挙メソッドを遅延スタイルで実装したライブラリも利用できる。

https://github.com/yhara/enumerable-lazy
require 'enumerable/lazy'
(1..1.0/0).lazy.map { |x| 2*x }.take(10).to_a
# => [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]

遅延評価の利点

  1. 明白な利点: もしも(CPU、メモリ、あるいは両者の効率化のために)不要であれば、 完全なデータ構造を組立てたり格納したりする必要が無い。

  2. それほど明白ではない利点: 遅延評価は、 必要であることに無関心な(無関心でもかまわない)コード設計を可能にする。 無限数の問題を解くコードを何種類か書いてみたが、場合によっては 最初の10個だけが欲しいこともあるという例題を見てみよう。 (一般には)以下と類似したコードを書く。

    solver(input, :max => 10)

    遅延データ構造を使えば、いつ停止するかを(パラメタで)指定する必要は無い。 いくつ値が欲しいかは、コール元が決定する。 コードはより単純となり、責務の所在はコール元へと移る。

    solver(input).take(10)
    		

実践的な例題

演習問題: 「二乗して5で割り切れる自然数について、最初の10個の合計はいくつ?」

Integer::natural.select { |x| x**2 % 5 == 0 }.take(10).inject(:+) # => 275

同等な命令型バージョンと比較してみよう。

n, num_elements, sum = 1, 0, 0
while num_elements < 10
  if n**2 % 5 == 0
    sum += n
    num_elements += 1
  end
  n += 1
end
sum # => 275
この例題が、以下に示す、本文書で論じた利点のいくつかを示しているものと期待する。

簡潔さ:

より短いコードで書けるようになる。 関数型コードは式を扱い、式は連鎖(チェーン)できる。 命令型コードは変数の更新(文)を扱い、それらは連鎖できない。

抽象化:

select, inject, ...等を 使えば多くのコードの隠蔽が達成できるし、 やりたい事が明確になるのだから、その導入は喜ばしいと考える。 抽象化の設計における隠蔽の一般化やコードの再利用可能化は、 あらゆるプログラミングで、 とりわけ関数型プログラミングではあちこちで見かけられる。 (単なる)コード行数の短さではなく、 再利用可能なパターンを認識することによって コードの複雑さを縮小できることが幸せをもたらす。

より宣言的に:

命令型バージョンは、(コメントが無ければ)一目では 何がしたいのかまったく想像できない、漠然としたコードの一群に見える。 「よろしい、では始めようか、nsum の値をさらっと書いて、何回かループさせて、どれだけ増えたか確認して、 最後の反復結果見て、うんぬん」と語るだろう。 それに対して、関数型バージョンは自己解説的であり、どのように行うかではなく 何を行うかを記述し宣言する。

「関数型プログラミングは、数学者が問題を記述するのと似ている。 命令型プログラミングは、まぬけが命令を与えられているのと似ている。」 (IRCチャンネル #scheme on Freenode における arcus の発言)

おわりに

関数型プログラミングの原理をより正しく理解することは、 より明解で、再利用可能で、かつ簡潔なコードを書く助けになるだろう。 Rubyは基本的には命令型言語であるけれど、 関数型プログラミングへの際立った潜在能力があるのだから、 それらをいつどのように使うか(そして、いつ使わないか)を知っておくべきである。 「状態はあらゆる悪の根源である(State is the root of all evil)」を座右の銘とし、 その利用はできる限り避けるようにしなさい。

プレゼンテーション

興味を持った読者へ

http://en.wikipedia.org/wiki/Functional_programming
http://www.defmacro.org/ramblings/fp.html
http://www.cse.chalmers.se/~rjmh/Papers/whyfp.html
http://www.khelll.com/blog/ruby/ruby-and-functional-programming/
http://www.bestechvideos.com/2008/11/30/rubyconf-2008-better-ruby-through-functional-programming
http://channel9.msdn.com/Blogs/pdc2008/TL11
http://www.infoq.com/programlistingsentations/Value-Identity-State-Rich-Hickey