左結合な減法，つまり「1-2-3」は「(1-2)-3」であって「1-(2-3)」ではない，ということを解決する方策をHigher-order Perlの8.4節からもらってきます．左結合を実現するのに，単純に expression : expression "-" atomとしてしまうと，expressionを処理する…

単純な足し算だけに続いて，引き算もしたいということで，単純に拡張します． use strict; use warnings; use Parse::RecDescent; my $grammar=q( expression : atom "+" expression { $return = $item[1] + $item[3] ;} #引き算を追加 expression : atom "-…

仕事でどうにもparserを書かないといけなくなるような気がしてます．なんかXMLへの変換とかさせられそうな雰囲気をびしびし．LaTEX2HTMLもそのための伏線．ということで，Parse::RecDescentも考えよう．HaskellのParsecだとマニアックすぎてだめかもしれない…

Higher-Order Perl（以下HOP）の8.2節の文法をさらにシンプルにして「足し算のみ」を考えます．足し算の文法として以下のものを考えます． expression -> atom + expression | atom atom -> /\d+/ なんか，いろいろなものをチャンポンにした表記ですが，表記…

やっぱりお馬鹿してたわけで，pushを使えば十分な速さでした． use strict; use warnings; use Time::HiRes qw/gettimeofday tv_interval/; my $x=primefactory2(); my $sum; my $start = [gettimeofday]; while (1){ my $p=$x->(); last if $p>2000000; $su…

「mod 6で1か5」を探索する方法でいってみます． use Benchmark; $x=primefactory2(); $count=5000; timethese($count, {'p1' => '$x->();', } ); sub next_cand{ $_[0] + 2 * ($_[0] % 6 ==5) + 4*($_[0] % 6 ==1); } sub primefactory2{ my @primes=(2,3,5…

キーボードが小さくなって誤入力倍増キャンペーン開催中． ##単純なエラトステネスの篩 use Benchmark; $x=primefactory1(); $count=5000; $i=0; timethese($count, {'p1' => '$x->();', } ); sub primefactory1{ my @primes=(2,3); my $state=-1; return su…

素数を列挙するは最適化の罠にはまったようです．ただいま原因の探求中（正しくは「自分の納得させる」作業中）． すくなくとも「探索範囲を縮小するための処理のコスト」が「縮小による効果」を大幅に上回ったのは間違いないでしょう（grepは遅いということ…

Haskellだと遅延評価で素数列に限らず「無限列なんでも来い」ですが，Perlだとどうなるでしょう．ここはMJD師匠（勝手に師匠よばわり）のHigher-Order Perlに助けを求めます．Perlでの「遅延評価」はコードリファレンス（サブルーチンへのリファレンス）とク…

リストの連結で，同じリストを連結させようとすると循環することに気がつきました．ということで，複製処理を追加です．さらに第一引数のリストを破壊してしまうことにも気がついたので修正です． sub Lconcat{ my $a=shift; my $b=shift; $b=Lduplicate($a)…

sub Llength{#長さ my $l=shift; my $len=0; return 0 unless Lhead($l); return Llength(Ltail($l))+1; } sub Lduplicate{#複製 my $l=shift; return [Lhead($l),undef] unless Ltail($l); return [Lhead($l),Lduplicate(Ltail($l))]; } sub Llast{#最後の…

Lmap/filterの第一引数には sub を省略した無名サブルーチンを使えますが，そのサブルーチンの引数は一個で，$_[0] を使います．一方，Perlの組み込みのmap/grepでは，デフォルトの $_ を使います．そこで，Lmap/filterでも同じように $_ に変更してみます．…

mapの次はgrep．名前をfilterにします． sub filter(&$){ my ($f,$l) = @_; return unless $l; my $temp=head($l); if ($f->($temp)){ node($temp, &filter($f,tail($l))); }else{ &filter($f,tail($l)); } } filterはリンクトリストのノードを一個一個たど…

sub Lmap(&$){ my ($f, $l) = @_; return unless $l; node ($f->(head($l)), Lmap($f, tail($l)) ); } listのmapということで，Lmapとしました．Higher-Order Perlでは，transformという名前になっていますが，mapの方が短いので(^^;．これを実行してみると …

二つの有限リンクトリストを連結してみます．つまり， $list1= [ 1, [ 2, [ 3, undef] ] ]; $list2= [ 10, [20, [30, undef] ] ]; から $list = [ 1, [ 2, [ 3, [ 10, [20, [30, undef] ] ] ] ] ]; を作る操作です． sub concat{ my ($a,$b)=@_; my $c = $a;…

HOP（Higher-Order Perl）にしたがって，リンクトリスト*1を考えます．HOPでいうところのリンクトリストは，それらしく書くと以下のものです． linked_list = node node | [ head, tail ] | [ head, undef] tail = node 言葉でいうと次のどちらかが成り立つ…

毎回手動で作っていては大変なので，規則に応じて自動的にリンクトリストを生成することを考えます．基本となるのは次の関数です． sub node{ my ($head, $tail)=@_; return [$head, $tail]; } ノードの要素と次の要素へのポインタ（ここでは無名配列）を与…

また，HOPに戻って考えてみます．Perlでのリンクトリストを考えるときに，一番自然なのは，ノードとポインタからなる要素が二つの無名の配列を使うことだと思います． $N1 = [ Node 1, $N2へのリファレンス] $N2 = [ Node 2, $N3へのリファレンス] .... とい…

キャッシュを使ったフィボナッチをもう一段抽象化してみます．初期値は引数にできますし，無名サブルーチンを使えば，漸化式そのものも引数にすることができます． use strict; use warnings; no warnings 'recursion'; use bigint; {my %cache; sub receq{ …

キャッシュとかいっても計算した値を保存しておくというだけです．Perlの場合，ハッシュで保存するのが楽です．第項を計算したら，その結果ををキーとするハッシュの値として保存しておくだけです．このハッシュをグローバル変数にしてしまっても構わないの…

単純な再帰でフィボナッチを計算させると，とても時間がかかります． my $count; sub fib1{ my $n = shift; $count++; return 0 if $n==0; return 1 if $n==1; return fib1($n-1)+fib1($n-2); } なんてすれば，fib1が何回呼ばれるか数えることもできますが，…

フィボナッチ数列というのは，大抵のプログラムの本，それも再帰を扱っているものなら，まず出ているといってもよいほどの，人気者です．高校の数学の本にもまずでています．出ていなかった，きっと著者がフィボナッチが嫌いか，ウサギが嫌いなのに違いあり…