Snippets created by Brian Berns
-
Top k values from an array of length N using Knuth's tournament method
This method is described in Knuth's Art of Programming, Volume 3, Page 212. See https://stackoverflow.com/questions/4956593/optimal-algorithm-for-returning-top-k-values-from-an-array-of-length-n This isn't the fastest possible implementation, but it is pure functional code (no mutation).
0 people like this
Like the snippet!Posted: 6 years ago by Brian Berns
-
Seemingly impossible program defines equality between arbitrary functions
It is well known that it is impossible to define equality between arbitrary functions. However, there is a large class of functions for which we can determine equality, and it’s strange and surprising. We explore this idea using F# code translated from the Swift programming language.
3 people like this
Like the snippet!Posted: 6 years ago by Brian Berns
-
Inclusive choice type: left value, right value, or both values
F#'s Choice type is exclusive. The "Both" type defined here allows for the possibility that both values are present. This allows us to zip together sequences of unequal length. Based on Haskell's "These" type and corresponding alignment functions. (See http://hackage.haskell.org/package/these-0.8/docs/Data-These.html and http://hackage.haskell.org/package/these-0.8/docs/Data-Align.html)
1 people like this
Like the snippet!Posted: 5 years ago by Brian Berns
-
Continuation monad for mortals
Basic implementation of the continuation monad with explanation.
9 people like this
Like the snippet!Posted: 4 years ago by Brian Berns
-
Infinite lazy list of primes
An infinite lazy list of primes. Not efficient, but elegant and fun.
4 people like this
Like the snippet!Posted: 3 years ago by Brian Berns
-
Enumerating the Rationals
How to enumerate the rational numbers without duplication using a Calkin–Wilf tree.
4 people like this
Like the snippet!Posted: 6 years ago by Brian Berns
-
Complete lambda calculus interpreter with example of Y-combinator recursion
Calculate triangle numbers in the most inefficient way possible!
4 people like this
Like the snippet!Posted: 5 years ago by Brian Berns
-
Step-by-step explanation of the Y combinator
Describes a function called "fix" that can be used to generate recursive functions from non-recursive functions, with some simple examples. (Updated with slightly improved comments.)
9 people like this
Like the snippet!Posted: 5 years ago by Brian Berns
-
A very simple free monad
You might have heard that a "free" monad can be created from any functor. Unfortunately, that doesn't mean much if you're not already familiar with category theory. This example creates a free monad from a simple functor types
5 people like this
Like the snippet!Posted: 4 years ago by Brian Berns