perlでのコレクション操作 (後編)

はじめに

去年の perlでのコレクション操作 (前編) - Qiita の続きになります。
今回の内容はコレクションに関連した実験と試作を含みます。perl v5.20環境で動作確認していますが、正確性を保証するものではありませんので、参考にされる場合はご注意ください。
なお、本記事では、「コレクション」を「配列(リスト)っぽいデータ構造」全般を指す言葉として使っています。

要約

• ARRAYベースのコレクションオブジェクトは便利!
  • 両方OK
    • オブジェクト的な操作 (例: $c->uniq->sort)
    • 配列/リスト的な操作 (例: $c->[0], push(@$c, 10), for (@$c) {})
• さらに、tieした配列をコレクションに使うともっと便利！!（かも)
  • 配列要素データ以外の情報を隠し持つことができる
  • → 状態やキャッシュなどに利用
  • → HASHベースコレクションと同等の拡張性

本記事で可能になる便利な使い方

# コレクションを作る
use MyCollection;
my $c = MyCollection->new(1, 2, 3);

# 合計を計算するsum()メソッドは結果をキャッシュし、
# コレクションに変更がなければ 2回目以降はキャッシュが利用される
say $c->sum;  # -> 6
say $c->sum;  # -> 6 (キャッシュ利用)

# オブジェクト的な操作ができる
$c->uniq->reverse->join(',');

# 伝統的な配列/リスト操作も可能
push @$c, 4;

# (要素が更新され、合計キャッシュはクリアされている) 合計が再計算される
say $c->sum;  # -> 10

ARRAYベースコレクションの利点

前回は perl標準のリストの操作と、いくつかのコレクションライブラリについて説明しました。

特にARRAYベースのコレクションは、コレクションオブジェクトとしての便利メソッドが利用できることに加え、通常の配列と同じような操作ができるため、伝統的なperlのリスト操作を行うロジックとの親和性も兼ね備えていると言えるでしょう。

例：コレクションメソッドと伝統的リスト操作の混在

use Mojo::Collection qw(c);

# コレクションオブジェクト生成
my $c = c(1, 2, 3);

# 通常のリストとして操作
$c->[0] ++;
push @$c, 1;

# コレクションメソッドとして操作
say $c->sort->uniq->join(',');

一般的なARRAYベースコレクションの課題

ARRAYベースコレクションは、元になる配列をそのままオブジェクト化しますので、持っているデータとしては元の配列そのものです。
逆に言えば、その他の情報を持たせることができないので、各種状態やキャッシュを利用したオブジェクトを表現することができません。

例題

例えば、ゲームの得点を格納してその合計値を求めたい場合を考えます。

伝統的なリスト操作での実装イメージは以下です。

伝統的リスト操作で合計点を算出

# 得点リスト (配列)
my @scores = (1, 2, 3);

# forループで各要素を加算
my $sum = 0;
$sum += $_ for (@scores);

これをコレクションを利用すると以下の実装イメージです。

コレクションで合計点を算出

use Mojo::Collection qw(c);

# 得点リスト (コレクション)
my $scores = c(1, 2, 3);

# 畳み込みで各要素を加算
my $sum = $scores->reduce(sub { $a + $b }, 0);

以下のように、コレクションクラスを継承したカスタムコレクションクラスを作成して、合計算出をメソッド化してみます。

カスタムコレクションクラス MyCollection.pm

package MyCollection;
use Mojo::Base 'Mojo::Collection';

# 合計
sub sum {
    say '計算中...';
    return shift->reduce(sub { $a + $b }, 0)
}

1;

先程の合計メソッドを持ったカスタムコレクションクラスを使うイメージは以下です。
確かに合計は算出できるのですが、単純な実装なのでコレクションに変更が無くてもsumメソッドをコールするたびに何度も計算処理が実行されてしまいます。

カスタムコレクションクラスを利用して合計算出＠pry

0> use MyCollection
1> my $c = MyCollection->new(1, 2, 3);

# 合計を取得できる
2> $c->sum
計算中...
$res[1] = 6

# コレクションに変更が無いが、2回目も再計算されてしまう
3> $c->sum
計算中...
$res[2] = 6

課題まとめ

先の例では、

• 毎回、合計を計算してしまう
• 合計値をキャッシュしておき、コレクションの要素に変更がない限りキャッシュを活用したい
• しかし、シンプルなARRAYベースコレクションの実装では、要素情報以外の状態やキャッシュを持てない
• どこかに追加情報を隠しておきたいのですが。。。

アプローチ

課題解決の一つのアプローチとして tie を利用した仕組みを考えてみます。

tieの仕組み

tie とは、スカラ、配列、ハッシュなどの変数に対して、操作用のメソッド群を実装したオブジェクトを結びつける仕組みで、実際のデータはtieされたオブジェクト内に持ちます。以下のイメージです。

以下はtieで配列変数にオブジェクトを結びつけたコード例です。
tieされたオブジェクトは tied()関数でいつでも取り出せます。

tieで配列変数にオブジェクトを結びつけたコード例@pry

# Tie::Array に同梱のTie::StdArrayを使ってみる
0> use Tie::Array;

# Tie::StdArray型のオブジェクト($t)を作成し、@arrayに紐付ける
1> my $t = tie my @array, 'Tie::StdArray';
$res[0] = Tie::StdArray  {
    Parents       Tie::Array
    public methods (13) : CLEAR, DELETE, EXISTS, FETCH, FETCHSIZE, POP, PUSH, SHIFT, SPLICE, STORE, STORESIZE, TIEARRAY, UNSHIFT
    private methods (0)
    internals: []
}

# 配列操作してみる
2> push @array, (1, 2, 3);
$res[1] = 3

# tied()で紐付けられたオブジェクトを取得し($tと同じ)、中を見ると実データが変わっている
3> tied @array
$res[2] = Tie::StdArray  {
    Parents       Tie::Array
    public methods (13) : CLEAR, DELETE, EXISTS, FETCH, FETCHSIZE, POP, PUSH, SHIFT, SPLICE, STORE, STORESIZE, TIEARRAY, UNSHIFT
    private methods (0)
    internals: [
        [0] 1,
        [1] 2,
        [2] 3
    ]
}

tieした配列を内包したコレクション

このtieを利用して、配列データと追加情報をまとめたHASHベースのオブジェクトを内包したオブジェクトに配列を結びつけ(tie)、結び付けられた配列を内包するARRAYベースのコレクションオブジェクトを作れば、状態やキャッシュなどを隠し情報として持つことができそうです。
イメージは以下。

実装

PoCのために実装してみます。

ハッシュベースの配列Tie基本クラス

Tie::Array を継承して、ハッシュベースの配列を持つTie基本クラスを実装します。
中身は Tie::StdArray を踏襲してつくっています。
tieのためにnew()メソッドは必須ではありませんが、これをさらに継承したりする際の利便性や統一感のためにnewを実装しています。

Tie/Array/HashWrapedArray.pm

package Tie::Array::HashWrapedArray;
use Tie::Array;
our @ISA = 'Tie::Array';

sub array { $_[0]->{array} }

sub new {
    my $class = shift;
    my %hash = (scalar(@_) == 1) ? %{$_[0]} : @_;
    $hash{array} //= [];
    bless \%hash, $class;
}

sub TIEARRAY   { my $o = shift; $o->new(@_) }

sub FETCHSIZE { scalar @{$_[0]->array} }
sub STORESIZE { $#{$_[0]->array} = $_[1] - 1 }
sub STORE     { $_[0]->array->[$_[1]] = $_[2] }
sub FETCH     { $_[0]->array->[$_[1]] }
sub CLEAR     { @{$_[0]->array} = () }
sub POP       { pop(@{$_[0]->array}) }
sub PUSH      { my $o = shift; push(@{$o->array}, @_) }
sub SHIFT     { shift(@{$_[0]->array}) }
sub UNSHIFT   { my $o = shift; unshift(@{$o->array}, @_) }
sub EXISTS    { exists $_[0]->array->[$_[1]] }
sub DELETE    { delete $_[0]->array->[$_[1]] }

sub SPLICE {
    my $ob  = shift;
    my $sz  = $ob->FETCHSIZE;
    my $off = @_ ? shift : 0;
    $off   += $sz if $off < 0;
    my $len = @_ ? shift : $sz - $off;
    return splice(@{$ob->array}, $off, $len, @_);
}

1;

合計機能をもった配列Tieクラス

遅延評価され、値のキャッシュもする合計取得処理を実装します。
手抜きするために Moo を利用します。

MyApp/TieArrayWithSum.pm

package MyApp::TieArrayWithSum;
use Moo;
extends 'Tie::Array::HashWrapedArray';

# 合計 (遅延評価、ReadOnly)
has sum => (is => 'lazy', clearer => 1);

# 配列の変更操作の際に合計キャッシュをクリア
before [qw(STORESIZE STORE CLEAR POP PUSH SHIFT UNSHIFT DELETE SPLICE)] => sub { shift->clear_sum() };

# 合計を算出する
sub _build_sum {
    my $self = shift;
    say '計算中...';
    my $sum = 0;
    $sum += $_ for (@{$self->array});
    return $sum;
}

1;

合計機能付き配列のテスト

これで、合計機能をもった配列を作ることができました。

合計機能付き配列のテスト@pry

# 初期値[1, 2, 3]を与えてtie配列変数を作成する
0> use MyApp::TieArrayWithSum
1> my $t = tie my @array, 'MyApp::TieArrayWithSum', { array => [1, 2, 3] }

# 合計を取得
2> $t->sum
計算中...
$res[1] = 6

# 再度、合計を参照してもキャッシュが利用されて再計算されない
3> $t->sum
$res[2] = 6

# 配列に要素を追加してみる (キャッシュがクリアされる)
4> push @array, 4
$res[3] = 4

# 再度、合計を参照すると再計算される
5> $t->sum
計算中...
$res[4] = 10

Tie配列を内包するコレクションの基本クラス

次に、Tie配列を内包するコレクションの基本クラスを作ります。
手抜きするために Mojo::Collection を継承します。

Mojo/Collection/Tie.pm

package Mojo::Collection::Tie;
use Mojo::Base 'Mojo::Collection';

# デフォルトのtieクラス名
sub TIE_CLASS {'Tie::Array::HashWrapedArray'}

sub new {
    my $class = shift;
    tie my @array, $class->TIE_CLASS, { array => [@_] };
    return bless \@array, ref $class || $class;
}

# tieされたオブジェクトの参照
sub tied { tied(@{$_[0]}) }

1;

合計機能付き配列を扱いやすくするコレクション

合計機能付き配列そのままでは使いづらいので、コレクションクラスを作成します。
Tieクラス名を指定し、Tieオブジェクトのsum(合計)にアクセスするためのメソッドを同名で作っておきます。

package MyCollection;
use Mojo::Base 'Mojo::Collection::Tie';

# tieクラス名
sub TIE_CLASS {'MyApp::TieArrayWithSum'}

# 合計
sub sum { shift->tied->sum }

1;

検証

さて、合計機能付きコレクション MyCollection を使ってみましょう。

検証

0> use MyCollection
1> my $c = MyCollection->new(1, 2, 3)
$res[0] = MyCollection  {
    Parents       Mojo::Collection::Tie
    public methods (3) : has, sum, TIE_CLASS
    private methods (0)
    internals: [
        [0] 1,
        [1] 2,
        [2] 3
    ] (tied to MyApp::TieArrayWithSum)
}

# 合計を取得
2> $c->sum
計算中...
$res[1] = 6

# 再度、合計を参照 (キャッシュされている)
3> $c->sum
$res[2] = 6

# Mojo::Collection由来の便利メソッドも使える
4> $c->reverse
$res[3] = MyCollection  {
    Parents       Mojo::Collection::Tie
    public methods (3) : has, sum, TIE_CLASS
    private methods (0)
    internals: [
        [0] 3,
        [1] 2,
        [2] 1
    ] (tied to MyApp::TieArrayWithSum)
}

# 伝統的なリスト(配列)操作も可能
5> push @$c, 4
$res[4] = 4

# 要素を更新したので、合計キャッシュはクリアされ、合計が再計算される
6> $c->sum
計算中...
$res[5] = 10

伝統的なリスト(配列)的操作も、オブジェクトとしてのメソッド操作もどちらも可能で
しかも、キャッシュが効いてる！

考察

tieした配列を利用することで、配列ベースのコレクションは状態やキャッシュなどの追加情報を保持できそうです。
とはいえ、試作での検証レベルですので、何らかの制約がある可能性やパフォーマンスの問題などは考えられます。
同アプローチや類似の手法を採用した仕組みや既存ライブラリ、また、関連した問題点など、情報ありましたら共有いただけると幸いです。

その他、いくつか気がついたことを列記します。

• この方式で、何かしらの制約がないか？
• パフォーマンス面
• new時のI/F
  • 検証では Mojo::Collectionをベースにした
    • Mojo::Collectionを始め人気のあるコレクションライブラリはnewの際に要素を(リファレンスではない)リストのコピーで受け渡している
    • mapやfilterなど多くのメソッドは新しいコレクションオブジェクトを生成する際に、配列の要素情報だけのリストを元に生成される
  • →状態・キャッシュなどのコンテキスト情報をそのまま流用・受け渡しができない
  • →遅延評価状態をchainさせる、キャッシュを流用するなどの応用がしづらい
  • →キレイに実装するなら、newする際のI/FをHASHベースに変更する必要がある
• mapなどで返すコレクションの型を変更したい、要素の型に応じた振る舞いをさせてたい、などの応用

終わりに

本当は去年書こうと思っていたネタでしたが、何だかんだあって、1年後になってしまいました。。。
指摘、情報共有などいただけると幸いです。
良い年末を！