Tuesday, November 27, 2007

Elegant Haskell

I'm going to post some pieces of my game so that you can see just how clean and simple and easy to understand haskell code can be. I've modified this code somewhat so that all it really does is initialize the world, create an area, count ten turns and then exit.
data World = World {
turn :: Integer,
player :: Player,
area :: Area
} deriving (Show)
This is the structure of the game, holding all necessary data to progress in the game. Deriving show is an easy way to allow any arbitrary structure to be turned into a string provided each of its members is already capable of being shown. I made Area and Player types showable myself.
main = do
gameMap <- genArea 20 20
let w = World 0 initPlayer gameMap
gameLoop w
This is the initial entry point of the program. First it generates an area of 20x20 squares using a method we won't be discussing at the moment. Then it initializes a world state. Essentially it says the value of w is equivalent to the constructor of type World where each field is equal to in, order, 0, the player init function, and the map we generated. Finally, it passes the world into the gameloop.

You might be wondering why I didn't simply pass genArea into the World constructor the way I did for initPlayer. The reason is because area generation uses random variables and randomness is outside of the system. Therefore we have to use some special syntax to execute the process that will generate a map object. Player at the moment simply sets all the player stats to initial values. Eventually when it requires actual player input (as well as randomness), it will also use the same syntax to generate the player.

It may seem odd, but there are serious advantages to this obtuseness that I will get into later.
gameLoop :: World -> IO ()
gameLoop w = do
putStrLn $ ("Turn: " ++ show (turn w))
let w' = incTurn w
unless (gameEnd w') (gameLoop w')
This will require more instruction. The dollar sign means to call putStrLn and pass the rest of the line into it. The rest of the line says to concatenate "Turn: " and the string representation of the turn field of the World variable w. The show function simply turns anything into a string.

The next line increments the turns in the game by passing the whole world into incTurn and then taking the result. The result w' is just w with turns incremented by one. Then it passes the modified world into gameEnd to see if the game is finished and if not, calls gameLoop again with the new modified world.

First thing to note is the fact that this function is recursive. Due to the miracle of tail recursion, this recursion uses no extra memory. It can recurse indefinitely without using any resources at all.

The next thing to notice is that I did not try to increment turns in place with the let and then continue to use w. Instead I made a duplicate of w only with the turns increased.

"But OnMach, " you point out, "doesn't that mean you duplicated the variable and now are using twice the memory?" The answer is no. You can be sure that this is completely optimal. It won't actually calculate w' until it is needed, when it does it will end up with only what is needed because the language is lazy. Also, though my own knowledge is lacking in this department, I believe that due to the way this language is structured the compiler can see quite plainly what I need and when I'll need it. That is one of the major advantages of haskell. The compiler can make a huge number of optimizations on your code without you having to specify anything at all.
gameEnd :: World -> Bool
gameEnd w = turn w > 10

incTurn :: World -> World
incTurn (World t p a) = World (succ t) p a
GameEnd simply checks to see if ten turns have passed and returns true if so.

IncTurn takes a World structure and returns a World structure with the turns incremented by one. The succ function is defined on all enumerated types and simply returns the successor. So (succ 3) == 3+1.

That's all there is to it. At this point you are probably thinking it looks like a less readable version of python. But there are some important things about this code that aren't immediately obvious. I called initPlayer and genArea up above, but in reality those functions are never calculated. The reason is because I never actually used the player or area. Haskell doesn't calculate what it doesn't need to.

Another issue that needs to be mentioned is why in certain places I use a do notation and others I didn't. Do notation is used to string monads together. The reason I use them above is because in each case I either needed to deal with input/output (putStrLn) or I had to deal with return values that would not be the same on each call (genArea) in this case due to randomness.

A function that is guaranteed to give the same answer with the same arguments is called a pure function. Because it always gives the same answer, it can be hugely optimized. If you need to call a function with the same arguments twice, the second time it will simply return the answer instead of calculating it all over again. This leads to huge savings in places you'd never be able to hand optimize. And it requires no extra syntax, breaking out of loops, etc to achieve that.

One more thing. Notice how I passed in w to endGame as a single variable, but when I passed the same variable into incTurn, I was able to deconstruct it into its constituent parts and manipulate them separately. This is an enormously powerful feature of haskell. You can deconstruct any type into its constituent pieces (assuming you have access to them) and manipulate them at will. This goes way beyond how I've used them here, but I'll leave it at that for now.

I think this is an ok first impression from someone who is himself just getting a handle on the sheer power of the language himself.

No comments: