Brian Berns brianberns
brianberns
/ EnumerateRationals.fs
Created
March 24, 2019 04:30
Enumerating the Rationals: How to enumerate the rational numbers without duplication using a Calkin–Wilf tree
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| open System.Numerics | |
| // http://fsharpnews.blogspot.com/2013/08/implementing-rationals-in-f.html | |
| type Rational(p: BigInteger, q: BigInteger) = | |
| let rec gcd a (b: BigInteger) = | |
| if b.IsZero then a else | |
| gcd b (a % b) | |
| let fixSign(p: BigInteger, q: BigInteger) = | |
| if q.Sign > 0 then p, q else -p, -q |
brianberns
/ FixedPoint.fs
Last active
March 24, 2019 04:25
Step-by-step explanation of an F# function that can be used to generate recursive functions from non-recursive functions, with some simple examples. This is analogous to the Y combinator in untyped lambda calculus.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /// For a function, f, define fix(f) as the "fixed point" of f: | |
| /// A value, z, such that f(z) = z. | |
| /// | |
| /// Substituting fix(f) for z, gives f(fix(f)) = fix(f), which | |
| /// we flip to fix(f) = f(fix(f)). | |
| /// | |
| /// This fixed point, z, is itself is a function that takes an | |
| /// argument, x. We have to make x explicit in the definition | |
| /// in order to avoid infinite recursion when fix is called. | |
| /// |
NewerOlder