Ruby and elegance: Transpose

March 10, 2007

I recently found that the Array class of Ruby has a zip method, which works much like Haskell’s zip function, except that it allows multiple arguments.

For example:

$ irb --simple-prompt
>> [1,2,3].zip [4,5,6], [7,8,9]
=> [[1, 4, 7], [2, 5, 8], [3, 6, 9]]

The night after I did this little experiment I suddenly realized: this is a transpose function! I quickly got out of bed to document my little discovery:

def transpose(matrix)
matrix[0].zip *matrix[1..-1]

It’s the little things that make me like this language so much.

Update: I forgot the asterisk before matrix[1..-1] in the above method.


Summing it up

February 24, 2007

Today, I had a list of integers, and I wanted to sum it up. I guessed that I should write a script in Ruby, to make sure it would get done within 2 minutes. So I fired up my editor, and wrote the following script:

sum = 0 ;
$stdin.each do |line|
puts sum

Pretty straightforward. I’d rather had written the script in Haskell, but I figured I needed to get things done. This evening I tried the same thing in Haskell, but to I was surprised: it was even quicker and more straightforward than the Ruby version! Here it is:

main = interact $ show . sum . map read . lines

If you’d like more of these tiny tools, see Haskell Unix Tools.


My Evolution as a Haskell Programmer: Factorial with Arrows

February 19, 2007

A couple of years ago Fritz Ruehr wrote a great article about The Evolution of a Haskell Programmer. It was written in 2001, when I was still in high school, some years away from being introduced to the beautiful Haskell programming language.

Currently, I’m following a course on Advanced Functional Programming at the Utrecht University. One of the advanced topics tought in that course is about Arrows. Arrows are an abstraction of computations, just like Monads, but even more general and pretty nice to define stream functions with (useful for defining logical circuits, for example). I’m still trying to get my head fully around it, but so far I understand it enough to add a new part to the evolution (a missing link!): the factorial function defined with arrows.

I will present the code below and sparsely comment on it. Most of the code is actually from the Advanced Functional Programming lecture.

-- We need this library 
import Control.Arrow        

-- Define a type for stream functions, from one list to another 
newtype SF a b = SF { runSF :: [a] -> [b] }      

-- Define the Arrow functions for the SF type.  Once you've 
-- defined these three, you'll get a lot of other functions for 
-- free. 
instance Arrow SF where 
  arr f = SF (map f) 
  SF f >>> SF g = SF (f >>> g) 
  first (SF f) = SF (unzip >>> first f >>> uncurry zip)      

-- arr   lifts a function to the arrow domain 
-- >>>   combines (connects) two arrow functions 
-- first only applies the function to the first part from a 
--       tuple      

-- See the http://www.haskell.org/arrows for more 
-- information and some nice graphics, which will help 
-- understanding.

Okay, so far, so good. By defining the ‘first’ and ‘>>>’ functions, we get an ‘&&&’ combinator for free, which we will use in our final definition. For example: ‘f &&& g’ can be understood as accepting and input x, then applying both f and g to it, resulting in the output of a tuple of the results. In short, the type of ‘&&&’ is ‘Arrow arr => arr a b -> arr a c -> arr a (b, c)’.

-- The type of loop is (ArrowLoop arr) => arr (a, c) (b, c) -> 
-- arr a b.  A loop makes a function from 'a' to 'b', while 
-- 'looping' a 'c'. 
instance ArrowLoop SF where 
  loop (SF f) = SF $ \\as -> 
    let (bs,cs) = unzip (f (zip as (stream cs))) 
    in bs      

-- Note in the definition that cs is defined recursive(!)  This 
-- is really where the usefulness of Haskell's lazyness kicks 
-- in.  Although, because zip and unzip are both strict, we 
-- have to help it a little, by defining a helper function 
-- stream.      

stream :: [a] -> [a] 
stream ~(x:xs) = x:stream xs      

-- The ~ in the pattern makes the pattern matching irrefutable, 
-- which means that the pattern will not be interpreted but 
-- assumed to be correct.

Well, with that out of the way we can get to the good stuff. We just need two simple helpers to modify the stream.

-- 'Delays' a stream by prepending an element.  This can be 
-- used to initialize a stream _before_ the input is read. 
-- We're going to need this to use that nasty loop above. 
-- Remember, the c was defined recursive, without 
-- initialization. 
delay :: a -> SF a a 
delay x = SF (x:)      

-- Takes an input and muliplies it.  It 'simply' lifts an 
-- uncurried (*) to the arrow domain. 
-- Example (try it yourself): mul (6,7) = 42 
mul :: Arrow arr => arr (Integer, Integer) Integer 
mul = arr (uncurry (*))

Okay, now, the basic idea is to supply a stream function with the list of integers and then all we have to do is multiply the result of the first item with the second and multiply that result with the third, etc. Aha, that’s easy, we can just use the loop for that. The only thing we need is in initialization value to start the multiplying with. For this we use the delay. Schematicly, our plan looks like the following picture.

Factorial Arrows

You can clearly see how the loop works while the input and the output of the whole is still a single stream. The dot in the image where the output of ‘mul’ splits is actually the ‘&&&’ combinator. The code then looks like this.

facSF :: SF Integer Integer 
facSF = loop (mul >>> (arr id &&& delay 1))

Pretty clean, eh? Only thing left is a nice wrapper to run this thing.

-- Using Integers so that for large numbers (and factorials 
-- tend to get really large fast) it still produces nice 
-- output.  Try 'fac 420' for example. 
fac :: Integer -> Integer 
fac x = runSF facSF [1..x] !! fromInteger (x - 1)

This concludes our fun with Arrows. Viva la evolucion!


Haskell is fun!

January 8, 2007

Lately, I’ve been doing a lot of Haskell. I must warn you, I always have a Programming Language Of The Month, but now I feel as if it’s different. Haskell is a programming language where you get the feeling that a lot of things are just perfect.

First off, the way the type-system works, many, many, many errors that you’d normally make in your imperative language are simply impossible to make. It’s very strict, and although ruby is me second language of choice, this is also a really good thing. For example, I recently read that it’s virtually impossible to generate invalid XML. And that’s not because the author is some crazy god-like person, it’s just an intrinsic feature of the data-types in Haskell.

Furthermore, Haskell gives you a really good intellectual challenge. You really spend more time thinking than typing. The information density in your code is quite high compared to a lot of other languages I work in.

Also, having no side-effects is a Good Thing. The first time that I worked in Haskell, I was really disappointed that IO was so hard to do, with all that incomprehensible Monad-stuff and more. As it turned out, it’s really not that hard, and debugging will get so much easier. You just don’t need logger statements all around your code.

Ruby is my second language of choice, and that’s because you don’t have to type that much. But one of the powers of ruby is the meta-programming, which is a bit of a hack. But less typing means you’ll get stuff done sooner and it’s harder to make errors. In Java, you’ll have to type a lot (even with Eclipse), because of the type-system (pun intended). In Haskell, the type-system is really smart, and you don’t have to type a lot of trivial things. The compiler will automatically deduce the types of functions for you. So you’ll end up having the advantages of a static typed language, but better, and having the advantages of dynamic languages, less code.

Finally, there are a lot of really smart people in the Haskell community. There’s lots of really advanced stuff being done, but most people are also very good writers. Just google for “Simon Peyton Jones“, and read some of his papers. Most are explaining beautiful, advanced things, and he has a really clear writing style. Maybe he’s one of the best, but there’s lots of other people that write excellent programs, articles and other stuff.

So, if you feel at least the tiniest bit excitement, I can recommend that you download a haskell compiler, do some tutorials, don’t give up and get just as excited as I am! And don’t forget: the best way to get to know a language is to program in it!



January 7, 2007

Quite some time ago, when the sky of the internet was still blue, people didn’t have blogs and Wikipedia, but used so-called newsgroups to communicate and learn. Those newsgroups got lots of questions asked over and over again, so they started compiling a list of them, posting it each month, and naming it, appropriately, Frequently Asked Questions.

These days, the three-letter acronym is used mostly for documents that are a convenient way out of writing real documentation or structuring information on a website. There’s nothing wrong with that, but the difference with the original FAQ is that most of the time, the questions answered are never really asked.

Obviously, this kind of language polution is not the way to go. And because I have a big hole in my language ozon layer I got just annoyed enough to go and think of solution for this misbehavior.

Because I’m a realistic kind of guy, I don’t expect the whole word to use my made-up acronym to rebrand their FAQs. So I thought of something clever: find another group of words that discribe what’s really going on with the same acronym!

I’ve got three favorites, pick yours and hopefully you’ll think of it the next time you see ‘FAQ’:

  • Firmly Anticipated Questions
  • Fabricated Answered Questions
  • Fictionally Asked Questions

Breaking up

December 17, 2006

Sometimes you’ll have a project that’s starting to become very big. You’ll have a lot of actions attached to it, and the first five could all be the next action. My advice is to break them up into smaller projects. Sometimes the actions can literally be the projects’ names.

In my experience, you’ve got problem when the “big” actions aren’t physical anymore. As soon as you start to write something like “Get a hotel” on your action list, you’re screwed. But fortunately, the solution is easy, just make a new project and think of the necessary actions to complete it.

You’ll have a lot more projects if you do refactoring and planning like this, but you’ll get used to that. The big difference is that you’ve decided on the very next physical action, instead of having a blob of actions hidden in that one “action”.