Data vs Codata

Infinite lists

OCaml and Haskell are both statically typed functional programming languages. Their type systems are very similar. They both have function types, algebraic data types, higher-order types (list of things, maybe/option types, tuple types). They both support type variants of the Hindley-Milner type inference algorithm.

But in Haskell, one often heralded featured is that data types can be "infinite". Haskellers love to showcase this clever one-linear which produces the fibonacci numbers:

fibs :: [Int]
fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

qed

Infinity Plus One

2014年09月21日

A school-yard argument

Everyone has, at some point during their childhood, found themselves in a contest to name the largest number. It starts off with perhaps a hundred, or a thousand, then a million, a billion, a trillion. Perhaps the savvy youngsters will know about quadrilions or quintillions.

But at some point, we run out of words for numbers. The argument continues with one-upsmanship. Your friend names a numbers. You tack "plus one" onto the end. They come back with "plus two". Maybe some multiplication gets thrown in there ("a trillion trillion!").

The game gets boring pretty quickly, though. You decide it's time to pull out your trump card: infinity!

Surely, you've won. No one can top infinity. It's bigger than the biggest number, after all. Your friend will have to forfeit.

Or so you think. But they comeright back at you: "Infinity plus one!"

qed

The Halting Problem in Javascript

2014年09月11日

The Specs for Halt

We suppose the existence of a function called Halt. It takes one parameter: a function, we will call f, that takes 0 parameters. Then Halt(f) returns true if the call to f() ever returns a value, and Halt(f) returns false if f() loops infinitely.

An important part of this assumption is that Halt(f) must always return true or false regardless of your choice of f. It must not itself loop.