たらい回し関数

竹内関数

竹内郁雄氏が考案

遅延評価の有無で速度の差が大きい

定義

code:hs

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)

code:ts

function 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));

}

code:rs

fn tarai(x: i32, y: i32, z: i32) -> i32 {

if x <= y {

} else {

tarai(tarai(x-1, y, z), tarai(y-1, z, x), tarai(z-1, x, y))

}

無駄に再帰しまくっているだけで、実際の結果は以下と同じ

code:hs

taraiResult :: Int -> Int -> Int -> Int

taraiResult x y z

| x <= y = y

| y <= z = z

| otherwise = x

めちゃくちゃ雑な速度比較

table:tarai(15,10,0)の結果を得るまでの時間

Haskell 一瞬

Rust 9.8秒ぐらい

TypeScript 28.1秒ぐらい

x <= yなので、そもそも1行目でマッチして返しているだけ

例えば、tarai 15 10 0の場合、

code:hs

tarai x y z

| x <= y = y -- ←ここを評価しているだけ

| otherwise = ... -- ←ここは無視

遅延評価だと、不要な部分を計算しないので、竹内関数の場合は速い

無引数closureはThunkなので、TSでも以下のように書けば遅延評価されるので一瞬で求まる

code:ts

type 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)

);

}