Y combinator: Difference between revisions
→{{header|F Sharp|F#}}: Minor corrections to second group of examples and comments...
m (→{{header|Scala}}: added parentheses for clarity) |
GordonBGood (talk | contribs) (→{{header|F Sharp|F#}}: Minor corrections to second group of examples and comments...) |
||
Line 2,379:
// val fix : ((unit -> 'a) -> 'a -> 'a) = <fun>
// same efficient version of factorial functionb with added deferred execution...
let fac = fix (fun f n i -> if i < 2 then n else f () (bigint i * n) (i - 1)) <| 1I
// val fac : (int -> BigInteger) = <fun>
// same efficient version of
let fib = fix (fun fnc f s i -> if i < 2 then f else fnc () s (f + s) (i - 1)) 1I 1I
// val fib : (int -> BigInteger) = <fun>
Line 2,390:
type CIS<'a> = CIS of 'a * (unit -> CIS<'a>) // ' fix formatting
// Using a double Y-Combinator recursion...
//
// this way
// much slower than other ways due to the many additional function calls
// it demonstrates something that can't be done with the Z-combinator...
let fibs() =
let fbsgen
Seq.unfold (fun
<| fix (fun cis -> fbsgen (CIS((1I, 0I), cis))) // cis is a lazy thunk!▼
▲ <| fix (fun cis -> fbsgen (CIS(0I, cis)))
[<EntryPoint>]
Line 2,406 ⟶ 2,405:
fac 10 |> printfn "%A" // prints 3628800
fib 10 |> printfn "%A" // prints 55
fibs() |> Seq.take 20 |> Seq.iter (printf "%A ")
printfn ""
0 // return an integer exit code</lang>
Line 2,412 ⟶ 2,411:
<pre>3628800
55
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
The above would be useful if F# did not have recursive functions (functions that can call themselves in their own definition), but as for most modern languages, F# does have function recursion by the use of the `rec` keyword before the function name, thus the above `fac` and `fib` functions can be written much more simply (and to run faster using tail recursion) with a recursion definition for the `fix` Y-combinator as follows, with a simple injected deferred execution to prevent race:
|