The Joy of Stealing

I'll never forget the first time I saw the fibonnacci set written in Haskell:

fibs :: [Int]
fibs = 0 : 1 : [ a + b (a, b) <- zip fibs (tail fibs)]

"What the heck is 'zip'?" I wondered. "That's the problem with all these academic types, they're always picking these totally uninituitive names like....oooooooohhhhh."

Then it clicked. Zip accepts two streams, takes each corresponding item in the two streams, merges them into a struct, and then emits a stream of structs. If you visualize this process you will find it looks awfully like zipping up a zipper. Hence the name.

This is a very useful function as it turns out. I was dissapointed to find that it is missing from C# 3.0 given the fact that most of the other Haskell stream functions are present and accounted for. "No problem" I said aloud to no one in particular. "I'll just write it myself."

Then I found out why it was left out. Even though C# 3.0 can create anonymous structs it can't return them from a function for the simple reason that it's a strongly-typed language and you can't refer a type's name if it doesn't have one. Luckily Wes Dyer explains that there is a solution to this problem known as "mumbling."

Basically if we pass a generic function a prototypical instance of the anonymous type which we want to return C# will be able to infer the type name transitively. Notice that mumbling only solves the problem of how to write the function definition. It doesn't solve the problem of how to actually create and return an anonymous type from within the function. Sure, I could probably instantiate it given that all anonymous structs have a default constructor. However I can't exactly set arbitrary property values on an instance of "T" now can I?

Expression Trees to the rescue. I examine the anonymous type's structure using reflection and generate a function. This function accepts one item from each stream and returns an instance of the anonymous type. Here's the code:






To help link the PropertyInfo objects with the corresponding lambda parameters when creating the expression tree I stole the EachWithIndex function from Ruby. Notice though that it would have been more elegant to merge the streams with Zip instead of using EachWithIndex. Unfortunately I have to bootstrap the language first. :-)

Here's an example of me using the Zip function to find the square root of 2:

The IterationStream is the C# equivalent of the Haskell iterate function. It simply takes a function, an initial value, and each result in the stream is equal to the result of applying the function to the previous result. Don't you love stealing good ideas from other languages?

Just for fun, here's the preceeding program in Haskell.

nextGuess :: Double -> Double
nextGuess guess = ((2.0 / guess) + guess) / 2.0

guesses = iterate nextGuess 1.0

guessAndPreviousPairs = [ (guess, previousGuess) (guess, previousGuess) <- zip (tail guesses) guesses] guessesWherePairsAreEqual = filter (\ (guess, previousGuess) -> guess == previousGuess ) guessAndPreviousPairs

answer = fst (head guessesWherePairsAreEqual)

Despite the unnecessary prototype object passed to the Zip function in the C# version I still find it to be easier to read than the Haskell version, largely due to C#'s query comprehensions. Beauty is in the eye of the beholder though. :-)

*Note: Ideally Zip would cache the generated function, making subsequent calls as fast as any other stream operator. That said I wanted to keep the example simple for the purposes of demonstration.