2007年05月26日 18:30 [Edit]

perl - Tie::Array::Lazy

camel

この点で妥協する、ということであれば、実装はそれほど難しくないはず。

Matzにっき
「長さが決まってないArrayがありえるのか」というツッコミもあるだろう。 が、queueやらstackやらとしての機能までも備える「大クラス主義」のRubyのArrayである。 ある時点でサイズが決まっていないなど些細なことではないだろうか。 アクセスがO(1)である点も、「値が確定している範囲内ではO(1)」で十分だと考える。

と、思って作ったら、簡単にできちゃいました。


demo.pl
use 'Tie::Array::Lazy';
use Data::Dumper;
local $Data::Dumper::Terse  = 1;
local $Data::Dumper::Indent = 0;
local $\                    = "\n";    # to make print() say()
local $,                    = ", ";    # autojoin with ", "
tie my @a, 'Tie::Array::Lazy', [], sub { $_[0]->curr ** 2 };
print $a[10];
print Dumper( tied @a );
print splice( @a, 5, 10, qw/foo bar baz/ );
print Dumper( tied @a );
print for (@a);

単にLazyなだけではなく、Arrayである証拠にちゃんとsplice()とかも出来ます。

% perl demo.pl | head -25
100
bless( {'next' => sub { "DUMMY" },'seed' => [0,1,4,9,16,25,36,49,64,81,100,121]}, 'Tie::Array::Lazy' )
25, 36, 49, 64, 81, 100, 121, 144, 169, 196
bless( {'next' => sub { "DUMMY" },'seed' => [0,1,4,9,16,'foo','bar','baz',64,81,100,121,144,169,196,225]}, 'Tie::Array::Lazy' )
0
1
4
9
16
foo
bar
baz
64
81
100
121
144
169
196
225
256
289
324
361
400

実装も、至ってシンプル。

package Tie::Array::Lazy;
use warnings;
use strict;
our $VERSION = '0.01';

use base 'Tie::Array';
use Carp;

sub DESTROY { }

sub TIEARRAY {
    my ( $pkg, $seed, $next ) = @_;
    croak "$seed must be anarray ref"
      unless UNIVERSAL::isa( $seed, 'ARRAY' );
    croak "$next must be a code ref"
      unless UNIVERSAL::isa( $next, 'CODE' );
    bless { seed => $seed, next => $next }, $pkg;
}

sub seed { $_[0]->{seed} }
sub curr { scalar @{ $_[0]->{seed} } }
sub next { $_[0]->{next} }

sub EXTEND($$) {
    my ( $self, $size ) = @_;
    my $seed = $self->seed;
    my $tail = @$seed;
    return unless $tail < $size;
    for ( $tail .. $size ) {
        my $value = $self->next->($self);
        push @{$seed}, $value;
    }
}

sub FETCH($$) {
    my ( $self, $index ) = @_;
    $self->EXTEND( $index + 1 );
    $self->seed->[$index];
}

sub STORE($$$) {
    my ( $self, $index, $value ) = @_;
    $self->EXTEND($index);
    $self->seed->[$index] = $value;
}

sub STORESIZE($) { }

sub FETCHSIZE($) { scalar @{ $_[0]->seed } + 1 }
1;

要はLazy Arrayに「本当の」ArrayとGeneratorを持たせておき、足りない要素をGeneratorで生成して埋める、というわけです。

Generatorの引数は、ここではtied objectそのものにしています。$self->seedで「本当の」ArrayへのReferenceに、$self->nextでGeneratorのcode referenceに、$self->currでArrayの要素数にそれぞれアクセスできます。

みんなが大好きなフィボナッチ数も、この通り。

tie my @fib, 'Tie::Array::Lazy', 
    [ 1, 1 ], 
    sub { $_[0]->seed->[-2] + $_[0]->seed->[-1] };

FizzBuzzは読者におまかせします。

Rubyでの実装は、Perl以上に簡単だと思われますが、それはRubyistsにおまかせします。

Enjoy!

Dan the Lazy Evaluator


この記事へのトラックバックURL

この記事へのトラックバック
というわけで、Tie::Array::LazyをCPANizeしたのでお知らせします。 .cpan { list-style-image: url(http://search.cpan.org/favicon.ico) } on CPAN (coming soon) http://www.dan.co.jp/~dankogai/cpan/Tie-Array-Lazy-0.01.tar.gz
CPAN - Tie::Array::Lazy 0.01 released!【404 Blog Not Found】at 2007年05月27日 03:24