Skip to content

Instantly share code, notes, and snippets.

View brianberns's full-sized avatar

Brian Berns brianberns

View GitHub Profile
@brianberns
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.
/// 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.
///
@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
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
brianberns / Continuation.fs
Created March 24, 2019 04:32
Computation monad for mortals: A clearly-explained implementation of the continuation monad
/// https://stackoverflow.com/questions/40052256/how-does-continuation-monad-really-work/42062682#42062682
/// A continuation is a function that represents "the rest of the computation".
type Cont<'T, 'U> = ('T -> 'U)
/// An incomplete computation is a function which, when given a continuation,
/// will return a value.
type Inc<'T, 'U> = Cont<'T, 'U> -> 'U
/// Creates an incomplete computation that holds the given value.
@brianberns
brianberns / Nest.fs
Last active May 1, 2020 05:59
Free monad of Option<'t>
/// Free monad of Option<'t>.
type Nest<'t> =
/// Nested options.
| Free of Option<Nest<'t>>
/// Lifts a value directly into the monad.
| Pure of 't
module Nest =
@brianberns
brianberns / Primes.fs
Last active February 23, 2021 07:01
Generating an infinite lazy list of primes in F#
open System.Collections
open System.Collections.Generic
type InfiniteLazyList<'T> =
| (::) of ('T * Lazy<InfiniteLazyList<'T>>)
interface IEnumerable<'T> with
member this.GetEnumerator() =
let head :: tail = this
let s =
@brianberns
brianberns / RoseTreeCps.fs
Created April 1, 2021 21:36
Rose trees, continuation-passing style
type ContinuationMonad() =
member __.Bind(m, f) = fun c -> m (fun a -> f a c)
member __.Return(x) = fun k -> k x
let cont = ContinuationMonad()
let rec reduce fs =
cont {
match fs with
| [] -> return []
open MongoDB.Bson
open MongoDB.Driver
type User =
{
_id : BsonObjectId
Name : string
}
[<EntryPoint>]
@brianberns
brianberns / Arrow.fs
Last active April 23, 2021 14:34
Arrow tutorial
[<AutoOpen>]
module Operators =
let uncurry f (a, b) = f a b
let cnst x _ = x
/// https://en.wikibooks.org/wiki/Haskell/Arrow_tutorial
type Circuit<'a, 'b> = Cir of TransitionFunction<'a, 'b>
and TransitionFunction<'a, 'b> = 'a -> Circuit<'a, 'b> * 'b
module Circuit =
open System
open System.Linq
open FSharp.Data.TypeProviders
open Microsoft.FSharp.Linq.RuntimeHelpers
type Db = SqlDataConnection<"Server=.;Database=QueryTest;Trusted_Connection=true">
let d = Db.GetDataContext()
type Result =
{
open Microsoft.EntityFrameworkCore
[<CLIMutable>]
type Customer =
{
CustomerId : string
CompanyName : string
Address : string
City : string
}