Short Haskell Programs


David Bushong wrote an article about comparing programing languages. He has several small programming assignments and the goal is to write the shortest program in your favourite language to meet the requirements. Of course, this is all in good fun, and one shouldn’t draw any conclusions from it.

Haskell wasn’t winning the power set competition because it wasn’t entered. hukuma created a solution.

p []=[[]];p (h:t)=(p t)++[h:x|x<-p t]

and then quickly refined it, shortening it by two characters.

p (h:t)=(p t)++[h:x|x<-p t];p x=[x]

hukuma and I had previously solved the primes up-to-n challenge with:

f n=[x|x<-[2..n],all((0<).mod x)[2..x-1]]

We then slimmed it down by one character at the cost of turning a quadratic algorithm into an exponential algorithm.

f n=[x|x<-[2..n],all((0<).mod x)(f$x-1)]

That’s the price you pay for the shortest algorithm.

Yesterday I completed my solution to the BEncoding problem. BEncoding is part of the BitTorrent protocol. The problem is particularly difficult in Haskell because it requires encoding Python-style dictionaries where values can be of different types. Fortunately the glasgow extensions give rank-2 polymorphism and hence existential types. With existential types one can create a finite map type with string keys and values of any BEncodable type, and a solution is possible.



Russell O’Connor: contact me