たらいを回すならHaskell

たらい回し関数、またはtakと呼ばれる有名な関数が存在する。

C言語による最新アルゴリズム事典
奥村晴彦

同書をお持ちの方は、185ページに乗っている。

実はこれ、Haskellの売り込みには最高の関数なのだ。

ちなみに、これ最後にyを返すバージョンとzを返すバージョンがあるようで、それぞれtakyとtakzと呼ばれている模様。ここではtakyの方を採用。

まずは、私のnative tongueとも言えるperl。

tak.pl

#!/usr/bin/perl
use strict;
use warnings;

sub tak{
    my ($x, $y, $z) = @_;
    ($x <= $y) ? $y : tak(tak($x-1, $y, $z),
                          tak($y-1, $z, $x),
                          tak($z-1, $x, $y));
}

my ($x, $y, $z) = @ARGV ? @ARGV :  (10, 5, 0);
print "tak($x, $y, $z) = ", tak($x, $y, $z), "\n";
__END__

次は、みなさんお馴染みのruby。ARGVを数値変換しなきゃいけないところがちょっとめんどい。

tak.rb

#!/usr/bin/ruby

def tak(x, y, z)
  if x <= y
  then y
  else tak(tak(x-1, y, z),
           tak(y-1, z, x),
           tak(z-1, x, y))
  end
end

x, y, z = ARGV.size == 3 ? ARGV.map{|s| s.to_i } : [10, 5, 0]
puts "tak(#{x}, #{y}, #{z}) = #{ tak(x, y, z) }";

蛇も試してみた。Rubyと同じくARGVを数値変換しているんだけど、このlambdaの書き方、なんとかならんか。

tak.py

#!/usr/bin/python
import sys
import string

def tak (x, y, z):
    if x <= y:
       return y
    else:
        return tak(tak(x - 1, y, z),
                   tak(y - 1, z, x),
                   tak(z - 1, x, y))

[x, y, z] = [10, 5, 0]
if len(sys.argv) == 4:
   [x, y, z] = map(lambda s: string.atoi(s), sys.argv[1:])
print ('tak(%d, %d, %d) = %d' % (x, y, z, tak(x, y, z)))

tak.cはこんな感じ。

#include <stdio.h>

int tak(int x, int y, int z){
    return (x <= y) ? y : tak( tak (x-1, y, z),
                               tak (y-1, z, x),
                               tak (z-1, x, y) );
}

int main(int argc, char **argv){
    int x = 10;
    int y =  5;
    int z =  0;
    if (argc > 3){
        x = atoi(argv[1]);
        y = atoi(argv[2]);
        z = atoi(argv[3]);
    }
    printf("tak(%d, %d, %d) = %d\n", x, y, z, tak(x, y, z));
}

そして、宇宙語Haskell。入出力に苦労の跡が伺える(苦笑)

tak.hs

import System.Environment

main :: IO ()
main = do args <- getArgs
          if length args == 0
             then putStrLn $ strtak ["10","5","0"]
             else putStrLn $ strtak args

strtak :: [String] -> String
strtak l = concat ["tak(", (l!!0), ", ", (l!!1), ", ", (l!!2), ") = ",
                  show(taklm l)]

taklm :: [String] -> Int
taklm l = takl (map read l)

takl :: [Int] -> Int
takl l = tak (l !! 0) (l !! 1) (l !! 2)

tak :: Int -> Int -> Int -> Int
tak x y z
    | x <= y    = y
    | otherwise = tak(tak (x-1) y z)
                     (tak (y-1) z x)
                     (tak (z-1) x y)

これらを、benchmarkしてみる。cとHaskellはそれぞれ.cx,.hxとしてcompileしてある。私のPowerBook G4 (1.67GHz, 2GB RAM)上での結果。perl,ruby,pythonは、あえてMac OS X標準搭載のものを利用している。Cには最適化は施していない。

tak.cx
tak(12, 6, 0) = 12
        0.67 real         0.52 user         0.00 sys
tak.hx
tak(12, 6, 0) = 12
        0.00 real         0.00 user         0.00 sys
tak.pl
tak(12, 6, 0) = 12
       36.10 real        29.34 user         1.95 sys
tak.py
tak(12, 6, 0) = 12
       12.05 real        10.61 user         0.13 sys
tak.rb
tak(12, 6, 0) = 12
       30.87 real        26.95 user         0.24 sys

Haskellすごし!Perlあやうし!

しかし、Perlはこういう手でHaskellに見劣りしなくなる。

#!/usr/bin/perl
use strict;
use warnings;
no warnings 'recursion'; # 理由は後述

my %tak = ();
sub tak{
    my ($x, $y, $z) = @_;
    return $tak{$x}{$y}{$z} if exists $tak{$x}{$y}{$z};
    $tak{$x}{$y}{$z} = 
    ($x <= $y) ? $y : tak( tak ($x-1, $y, $z),
                           tak ($y-1, $z, $x),
                           tak ($z-1, $x, $y) )
}

my ($x, $y, $z) = @ARGV ? @ARGV :  (12, 6, 0);
print "tak($x, $y, $z) = ", tak($x, $y, $z), "\n";
__END__

この手--Memoize--は、Rubyでも使える。が、ちょっとPerlの時より面倒。

#!/usr/bin/ruby

@tak = {}
def tak(x, y, z)
    @tak[x]    ||= {};
    @tak[x][y] ||= {};
    return @tak[x][y][z] if @tak[x][y].member?(z)
    @tak[x][y][z] =
    if x <= y
    then y
    else tak(tak(x-1, y, z),
             tak(y-1, z, x),
             tak(z-1, x, y))
    end
end
x, y, z = ARGV.size == 3 ? ARGV.map{|s| s.to_i } : [10, 5, 0]
puts "tak(#{x}, #{y}, #{z}) = #{ tak(x, y, z) }";

Python版は誰かよろしこ。

両方比べてみると、今度はperlの方が速くなる。実はno warnings 'recursion'はこの時にwarningsが出るのを抑えるため。

% /usr/bin/time ./tak-mem.pl 100 50 0
tak(100, 50, 0) = 100
        0.43 real         0.30 user         0.02 sys
% /usr/bin/time ./tak-mem.rb 100 50 0
tak(100, 50, 0) = 100
        0.62 real         0.46 user         0.02 sys

しかし、宇宙人がすごいのはここからだ。

% /usr/bin/time ./tak.hx 100 50 0
tak(100, 50, 0) = 100
        0.12 real         0.00 user         0.00 sys

もちろん、ghcでコンパイルしてあるという点も少なからず貢献しているが、Memoizeを使ってもなおまだHaskellに軍配が上がるというのは、まさにAudreyのSlides(注意:Firefoxでないと見れません)の

Power of Reason

を彷彿とさせるではないか。

Dan the Man with Too Many Computer Lanugages to Speak

Comments

Perlなら標準ライブラリにMemoize搭載でっせ。

use Memoize;

memoize('tak');

Posted by goro at 2006年04月07日 22:30

non-Memoizeのtak.rbの11行目にtak.rbというゴミが入ってます。

Posted by rubyco at 2006年04月07日 22:46

rubycoさん、
Thanks, fixed.
Dan the Terrible Paster

Posted by 弾 at 2006年04月08日 01:04

pythonは
x, y, z = map(int, sys.argv[1:])

Posted by coze at 2006年04月08日 05:38

Haskellの入出力は、他の言語と似た書き方も可能です(GHC6.4以降用)

import Text.Printf

main :: IO ()
main = do { args <- getArgs
; let [x,y,z] = if length args == 3 then map read args else [10,5,0]
; printf "tak(%d, %d, %d) = %d\n" x y z (tak x y z)
}

Posted by t at 2006年04月08日 06:49

cozeさん、
あ、intってあるんですねえ。
tさん、
> import Text.Printf
え?ghcってこれ付いて来たの?

:i Text.Printf
module `Text.Printf' is a package module

NativeとNon-nativeの違いは、idiomを覚えているかどうかでもあるのですよねえ。

Dan the Non-Native (Python|Haskell) Speaker

Posted by 弾 at 2006年04月08日 11:47

RubyのMemoizeは
return @tak[[x,y,z]] if @tak[[x,y,z]]
じゃ駄目ですか？

Posted by nido at 2006年04月08日 13:18

Haskellらしいのは、文字列はぺたぺたくっつけるように書くスタイルかなぁ。

import System

main :: IO ()
main = getArgs >>= \ args ->
case args of
[x,y,z] -> showTarai (read x) (read y) (read z)
_ -> showTarai 10 5 0

showTarai :: Int -> Int -> Int -> IO ()
showTarai x y z
= putStrLn $ unwords $ "tarai" : (map show [x,y,z] ++ ["=",show $ tarai x y z])

tarai :: Int -> Int -> Int -> Int
tarai x y z | x < y = y
| otherwise = tarai (tarai (x-1) y z)
(tarai (y-1) z x)
(tarai (z-1) x y)

Posted by nobsun at 2006年04月10日 11:38

しまった。いんでんとが。。。

Posted by nobsun at 2006年04月10日 11:40

たらいまわし関数でHaskellが有利なのは、この関数の第三引数を必ずしも評価する
必要がないからです。Haskellでは評価が必要なもののみ評価が必要になってから
評価しますので有利ということです。Lazy Evaluationの威力ですね。

memoiseしてもテーブルを引くときにKeyの値が必要になって、第三引数を評価する
はめになると、それだけで遅くなってしまうからです。

ただし、TAK関数(zを返す方)では第三引数を必ず評価しなければならないので、
Lazy Evaluationの威力は発揮されません(thunkを作る分むしろ遅くなる要因になります)。
また、こちらでは memoise が効きます。

Posted by nobsun at 2006年04月10日 11:51

nobsun
大御所登場。「入門Haskell」ってnobsunが出すのかと思ったのですが。
解説ありがとうございました。またいろいろと質問すると思いますが、よろしくお願いします。
Dan the Broken Haskell Speaker

Posted by 弾 at 2006年04月10日 13:15