haskellでフィボナッチそしてPerlで書いてみた

10 08 2006 perl Haskell Tweet

haskellでフィボナッチそしてPerlで書いてみた

普通のhaskellプログラミングを読み終えて、なんか次に読むものないかなと探していたら、webarchiveに面白そうなページがあることを知ったので、ダウンロードして読んでます。

3回目の講義資料に、タプルを使って高速にフィボナッチ数を計算する話があったので、なんでそうなるのかを理解するために手で書き下してみた。

普通に書くとこんな感じ(fib)。

fact :: Int -> Int
fact n
  | n == 0  = 1
  | n > 0   = fact (n-1) * n

書き下すと、計算量があっという間に増えていくことがわかる。

fib 5
=> fib 3 + fib 4
=> (fib 1 + fib 2) + (fib 2 + fib 3)
=> (fib1 + (fib 0 + fib 1)) + ((fib 0 + fib 1) + (fib 1 + fib 2))
=> (fib1 + (fib 0 + fib 1)) + ((fib 0 + fib 1) + (fib 1 + (fib 0 + fib 1)))

タプルを使った例(fastfib)

フィボナッチ数列を効率良く計算する方法を考えよう．前に見たとおり，フィボナッチ数列の各項は，その前の二つの項の和である．逆に言えば，二つの連続した項の値が与えられれば，次の項を計算するのは簡単なのだ．

fibStep :: (Int, Int) -> (Int, Int)
fibStep (u, v) = (v, u+v)

fibPair :: Int -> (Int, Int)
fibPair n
  | n == 0    = (0, 1)
  | otherwise = fibStep (fibPair (n-1))

fastFib :: Int -> Int
fastFib = fst . fibPair

コードを眺めただけではなんで速くなるのか実感がわかなかったので、書き下してみる。

fastFib 5
=> fst (fibPair 5)
=> fst (fibStep (fibPair 4))
=> fst (fibStep fibStep (fibPair 3))
=> fst (fibStep fibStep fibStep (fibPair 2))
=> fst (fibStep fibStep fibStep fibStep (fibPair 1))
=> fst (fibStep fibStep fibStep fibStep fibStep (fibPair 0))
=> fst (fibStep fibStep fibStep fibStep fibStep (0, 1))
=> fst (fibStep fibStep fibStep fibStep (1, 1))
=> fst (fibStep fibStep fibStep (1, 2))
=> fst (fibStep fibStep (2, 3))
=> fst (fibStep (3, 5))
=> fst (5, 7)
=> 5

をを、タプルにすることで、計算量が減ってます、自分で展開していくとなるほどとよくわかる。

さて、最近Higher-order Perlを読んでいる僕としては、これをperlで書いてみたくなるわけである。

#!/usr/bin/perl

use strict;
use warnings;

sub fibStep {
    my $n = shift;
    return [$n->[1], $n->[0] + $n->[1]];
}

sub fibPair {
    my ($n, $fs, $fp) = @_;
    return [0,1] if ($n == 0);
    return $fs->($fp->($n-1,$fs,$fp))
}

sub fastFib {
    my $n = shift;
    my $fs = \&fibStep;
    my $fp = \&fibPair;
    my $fib_num = $fp->($n,$fs,$fp);
    return $fib_num->[0];
}

my $number = shift;
print fastFib($number)

サブルーチンのリファレンスを引数にとらないといけないのがhaskellと異なるとこかな。あとは書いてて思ったのは関数の型を書くとプログラムの流れが理解しやすいナァと。

実行すると一瞬で計算が終わる（速い!）

実際に処理の流れを追うために-dオプションを付けて実行してsを連打すると、main::fibPairがどんどん実行されて$nが0になったところで今度はmain::fibStepが次々実行されていく様がわかる。

Higher-order Perlの5章にもフィボナッチ数列のことが書いてあるのだが、まだそこまで読み進めていない。(今3章突入したところ)

Higher-Order Perl: Transforming Programs with Programs
Mark Jason Dominus
Morgan Kaufmann / 5692円 ( 2005-03-28 )

ふつうのHaskellプログラミングふつうのプログラマのための関数型言語入門
青木峰郎
ソフトバンククリエイティブ / ?円 ( 2006-06-01 )

haskellを勉強しながら、Higher-order Perlを読むと、色々新たな発見があって楽しい。

Drkcore

haskellでフィボナッチ そしてPerlで書いてみた

haskellでフィボナッチそしてPerlで書いてみた