Archive for the ‘Uncategorized’ Category

End of an Era

July 1, 2011

Last tuesday I got my PhD. Unfortunately, that has some consequences for this blog. Since I’ll now be working at a real job, which I’m starting monday, I won’t be able to do any Programming Praxis exercises during working hours anymore like I have for the past couple years. I’ll try and do some in the evenings now and then, but since I have a lot of other stuff to do, the frequency will be significantly reduced.

I hope you guys have enjoyed this blog over the past few years and I hope I’ve gotten at least a few of you to try out Haskell. If you haven’t, what are you waiting for? Go download the Haskell Platform and get started! Looking for something to practise on? Go do some of the exercises from Programming Praxis. I’m looking forward to reading your solutions.

Remco Niemeijer

Programming Praxis – Rational Numbers

January 25, 2011

In today’s Programming Praxis exercise, our goal is to implement common operations on rational numbers. Let’s get started, shall we?

We could of course just use the Data.Ratio module, which does everything we need, but that kind of defeats the purpose of the exercise.

Creating a rational number isn’t too difficult, but if you condense the various cases into a single expression like I did here you need to take care to get the signs right. Fortunately, that’s what unit testing is for. I’m using plain tuples here for the sake of brevity. In production it would be advisable to use a data type instead to prevent passing in invalid rationals such as (1,0).

ratio :: Integral a => a -> a -> (a, a)
ratio _ 0 = error "Division by zero"
ratio n d = (signum d * div n g, abs $ div d g) where g = gcd n d

For adding we use the given formula. Subtracting is the same as adding the negative of the second number.

plus :: Integral a => (a, a) -> (a, a) -> (a, a)
plus (nx, dx) (ny, dy) = ratio (nx * dy + dx * ny) (dx * dy)

minus :: Integral a => (a, a) -> (a, a) -> (a, a)
minus x (ny, dy) = plus x (-ny, dy)

Multiplication didn’t pass the unit tests at first. Turns out the formula in the Scheme solution is wrong, so I replaced it with the correct one. Division is just multiplying by the inverse of the second number.

times :: Integral a => (a, a) -> (a, a) -> (a, a)
times (nx, dx) (ny, dy) = ratio (nx * ny) (dx * dy)

divide :: Integral a => (a, a) -> (a, a) -> (a, a)
divide x (ny, dy) = times x (dy, ny)

Finally, there’s the comparison operator.

lessThan :: Integral a => (a, a) -> (a, a) -> Bool
lessThan (nx, dx) (ny, dy) = nx * dy < dx * ny

I used a decent number of unit tests to cover all of the potentially problematic cases.

main :: IO ()
main = do print $ ratio 1 2           == (1,2)
          print $ ratio 1 (-2)        == (-1,2)
          print $ ratio (-1) 2        == (-1,2)
          print $ ratio (-1) (-2)     == (1,2)
          print $ ratio 2 4           == (1,2)
          print $ plus (1,2) (-1,6)   == (1,3)
          print $ minus (1,2) (1,6)   == (1,3)
          print $ times (3,5) (5,3)   == (1,1)
          print $ times (2,5) (3,7)   == (6,35)
          print $ times (2,5) (-3,7)  == (-6,35)
          print $ divide (3,4) (3,2)  == (1,2)
          print $ divide (1,3) (-2,3) == (-1,2)
          print $ lessThan (1,3) (1,2)
          print $ lessThan (-1,2) (1,6)
          print $ lessThan (-1,2) (-1,6)

Everything passes, so it looks like things are working correctly.


August 13, 2010

I’m away on conference/vacation for the next six weeks, so I’ll be back at the start of October. In the meantime, if you’ve not already done so, why not go and learn Haskell yourself? Real World Haskell is a good way to get started.

Happy Haskell hacking holidays!

Power programming

January 27, 2010

Yesterday I read called Power Programming, in which the author gives solutions for this Google Code Jam problem in Python, Perl, Arc and C++. I figured I’d have a go at providing a solution in Haskell to see how it stacks up.

Since converting the given tree to a tuple won’t work in Haskell (it might with Data.Dynamic, but that’s not exactly standard practice), we’ll have to settle for writing a parser. Fortunately, Parsec makes this really easy.

First, we need some imports.

import Control.Applicative ((<*>), (<$>))
import Text.Parsec
import Text.Parsec.Token
import Text.Parsec.Language
import Text.Printf

We’ll also have to define the structure of the decision tree.

data Tree = Node Double String Tree Tree | Leaf Double

Since we need a parser for the decision trees anyway, we might as well write a parser for the complete test case input. Because the tokens we’ll be getting are pretty much the same as in most programming languages, we can just use the existing haskell tokenizer to parse the tree.

input    = count' testCase
testCase = (,) <$> (natural h >> tree) <*> count' animal
tree     = parens h $ try node <|> leaf
node     = Node <$> float h <*> identifier h <*> tree <*> tree
leaf     = Leaf <$> float h
animal   = identifier h >> count' (identifier h)
h        = haskell
count' p = flip count p =<< (fromIntegral <$> natural h)

Once we have the tree and the animals, calculating the cuteness of one of them is just a matter of taking the correct branches and multiplying all the values.

cute (Leaf x) _        = x
cute (Node x f l r) fs = x * cute (if elem f fs then l else r) fs

Showing the result just requires a bit of printf use.

output = mapM_ (\(i, (t, as)) -> printf "Case #%d:\n" i >>
             mapM_ (printf "%1.7f\n" . cute t) as) . zip [1::Int ..]

And finally a function that combines the required steps.

solve = either print output . parse input ""

A test to see if everything works correctly (for the sake of brevity, we read the input from a file, but using getContents to read from the console or a plain string literal will work as well):

main = solve =<< readFile "input.txt"

Not bad I reckon. Obivously, it’s not quite as brief as the Perl solution, but at least to me it’s a whole lot more readable. It’s roughly the same size as the Arc solution, which seems about right to me.

Programming Praxis – Master Mind, Part 1

November 17, 2009

…aaaand we’re back. Sorry for the delay, life can get really busy. In yesterday’s Programming Praxis problem we have to create a program that will answer guesses for the game Master Mind. Let’s get to it, shall we?

As usual, some imports:

import Data.List
import System.Random

First, we need a function to determine how good the player’s guess was:

match :: [Int] -> [Int] -> String
match code guess = concat $ zipWith replicate [bs, ws, ds] "BW."
    where bs = length . filter id $ zipWith (==) code guess
          ds = length (foldr delete code guess)
          ws = length code - bs - ds

Next, we write the guess loop:

go :: [Int] -> IO ()
go code = do hits <- fmap (match code) readLn
             if all (== 'B') hits then putStrLn "You Win!"
                else putStr (hits ++ "\nTry again: ") >> go code

A game can be started either with a predefined code or a random one if none has been provided.

play :: Maybe [Int] -> IO ()
play code = do putStr "Enter your guess as a list: "
               rnd <- fmap (take 4 . randomRs (1, 8)) getStdGen
               go $ maybe rnd id code

To test, start a game with a random code:

main :: IO ()
main = play Nothing

And that’s it for this week. Have fun playing!

Vacation announcement

July 14, 2009

Since I will be on vacation for the next 4 weeks with no internet access, I won’t be able to post anything in the meantime. I should be back for Programming Praxis puzzle number 59.

In the meantime, I leave you with the following two koans to ponder:

A student said to his master:
“Master, there is a bug in my code, but I cannot find it.”
The master took one look at the code and said:
“No wonder, your code is far too long.
As it is difficult to find a needle in a haystack,
so is it difficult to find bugs in lengthy code.”
The student spent the next year studying
abstractions, algorithms and refactoring.
After that year, he once again approached his master and said:
“Master, there is a bug in my code, but I cannot find it.”
The master took one look at the code and said:
“No wonder, your code, while short, is so abstract
that it is difficult to reason about what happens.”
The student was enlightened.

A student approached his master and said:
“Master, I have heard that a neighboring monastery
teaches a different philosophy from ours. I would
very much like to study there.”
The master nodded, and said “It is always a good idea
to learn of other philosophies. You have my permission.”
Two years later the student returned to the monastery.
“Master, in my time at the other monastery I have observed
a striking difference between the two philosophies:
whereas we teach a strict adherence to the rules at all times,
they are more interested with the result, and obey rules
only when convenient. What is your opinion on this?”
The master replied: “What do you use to eat meat?”
“Chopsticks”, replied the student.
“What do you use to eat soup?”
“A spoon”.
The student was enlightened.

Hello world!

April 23, 2009

It wouldn’t be a programming blog without a Hello world post, now would it? 🙂