2007年05月28日 03:30 [Edit]

Code Snippets - reduce(l|r)を実装汁!

FizzBuzzにももうええかげん食傷してきたので、次のネタをないかと思ったら、yuguiさんがtwitterで私を登録したので、ごぶさた〜と思ってblogを見に行って格好の素材を(再)発見したという前回までのあらすじ。


inject + Symbol#to_proc = fold @ 2007年05月 @ ratio - rational - irrational @ IDM
(1..10).inject(&:*)
 =>  3628800
うーむ。素晴らしい。

reduce(l|r)

というわけで問題。reducelとreducerを実装せよ。制限時間はあわせて10分。ただし、reducelとreducerは、Haskellにおいて次の挙動を示すものとする。

*Main> reducel (\x y -> "("++x++"#"++y++")") $ map show [1..4]
"(((1#2)#3)#4)"
*Main> reducer (\x y -> "("++x++"#"++y++")") $ map show [1..4]
"(1#(2#(3#4)))"

Perl 5による回答例

sub reducel(&@){
    my $binop = shift;
    my $result = shift;
    $result = $binop->($result, shift) while(@_);
    $result;
}

sub reducer(&@){
    my $binop = shift;
    my $result = pop;
    $result = $binop->(pop, $result) while(@_);
    $result;

}
$\="\n";
print reducel { "($_[0]#$_[1])" } (1..4); # (((1#2)#3)#4)
print reducer { "($_[0]#$_[1])" } (1..4); # (1#(2#(3#4)))

Extra Credit

Haskellのfold(l|r)は、なぜfoldx binop [...]ではなくfoldx binop init [...]という具合に初期値を必要とするのか、その理由を述べよ。

Dan the (Dys)?functional

追記: Twitterで私を友人登録して下さったみなさん、私が友人登録しないからといって嘆かないで下さいネ。私は猫をいぢめたくないだけなので。


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

この記事へのトラックバック
単に実装しても面白くないので、非常にキモい reduce の変種を考えてみた。
reduce【黎明日記】at 2007年05月28日 18:35
Haskellのfold(l|r)は、なぜfoldx binop [...]ではなくfoldx binop init [...]という具合に初期値を必要とするのか、その理由を述べよ。 404 Blog Not Found:Code Snippets - reduce(l|r)を実装汁! さて、なんでだろう。リストの要素の型が T だとして、foldx binop [...]
[Haskell]foldl/foldr【odz buffer】at 2007年05月28日 16:40
――ぐらい書いてくれないとわかりません>< ぼくたち地球人! コミュニケーション能力の無さでハッカーらしさをアピールしないでください!
reducel/reducer【はてな匿名ダイアリー】at 2007年05月28日 15:53
reduce(l|r) というわけで問題。reducelとreducerを実装せよ。制限時間はあわせて10分。ただし、reducelとreducerは、Haskellにおいて次の挙動を示すものとする。 404 Blog Not Found:Code Snippets - reduce(l|r)を実装汁! Symbol.class_eval do def to_proc proc do |x, y
[PG][Ruby]実装すた!【地獄の猫日記】at 2007年05月28日 14:45
Pythonで実装してみました。 404 Blog Not Found:Code...
Pythonでreduce(l|r)【西尾泰和のブログ @ Cybozu Labs】at 2007年05月28日 13:04
ref:404 Blog Not Found:Code Snippets - reduce(l|r)を実装汁! ふむ。Python でやってみるべ。 sequence だけを対象にするなら、簡単。さすがに10分もいらない。 def reducel(func, l): result = l[0] for item in l[1:]: result = func(result, item) return result def r
[Python]reducel, reducer【odz buffer】at 2007年05月28日 10:07
この記事へのコメント
なぜ初期値を必要とするのか、その理由を述べよ。
空リストのときに返す値に困るから…かな?
Posted by masatic at 2007年05月29日 18:37