FP in Scala EXERCISE2-1 in F#

fib.fsx

/// 素朴なフィボナッチ数列の実装
let rec fib = function
    | 0 -> 0
    | 1 -> 1
    | n -> fib (n - 1) + fib (n - 2)

/// 素朴なフィボナッチ数列の実装(メモ化)
let fibMemo =
    let memo = System.Collections.Generic.Dictionary(dict [0, 0; 1, 1])
    let rec fib n =
        match memo.TryGetValue n with
        | true, r -> r
        | false, _ ->
            let r = fib (n - 1) + fib (n - 2)
            memo.[n] <- r
            r
    fib

/// 末尾再帰版フィボナッチ数列
let fibTailRec =
    let rec fib a b = function
        | 0 -> a
        | n -> n - 1 |> fib b (a + b)
    fib 0 1

/// 行列計算
module Mat =
    type Mat = int[,]
    let init (arrays : int[][]) : Mat =
        let r = arrays.[0].Length
        Array2D.init arrays.Length r (fun i j -> arrays.[i].[j])
    let E n : Mat = Array2D.init n n (fun i j -> if i = j then 1 else 0)
    let mul (x : Mat) (y : Mat) : Mat =
        if Array2D.length2 x <> Array2D.length1 y then invalidArg "x, y" "乗算不可能"
        let n = Array2D.length2 x - 1
        Array2D.init (Array2D.length1 x) (Array2D.length2 y) (fun i j ->
            [0 .. n] |> List.sumBy (fun k -> x.[i, k] * y.[k, j]))
 
open Mat
 
let private A = init [| [|1; 1|]; [|1; 0|] |]
let private E = Mat.E 2
 
/// ループを使用せず再帰関数を使用したO(log N)のフィボナッチ数列
/// 元ネタ : http://yosuke-furukawa.hatenablog.com/entry/20120120/1327056359
let fibMat n =
    let rec fib (a : Mat) (b : Mat) = function
        | 0 -> b.[1, 0]
        | n ->
            let b = if n &&& 1 = 0 then b else mul a b
            let a = mul a a
            n >>> 1 |> fib a b
    fib A E n
 
/// ループも再帰関数も使用しないO(log N)のフィボナッチ数列
let fibMatNoRec n =
    let r =
        n |> Seq.unfold (function 0 -> None | n -> Some(n &&& 1, n >>> 1))
        |> Seq.fold (fun (a, b) n -> mul a a, if n &&& 1 = 0 then b else mul a b) (A, E)
        |> snd
    r.[1, 0]

let test() =
    let test name func =
        let result = [0 .. 20] |> List.forall (fun i -> fib i = func i)
        printfn "%s result : %A" name result
    ["fibMemo", fibMemo; "fibTailRec", fibTailRec; "fibMat", fibMat; "fibMatNoRec", fibMatNoRec]
    |> List.iter ((<||) test)

(*
> test();;
fibMemo result : true
fibTailRec result : true
fibMat result : true
fibMatNoRec result : true
val it : unit = ()
*)