たらい回し関数
遅延評価の有無で速度の差が大きい
定義
hstarai :: 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)
tsfunction tarai(x: number, y: number, z: number) {
return x <= y
? y
: tarai(tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(z - 1, x, y));
}
rsfn tarai(x: i32, y: i32, z: i32) -> i32 {
if x <= y {
y
} else {
tarai(tarai(x-1, y, z), tarai(y-1, z, x), tarai(z-1, x, y))
}
}
無駄に再帰しまくっているだけで、実際の結果は以下と同じ
hstaraiResult :: Int -> Int -> Int -> Int
taraiResult x y z
| x <= y = y
| y <= z = z
| otherwise = x
めちゃくちゃ雑な速度比較
x <= y なので、そもそも1行目でマッチして返しているだけ
例えば、 tarai 15 10 0 の場合、
hstarai x y z
| x <= y = y -- ←ここを評価しているだけ
| otherwise = ... -- ←ここは無視
遅延評価だと、不要な部分を計算しないので、竹内関数の場合は速い
tstype CloNum = () => number;
function tarai(x: CloNum, y: CloNum, z: CloNum): number {
return x() <= y()
? y()
: tarai(
() => tarai(() => x() - 1, y, z),
() => tarai(() => y() - 1, z, x),
() => tarai(() => z() - 1, x, y)
);
}
関連
たらい回し関数で音楽生成をした人
参考
たらい回し関数の誕生の経緯。エッセイ