Higher Logics

In a slight departure from my usual computer science focused musings, I'm going to analyze another logical conundrum that has raged for centuries. Which came first, the chicken or the egg? One of my many online debates clued me into the fact that there is a widespread belief that the egg came first. I even found a "paper" providing an in-depth analysis concluding the same. Unfortunately, the analysis appears flawed. An e-mail to the author bounced, so I figured I might as well post my brief analysis here. A simple inductive analysis suffices to conclusively determine the causal chain. Base case: single celled organism, asexual reproduction via mitosis (given our current knowledge) n implies n+1: species n produces, by its own reproduction mechanism R n , an offspring n+1 with a slightly different reproduction mechanism, R n+1 . Conclusion: the "chicken" came first. In this case, our "chickens" were not hatched from "chicken eggs", but wer...

My day job is has stuck me with C#, but I try to make the best of it, as evidenced by my FP# and Sasa C# libraries. One thing that still gets in my way more than it should is O/R mapping. No other mapper I've come across encourages a true object-oriented application structure. Granted, I've only really used NHibernate, and I had built my own mapper before that was even available, but I've read up quite a bit on the the other mappers. By true OO structure, I mean that all application objects are only constructed from other application objects, which doesn't involve dependencies on environment-specific code (ie. if you're running under ASP.NET, Windows forms, Swing, etc.). A pure structure encourages a proper separation between core application code, and display and controller code, which allows more flexible application evolution. Instead, controller logic often manually constructs application objects, passing in default arguments to properly initialize the required ...

Calculating permutations has some fairly nifty algorithms out there. I recently ran into a permutation problem for which I couldn't find an existing algorithm. I admit that I didn't look too hard though. Basically, I needed the permutations of the elements of a set of size N over K slots. However, the permutations should include duplicate elements from the set, as K > N is valid configuration. This corresponds to N K permutations. Most algorithms I found did not permit duplicate elements. As an example of an application for such a permutation algorithm, imagine the set of all function signatures of arity K-1 over N types. This corresponds to K slots with N possible choices for each slot. I devised a fairly simple implementation of such a permutation algorithm. Essentially, N forms the base of an arbitrary-precision integer of size K. In other words, we have an array of elements with a maximum of N which index our set. To permute, we simply increment the first element and pr...

Many people find themselves stumped by the so-called Blue-Eyed Islanders puzzle . There is also much controversy over its supposed solution. I'm going to analyze the problem and the solution, and in the process, explain why the solution works. To begin, let's modify the problem slightly and say that there's only 1 blue-eyed islander. When the foreigner makes his pronouncement, the blue-eyed islander looks around and sees no other blue eyes, and being logical, correctly deduces that his own eyes must be blue in order for the foreigner's statement to make sense. The lone blue-eyed islander thus commits suicide the following day at noon. Now comes the tricky part, and the source of much confusion. Let's say there are 2 blue-eyed islanders, Mort and Bob. When the foreigner makes his pronouncement, Mort and Bob look around and see only each other. Mort and Bob thus both temporarily assume that the other will commit suicide the following day at noon. Imagine their chagrin...

Extending the work in my last post , I've developed a way to express an almost type-safe, general monad in C# . Similar to my module translation, the single monad object becomes a pair of co-operating objects, only one of which the monad implementor must define. Since C# cannot abstract over type constructors, I had to exploit the only feature that could accomodate the flexibility I needed: C#'s dynamic typing. // The Monad object, indexed by a singleton type that implements the // monad operations. public sealed class Monad<M, T> where M : struct, IMonadOps<M> { ... } // An object that implements operations on the monad's encapsulated // state. public interface IMonadOps<M> where M : struct, IMonadOps<M> { /// Return the encapsulated state for the monad's zero value. object Zero<T>(); // Return the encapsulated state for the 'unit' operation. object Unit<T>(T t); // Perform a bind operation given th...

I've found other monad tutorials very frustrating. They are typically written in expressive languages with type inference, which permits concise descriptions, but obscures the underlying type structure. I've been struggling with writing something close to a monad in C# for quite some time, simply because none of these tutorials give a sufficiently complete description of a monad's structure. Suprisingly, the Wikipedia page on monads helped clarify what I was missing. Here is the general structure of a monad all these tutorials use : -- the type of monad m type m a = ... -- return is a type constructor that creates monad instances return :: a → m a -- bind is a function that combines a monad instance m a with a -- computation that produces another monad instance m b from a's -- to produce a new monad instance m b bind :: m a → (a → m b) → m b So the monad type 'm', has a function 'return' that constructs instances of that type, and 'bind' which c...

The venerable Oleg Kiselyov once posted about the "best" collection traversal API . Let's call this ideal iterator a "SuperFold". LTU also covered his article . Essentially, a SuperFold is a left fold with early termination support. Any cursor can then be automatically derived from the SuperFold. The converse is not true. Additional arguments are made in the above paper and in the LTU thread, so I won't repeat them here. Without further ado, I present the SuperFold for my purely functional list in C# : //OCaml signature: ((T → B → bool * B) → B → B) → (T → B → bool * B) → B → B B SuperFold<B>( Fun<Fun<T, B, Pair<bool, B>>, B, B> self, Fun<T, B, Pair<bool, B>> proc, B seed) { bool cont; proc(head, seed).Bind(out cont, out seed); return cont ? self(proc, seed) : seed; } While quite simple, it's not as efficient as it should be since C#/.NET doesn't support proper tail calls. You can see in that so...