階乗の実装

再帰の見本としてよく使われる階乗をJとF#で実装してみるテスト。

F#の場合

まずは普通に再帰的に実装してみる。

let rec fact = function
    0 -> 1
    | n -> n * fact (n-1)

次に末尾再帰の形で実装してみる。

let rec fact2 n res =
    if n = 0 then res
    else fact2 (n-1) (res * n)

最後に手続き的な実装もやってみる。

let fact3 n =
    let res = ref 1
    for i in [1..n] do
        res := !res * i
    res

[以下追記(2009/01/09 23:08)]

いげ太さんのコメントにより追加。fold/reduce系の関数による実装。

let fact4 n = List.fold_left ( * ) 1 [1..n]
let fact5 n = List.reduce_left ( * ) [1..n]

どんどんいろんな方法による実装が増えると面白いなあ。

[追記ここまで]

J言語の場合

まずはfact(n)の計算に1〜nまでの数列を用意して全部掛けるパターン。

   fact =: */@:>:@i.
   fact 5
120

次に再帰的な実装。これは見た目どおり。

   fact2 =: 3 : 'if. y=0 do. 1 else. y*fact2 <:y end.'
   fact2 5
120

再帰的な、暗黙の定義による実装。

   fact3 =: 1:`(* $:@<:)@.*
   fact3 5
120

最後のが複雑だけど、自身を再帰的に呼び出す動詞 $: を使って再帰を表現している。

最初に * で符号を判定して @. の働きで引数が0なら 1: を、そうでないなら (* $:@<:) を適用する。

1:は定数関数で必ず1を返し、(* $:@<:)は y * fact3 <:y と同じこと。フックをよく見てみよう。