Thursday, March 8, 2007

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.

5 comments:

Affordable Luxurious Wedding Dress Blog said...

cheap wedding gowns,
discount bridal gowns,
China wedding dresses,
discount designer wedding dresses,
China wedding online store,
plus size wedding dresses,
cheap informal wedding dresses,
junior bridesmaid dresses,
cheap bridesmaid dresses,
maternity bridesmaid dresses,
discount flower girl gowns,
cheap prom dresses,
party dresses,
evening dresses,
mother of the bride dresses,
special occasion dresses,
cheap quinceanera dresses,
hot red wedding dresses

products said...

China Wholesale has been described as the world’s factory. This phenomenom is typified by the rise ofbusiness. Incredible range of products available with China Wholesalers “Low Price and High Quality” not only reaches directly to their target clients worldwide but also ensures that wholesale from china from China means margins you cannot find elsewhere and buy products wholesaleChina Wholesale will skyroket your profits.

products said...

Women’s nike tn Shox Rivalry est le modèle féminin le plus tendance de baskets pour le sport. tn chaussuresConcernant la semelle :Cheap Brand Jeans ShopMen Jeans - True Religion Jeans nike shoes & Puma Shoes Online- tn nike, le caoutchouc extérieur, l’EVA intermédiaire et le textile intérieur s’associent pour attribuer à la.ed hardy shirts pretty fitCharlestoncheap columbia jackets. turned a pair of double plays to do the trick.Lacoste Polo Shirts, , Burberry Polo Shirts.wholesale Lacoste polo shirts and cheap polo shirtswith great price.Thank you so much!!cheap polo shirts men'ssweate,gillette mach3 razor bladesfor men.As for

Anonymous said...

情趣用品|情趣用品|情趣用品|情趣|情趣用品|情趣

eda said...

情趣按摩棒,自慰套,角色扮演,按摩棒,跳蛋,跳蛋,
情趣,情趣,角色扮演服,吊帶襪,丁字褲,情趣用品,情趣用品,跳蛋,男女,
潤滑液,SM,情趣內衣,內衣,性感內衣,自慰器,充氣娃娃,AV,
按摩棒,電動按摩棒,飛機杯,視訊,自慰套,自慰套,

About Me

My photo
I'm a software developer who started programming at age 16 and never saw any reason to stop. I'm working on the Presentation Platform Controls team at Microsoft. My primary interests are functional programming, and Rich Internet Applications.