## 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

Posted: 5 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

Posted: 5 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

Posted: 4 years ago by Brian Berns

• ### Continuation monad for mortals

Basic implementation of the continuation monad with explanation.

9 people like this

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

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

Posted: 5 years ago by Brian Berns

• ### Complete lambda calculus interpreter with example of Y-combinator recursion

Calculate triangle numbers in the most inefficient way possible!

3 people like this

Posted: 4 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.)

6 people like this

Posted: 4 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

Posted: 3 years ago by Brian Berns