Linkers Tech Blog

リンカーズ株式会社の開発者ブログです。

Rubyのパターンマッチで再帰関数

Ruby

はじめに

こんにちは、情報システム部サービス開発チームの金です。

Rubyのパターンマッチ機能、皆さんは使っていますか？
Ruby2.7の実験的(experimental)新機能として発表されて久しいですが、Ruby3.0では一部についてexperimentalの警告が出なくなり、その後も新構文が続々と追加されています。
RailsでもActive Modelにパターンマッチを使えるようにするPRがマージされたりと、これから使う機会が増えそうな機能です。

...が、私はまだ使ったことがありません。

何かを覚えるには実際に手を動かすのが一番ですよね。
聞くところによると、「パターンマッチ」は「再帰関数」と相性が良いそうです。確かに、いつかHaskellを学んだ際はこの２つのワードが頻出していました。
そこで、本記事では「パターンマッチを使った再帰関数」をRubyで書いてみることにします。

バージョン

Ruby 3.1.2で動作確認しています

前提知識

再帰関数とパターンマッチのうち、この記事で扱っている部分についてざっくり説明します。
そんなの知ってるよ、という方は飛ばしていただいて構いません。

再帰関数

関数が内部で自分自身を呼び出しているなら、その関数は再帰関数と呼べます。
終了条件を正しく記述しないと、無限に自分自身を呼び出してしまうので注意が必要です。

def stack_overflow
  stack_overflow
end

stack_overflow
# stack level too deep (SystemStackError)

また、再帰関数はスタック領域を大量に消費することがあるため、何も考えずに書くとメモリ消費が大きくなりやすいです。
(本記事ではメモ化等による処理の最適化は行わず、パターンマッチと再帰関数に慣れ親しむことを目的にします。)

パターンマッチ

Rubyのパターンマッチではオブジェクトとパターンを比較します。
オブジェクトがあるパターンにマッチした場合、何らかの処理を行う、ということになります。

まずは単純な例から見てみます。

case [100, 'hello']
in [Integer, Integer]
  'どちらもIntegerです'
in [String, String]
  'どちらもStringrです'
in [Integer, String]
  'IntegerとStringです'
end
#=> "IntegerとStringです"

[100, 'hello']は[Integer, String]というパターンにマッチした、ということがわかります。

また、オブジェクトの構造をパターンとして記述することも可能です。

case [1, [3], 5]
in [[x], y, z]
  'パターンA'
in [x, [y], z]
  'パターンB'
in [x, y, [z]]
  'パターンC'
end
#=> "パターンB"

[1, [3], 5]が[x, [y], z]という構造にマッチしたことがわかるかと思います。

実は、上記の例ではパターンマッチで構造を解析しつつ、変数に束縛するという事が行われています。

case [1, [3], 5]
in [[x], y, z]
  x * y * z
in [x, [y], z]
  x + y + z
in [x, y, [z]]
  x - y - z
end
#=> 9

1 + 3 + 5が計算されていますね。

また、*を使うと配列のその他の要素を束縛することも出来ます。

case [1, 2, 3, 4, 5]
in [head, *rest]
  # headには1が、restには[2, 3, 4, 5]が束縛される
  rest << head
end
#=> [2, 3, 4, 5, 1]

つまり、パターンマッチを使うと

  • オブジェクトの構造を解析しながら変数に値を束縛する
  • 束縛した値を用いて処理を行う

ことが可能になります。
この特性を生かして再帰関数を定義してみます。

１つ目の再帰関数

Array#reverse_rec

手始めに、Array#reverseを再帰関数として定義してみたいと思います。
再帰的なのでreverse_rec(recursive)と名付けることにします。
Array#reverse_recは、自身の要素を逆順に並べた新しい配列を生成して返すメソッドです。

class Array
  def reverse_rec
    case self
    in []
      []
    in [head, *rest]
      rest.reverse_rec << head
    end
  end
end

[1, 2, 3].reverse #=> [3, 2, 1]
[1].reverse #=> [1]
[].reverse #=> []

[1, 2, 3].reverse_rec #=> [3, 2, 1]
[1].reverse_rec #=> [1]
[].reverse_rec #=> []

問題なく動いているようですね。

in []
  []

の部分では[].reverse_recが[]であると定義しています。
[]の逆は[]であるという、ある意味当たり前の部分を基底部といいます。再帰呼び出しが最終的にたどり着く部分です。

in [head, *rest]
  rest.reverse_rec << head
end

の部分では、自分自身が再帰的に呼ばれています。こちらを再帰部といいます。
もとの配列をheadとrestに分解した時、restを逆にしたものの後ろにheadを付け加えればもとの配列の逆が得られる、ということになりますよね。

[1, 2, 3].reverse_rec
[2, 3].reverse_rec << 1
[3].reverse_rec << 2 << 1
[].reverse_rec << 3 << 2 << 1
[] << 3 << 2 << 1
#=> [3, 2, 1]

ちなみに、もとの配列を[head, *rest]ではなく[*rest, tail]と分解する方法でも考えてみました。

class Array
  def reverse_rec_tail
    case self
    in []
      []
    in [*rest, tail]
      [tail] + rest.reverse_rec_tail
    end
  end
end

この場合は以下のような動きになります。

[1, 2, 3].reverse_rec_tail
[3] + [1, 2].reverse_rec_tail
[3] + [2] + [1].reverse_rec_tail
[3] + [2] + [1] + [].reverse_rec_tail
[3] + [2] + [1] + []
#=> [3, 2, 1]

パターンマッチの特徴である、構造を解析しながら変数に値を束縛する機能 がうまく再帰関数の一部として働くことが分かりました。

また、そのためには基底部と再帰部の定義が必要だということがわかりました。

さらに再帰関数

同じ方法でいくつか再帰関数を定義してみます。頭の中で再帰処理を展開しながらご覧ください。

Array#max_rec

Array#max_recは、配列のうち最大の要素を返すArray#maxのようなメソッドです。

class Array
  def max_rec
    case self
    in []
      nil
    in [n]
      n
    in [head, *rest]
      head > rest.max_rec ? head : rest.max_rec
    end
  end
end

[20, 800, 3].max #=> 800
[20].max #=> 20
[].max #=> nil

[20, 800, 3].max_rec #=> 800
[20].max_rec #=> 20
[].max_rec #=> nil

基底部は

  • []の最大値はnil
  • [n]の最大値はn

再帰部は

  • [head, *rest]の最大値は、headとrestの最大値のうち大きい方

となります。

Array#take_rec

Array#take_recは配列の先頭から n 要素(nは0以上)を配列として返すArray#takeのようなメソッドです。

class Array
  def take_rec(n)
    raise ArgumentError if n.negative?

    case [self, n]
    in [_, 0] | [[], _]
      []
    in [[head, *rest], n]
      [head] + rest.take_rec(n - 1)
    end
  end
end

[1, 2, 3].take(2) #=> [1, 2]
[1, 2, 3].take(0) #=> []
[].take(2) #=> []

[1, 2, 3].take_rec(2) #=> [1, 2]
[1, 2, 3].take_rec(0) #=> []
[].take_rec(2) #=> []

基底部は

  • 引数が0であればselfが何であろうと[]
  • selfが[]であれば引数が何であろうと[]
    • [_, 0] | [[], _]で２つのパターンを併記しています

再帰部は

  • [head, *rest]からn個取得した配列は、headを先頭とした配列に、restからn-1個取り出して付け加えたもの

となります。

Array#any_rec?

Array#any_rec?は、ブロックの評価が真である要素があればtrueを返すArray#any?のようなメソッドです。

class Array
  def any_rec?(&block)
    case self
    in []
      false
    in [head, *rest]
      !!block.call(head) || rest.any_rec?(&block)
    end
  end
end

[1, 2, 3].any?(&:negative?) #=> false
[1, -2, 3].any?(&:negative?) #=> true

[1, 2, 3].any_rec?(&:negative?) #=> false
[1, -2, 3].any_rec?(&:negative?) #=> true

基底部は

  • selfが[]であれば必ずfalse

再帰部は

  • [head, :rest].any_rec?(&block)は、headにblockを適用した結果とrest.any_rec?(&block)の論理和

となります。

おわりに

普段目にするメソッドを再帰的な目線から見直してみるのは、なかなか楽しい作業でした。
パターンマッチとも少し仲良くなれた気がします。
プログラミングの世界には木構造をはじめ様々な構造が存在するので、構造を解析しながら変数に値を束縛するというパターンマッチの特性と再帰関数を組み合わせれば、色々な可能性が見つかりそうです。

今回はRubyのパターンマッチの中でも配列を使ったArray Patternのみ扱いましたが、他にも様々なパターンの記法があります。
みなさんもパターンマッチや再帰関数で遊んでみてはいかがでしょうか。

参考資料