Contractive Functions on Streams in F#

Programming isn’t always about hitting deadlines, doing sprints, building apps or fixing bugs, sometimes you want to meander and explore and enjoy the journey.

F# is a great language for kicking back, zoning out, letting the worries of the world melt away, and simply having some fun. Heresy, I know, but yes programming can be fun.

It always cracks me up when Apple pitches Swift as the perfect learning language for kids, ostensibly because of how much fun it is to use. In fact, I can’t think of a less fun language, a recycled stale amalgamation of statement oriented ideas, past their sell-by date even when fresh off the factory floor.

Anyways, enough ranting and raving, let’s do some meandering :)

Fun with Fixed Points

Before we take a look at contractive functions, let’s breifly go over the fix function. This article does a good job of explaining the function in Haskell, with the basic idea being that fix allows us to write the body of our function as a normal function, and fix takes care of the recursion.

fix (1:)

: is the lazy cons operator in Haskell and so the above function will generate an infinite sequence of ones.

As fix takes care of the recursive machinery, we get to focus on the meat of writing our simple function body.

Of course, things aren’t quite so straightforward in f#, if we try to write the same function in f#

let rec fix f = f (fix f)
let cons h t = h :: t
let ones = fix (cons 1)

we are greeted with a

Process is terminated due to StackOverflowException.

Of course this is no shock, we all know f# uses eager evaluation to evaluate function arguments to normal form before reducing the function application itself. Haskell does the opposite, it evaluates the function to weak head normal form and leaves the arguments unevaluated.

This previous mouthful of technical gobbleygook probably doesn’t mean much, so read this for a much more accessible article on evaluation strategies. The bottom line is we need to introduce thunks (placeholders for functions) into our f# definition.

Do You Feel Lucky, Thunk?

We can roll our own thunk such as here, or we can take advantage of the inbuilt Lazy type such as the following

Lazy fixed-point and Infinite Streams | F# Snippets

The lazy definition of fix wraps each of our function applications in a thunk using the lazy constructor.

let fix : (Lazy<'T> -> 'T) -> Lazy<'T> = fun f ->
    let rec x = lazy (f x) in x

So now we can write our infinite stream of ones.

let ones = fix (fun x -> Cons (1, x))

And although it’s a little unwieldy, we can write an infinite stream of natural numbers as well. We just have to be explicit about when to force a value and when to wrap one.

let nats = fix (fun x -> Cons (1, lazy ( (force (map ((+) 1))) (force x)  )))

Following Along with Really Smart People

So with our newfangled fix function and the funky … err thunky stream it generates, we’ll follow along with this highly enjoyable talk from Graham Hutton and implement a generator for contractive functions in f#.

Gory details alert! Feel free to skip over the implementation of the generating machinery as it’s not what’s important, we’ll get to the important parts afterwards.

C9 Lectures: Graham Hutton - How To Be More Productive

If you haven’t watched the talk then a contractive function boils down to a function that can look back in time at all previous inputs, but can’t access the current input, or any future inputs.

And to formalize the idea we introduce the following type and call it a generating function. A generating function takes a list of earlier inputs and generates a single output.

type Gen<'T,'U> = Gen of (List<'T> -> 'U)

And a simple function gen converts a generating function into a contractive function. Although the implementation isn’t quite so simple in f#, this was the best I could come up with.

let gen' g = fix (fun f' acc xs -> Cons (g acc, lazy (force f'      ((head (tail xs))::acc) (tail xs)  )))
let gen (Gen g) = (fun xs -> Cons (g [], lazy ( (force (gen' g) [head (force xs)] (force xs)  ))))
// type signature of gen
val gen : Gen<'T,'U> -> Lazy<Stream<'T> -> Stream<'U>

The output type signature of our gen function fits perfectly with the input of our lazy fix function,

// type signature of fix
val fix : (Lazy<'T> -> 'T) -> Lazy<'T>

so we can combine them into a new function gfix.

let gfix g = fix (gen g)
// type signature of gfix
val fix : Gen<'T,'T> -> Lazy<<Stream<'T>>

Because fix feeds our outputs back in as inputs, our Gen type gets contstrained to be T -> T instead of T -> U.

Now with the yucky machinery of our gen function out of the way, we get to the business of writing actual generator functions.

Working in Simpler Function Spaces

If you skipped over the previous section then great, because that’s not what’s important. What’s important is that gfix let’s us work in a much simpler function space!

In the same way fix freed us from worrying about the yucky details of recursion and let us focus on writing a simple function body, gfix frees us from worrying about both the recursion and feeding in a history of inputs.

So if we know our function only looks at a history of inputs in order to generate the next output, then we can write this function in the much simpler and narrower space of generating functions.

let gones = Gen (function
    | []    -> 1
    | x::xs -> x)

If we don’t have any previous inputs then generate the number one, and if we do then simply hand back our previous input, the number 1.

let gnats = Gen (function
    | []    -> 0
    | x::xs -> x + 1)

If we don’t have any previous inputs then generate the number zero, and if we do then simply add one to our previous input.

let gfibs = Gen (function
    | []        -> 0
    | [x]       -> 1
    | x::y::xs  -> x + y)

If we don’t have any previous inputs then generate the number zero, with a single previous input generate the number 1, after that add together the two most recent inputs. Simple!

The gen function and its associated rep function from the talk represent an isomorphism, a way to convert difficult problems in one space into a much simpler problem in another.

Back to that “Fun” Rant

Following along with Dr. Hutton’s talk was good fun and trying to implement his ideas in F# was also good fun. To pick up on where I left off with my rant, I often wonder whether anybody sits down with Swift of Typescript or Python and has fun with those languages?

What do you do for fun or for play with statement oriented languages? Do you break out of loops? Throw exceptions? Mutate state? Guard for nulls with asserts?

I often wonder whether introducing kids to programming through statement oriented languages is why kids don’t think programming is for play, or exploration, or meandering along a remote stream on a Sunday afternoon.

Anyways here’s the full listing for the code, along with the cribbed parts from the infinite streams snippet. Feel free to play around with it, and yes, have some fun :)