25 June 2013

The Polar Game in Haskell, Day 1

So if you've been following recent posts, you know I've been messing with the logic for a simple sliding-tile game. In my last post I took some designs refined via a side trip into Dylan and brought them back into Objective-C, making them a little more idiomatic by pruning my tile classes that didn't hold their weight, and compensating for Objective-C's very limited method dispatch options.

But in addition to learning Objective-C, and Apple's APIs for writing an app, I'm also trying to further my knowledge of Haskell, which is somewhere just beyond "utter newbie." So I'm going to try to implement the game logic in Haskell, too. Since the game is decidedly stateful, there is a certain impedance mismatch here, at least with respect to the early chapters in most of the tutorials and guides. But I'm told that Haskell also makes a great imperative programming language, so let's give it a shot. And along the way I can try to mold my understanding of stateful versus imperative a little more.

For day one, which was a shorter-than-usual day, I did not get into the state monad or how to model mutation of a 2-D array yet. I wanted to consider whether I could model the tile classes the way I could in Dylan, and do something useful in them. It occurred to me that each move of the penguin, and all the subsequent actions including possibly pushing an object, possibly a collision, possibly an object sliding frictionlessly as long as it can and then another collision, actually takes place in a 1-dimensional vector, not a 2-dimensional array. So it might be interesting to handle a penguin move by extracting a vector (in the form of a list) from the array, and replacing it with an updated list.

I haven't worked that all out yet but here is the bare beginning of my experimentation. There's a way to represent tiles:

data Tile = Empty | Tree | Mountain | House | Ice_Block | 
    Bomb | Heart | Edge
    deriving (Show)

Part of the confusion of learning Haskell is that, semantically, this isn't quite the equivalent of a set of enumerations, or of a set of class declarations. From what I can tell, this is more like a list of singleton factories -- constructors, where I've also derived them from Show, sort of the equivalent of mixing in a base class. But this is all an approximation, and Haskell is quite different than the other languages I'm most familiar with.

My next thought was that I wanted to be able to declare "base classes" so that, for example, I could have a Walkable class that comprised Empty and Tree. In Dylan I would do this by using classes, but there is different way: declaring a type-union of singletons. I think that this Haskell solution is more like the type-union. I looked in vain for an explicit type union. Instead I found class (which, in Haskell, does not correspond to a class in the sense that I'm used to, of a template for a run-time object that consists of data members and methods to operate on it, but a typeclass, something I clearly need to study more):

class Walkable a where
    walkable :: a -> Bool

And then this: which boils down to, I think, a function to determine whether a Tile is an instance of a Walkable typeclass:

instance Walkable Tile where
    walkable Empty = True
    walkable Tree = True
    walkable _ = False

Now I can write something like this (just a vague thought-in-progress at the moment):

slide :: [Tile] -> [Tile]
slide [] = error "slide empty list!"
slide (t) = error "single item list!"
slide (Empty:ts) = ts ++ slide ts

collide :: [Tile] -> [Tile]
collide [] = error "traverse empty list!"          
collide [Edge] = [Edge]
collide (Empty:ts) = ts
collide (Bomb:Mountain:ts) = [Empty, Empty] ++ ts          
collide (Heart:House:ts) = [Empty, House] ++ ts

step :: [Tile] -> Bool
step [] = error "step: empty list!"
step (t:_) = if walkable t then True else False

Then after sticking in a dummy main I can load this into GHCI and interact with it a little:

*Main> :t Tree
Tree :: Tile
*Main> step [Mountain, Empty, Empty, Tree, Edge]
*Main> step [Tree, Empty, Empty, Tree, Edge]
*Main> collide [Heart, Mountain]
*** Exception: arctic-slide.hs:(22,1)-(26,47): Non-exhaustive patterns in function collide
(Um, yeah, OK, I have work to do there)
*Main> collide [Heart, House]
*Main> slide [Empty, Empty, Empty, Empty, Mountain]
*** Exception: single item list!

Anyway, that's not exactly what I want to do -- really, I want the functions to actually return a new list of the same length, so I'll have to build it up as I recurse down the list -- maybe in the List monad? But it's a start on the whole basic concept of matching on the "types" of my tiles in a "vector," such as it is. That whole bit with walkable -- which I admit I don't quite understand yet -- seems like far too much conditional logic when I really just want to pattern-match on a type union of Tile. In other words, I want to write something like this (not valid Haskell):

union Walkable = Empty | Tree

step (Walkable:_) = True

That's a small example, but I have several other type union classes I need to use to categorize the tiles, so I have an incentive to make that as clear and simple as possible. It seems like I'm still fighting with Haskell's idioms here. Clearly, as they say, more research is needed...


Anonymous said...

Hi Paul,

I work with the CodeEval team and noticed you do a lot of work in Haskel. We're trying to get the word out that CodeEval now supports the Haskell community and we'd love to invite everyone to join. CodeEval is a great place to compete against fellow developers as well as have fun solving challenges.

Please let your friends know or tweet about it!


Twan van Laarhoven said...

Some tips:

slide (t) = error "single item list!"

The pattern (t) matches any list, you are looking for [t].

Instead of using if_then_else, use guards:

step :: [Tile] -> Bool
step [] = error "step: empty list!"
step (t:_) | walkable t = True
step (t:_) | otherwise = False

Or just

step (t:_) = walkable t

or even

step = walkable . head

If you really want to write this as a patter, there are two options:
1. use view patterns:

{-# LANGUAGE ViewPatterns #-}
step (walkable -> True : _) = True

2. change the datatype

data WalkableTile = Empty | Tree
data UnwalkableTile = Mountain | House | Ice_Block | Bomb | Heart | Edge
data Tile = Walkable WalkableTime | Unwalkable UnwalkableTile

Also, your Walkable class doesn't add much, it could just be a stand alone function walkable :: Tile -> Bool.

Finally, you should not unnecessarly raise errors, for example why isn't slide [] just []?

Paul Potts said...

Hi Apple,

Happy to share. Although I don't so much "do a lot of work in Haskell" as "frustrate myself dabbling in Haskell," at least at the moment, but I'm trying to change that. Thanks!

Paul Potts said...

T v. L, thanks very much for your help. It is embarrassing being such a beginner but I am very happy to get pointers. The books and tutorials are frustrating because there seems to be a gap between very simple program tailor-made for Haskell implementation, that they cover, and slightly more complicated program, without a good bridge between the two other than trying to read the code for much bigger published Haskell programs.

I am interested in the ViewPatterns -- I had not heard of those yet. Today I will be seeing if I can get the list monad working to collect up the altered lists.

You are right about the Walkable class, but there are some other classes that have more members, but they also overlap membership. That's probably a very un-Haskellish way to do it since it introduces multiple possible matches, except that I know Haskell evaluates the patterns in strict order. See the earlier Dylan code for what I mean. In Dylan I'm relying on the runtime to check for matches in order from less specific to more specific, and it seems to work OK, but I don't have a "catch everything" case deliberately -- since if all the methods don't match, I want a run-time error, as it indicates a design error upstream.

BMeph said...


I think the "more Haskellish" way to indicate a design error would be to have a compile-time error, not a run-time one. Of course, that only works when you are knowingly "doing it wrong," but still, there it is.

@Twan v. L.:

The second part of the step definition that starts "step (t:_) |..." should be all blanks up to that "|" part.