2006年04月07日 22:09 [Edit]

たらいを回すならHaskell

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

同書をお持ちの方は、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


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

この記事へのトラックバック
CSNagoya 「ふつうのHaskell」のP120にて、Haskellの特徴のひとつである遅延評価の利点として「たらいまわし関数」という関数が紹介されていました。遅延評価がされる場合はそもそも不要な部分が計算されないのでHaskellに軍配が上がるのは間違いないのですが、面白そうな...
対決!たらいまわし関数【csnagoya (PukiWiki/TrackBack 0.3)】at 2008年04月14日 13:26
Gauche Nightではしゃぎすぎたところにもってきて、昨日はEncodeをメンテしながらホームパーティーなんぞをしていたらどうやら風邪を引いてしまったみたい。 風邪で頭が痛いときには、λと戯れるに限る、ということでこの話題。
λ萌え - たらいを後回し【404 Blog Not Found】at 2007年05月13日 06:30
google-code-prettifyを本blogでも導入しました。 ul.favicon { list-style: none } google-code-prettify - Google Code ex: 404 Blog Not Found:CGIの神話と現実 404 Blog Not Found:たらいを回すならHaskell cf: 404 Hatena::Diary not Found - [Haten...
google-code-prettifyを導入【404 Blog Not Found】at 2007年03月26日 16:23
フィボナッチ関数やたらい回し関数のような、自分を複数回呼ぶような再帰関数は、memoizeするかしないかで結果が極度に変わってくるが、これをCでやってみようという企画。 Judy Arrays Web PageJudy is a C library that provides a state-of-the-art core technology that...
C - Judyでたらい回し【404 Blog Not Found】at 2006年12月07日 05:05
土と芋とユンボに戯れ、ご機嫌で過ごした三連休の最後をしめくくるかのように宅配ボックスに入っていたのがこちら。 javaによるアルゴリズム事典 奥村 晴彦他 404 Blog Not Found:Mastering Algorithms with Perl-siuyeさんのコメントjava版が数年前出てま....
javaによるアルゴリズム事典【404 Blog Not Found】at 2006年11月05日 23:54
おお、ついに正三郎さんまでたらい回し大会に参加!で、ここ読んで 標題: Re: ちょっと気になる本、その2: ホットコーナーの舞台裏この前も書いたけど、よくあるウェブアプリのようなものは、スクリプト言 語でも十分な時代になってるんです。だって、RDBはネイティブで動....
javascript でもたらいを回してみた【404 Blog Not Found】at 2006年04月25日 13:35
やはりtakに関しては、元祖であるLisp系がないというのもなんだし、折角gaucheを入れたので、同一条件でbenchmarkしてみた。 404 Blog Not Found:たらいを回すならHaskellこれらを、benchmarkしてみる。
gaucheでたらいを回してみた【404 Blog Not Found】at 2006年04月17日 00:10
私の大学生時代、竹内郁雄先生がうちの大学に講演に来たときに「再帰を使う適当な関数を作ってみたらベンチマークとして面白いものになった」とかいう話を聞いたような気がする。
竹内関数=たらいまわし関数?【淡々と生きる日記】at 2006年04月08日 22:14
なんか、非正格言語であるのに、これを書いておかないのはまずい気がしてきた。といっても、Haskellとほとんど(全く?)同じなので、面白くも何ともないのだが。 実行の結果 マシンの性能差が効くよな。 これだけでは、何がどう面白いのかあまりにもわらかなさ過ぎるので...
[プログラミング]Concurrent Clean : たらいまわし関数【lethevert is a programmer】at 2006年04月08日 18:57
[http://blog.livedoor.jp/dankogai/archives/50447103.html:title=たらいを回すならHaskell]の話。Haskellすげえええ。 さて、PythonのMemoize((ずっとMemorizeだと思ってました。))版は誰かよろしこということなので書いてみました。まずMemoizeしない版を、よりPythonら...
[技術]Pythonでもわりとたらい回せそう?【はこべにっき#】at 2006年04月08日 16:31
⇒ 404 Blog Not Found:たらいを回すならHaskell の tak 関数の ruby 版を書き直して、定数にハッシュをバインドして特異メソッドにすると、Ruby っぽいコーディング・スタイルになります。 size を length へ、map を collect に変えたのは私の趣味なのでどうでも良いです...
[src][Ruby]Memorize を Ruby で書くなら【Tociyuki::Diary】at 2006年04月08日 01:15
Dan Kogai さんのブログに 蛇も試してみた。Rubyと同じくARGVを数値変換しているんだけど、このlambdaの書き方、なんとかならんか。 http://blog.livedoor.jp/dankogai/archives/50447103.html ということで下記のようなコードがのってます。 最近の Python ではこうい...
Python でこんなんしないっす。【NamingSense::TokuLog!】at 2006年04月08日 01:13
これを見てふと思い立って作りました。 404 Blog Not Found:たらいを回すならHaskell-goroさんのコメント Perlなら標準ライブラリにMemoize搭載でっせ。 use Memoize; memoize('tak'); Get via CPAN (will be available soon) Get via www.dan.co.jp
perl - Attribute::Memoize 0.01 Released!【404 Blog Not Found】at 2006年04月08日 00:56
この記事へのコメント
nobsun
大御所登場。「入門Haskell」ってnobsunが出すのかと思ったのですが。
解説ありがとうございました。またいろいろと質問すると思いますが、よろしくお願いします。
Dan the Broken Haskell Speaker
Posted by at 2006年04月10日 13:15
たらいまわし関数でHaskellが有利なのは、この関数の第三引数を必ずしも評価する
必要がないからです。Haskellでは評価が必要なもののみ評価が必要になってから
評価しますので有利ということです。Lazy Evaluationの威力ですね。

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

ただし、TAK関数(zを返す方)では第三引数を必ず評価しなければならないので、
Lazy Evaluationの威力は発揮されません(thunkを作る分むしろ遅くなる要因になります)。
また、こちらでは memoise が効きます。
Posted by nobsun at 2006年04月10日 11:51
しまった。いんでんとが。。。
Posted by nobsun at 2006年04月10日 11:40
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
RubyのMemoizeは
return @tak[[x,y,z]] if @tak[[x,y,z]]
じゃ駄目ですか?
Posted by nido at 2006年04月08日 13:18
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
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
pythonは
x, y, z = map(int, sys.argv[1:])
Posted by coze at 2006年04月08日 05:38
rubycoさん、
Thanks, fixed.
Dan the Terrible Paster
Posted by at 2006年04月08日 01:04
non-Memoizeのtak.rbの11行目にtak.rbというゴミが入ってます。
Posted by rubyco at 2006年04月07日 22:46
Perlなら標準ライブラリにMemoize搭載でっせ。

use Memoize;

memoize('tak');
Posted by goro at 2006年04月07日 22:30