26 June 2013

The Polar Game in Haskell, Day 2

Another short day since I had several phone interviews. Thanks to the folks who left comments!

I got a little further today; I feel like I'm starting to understand Haskell's data handling a little bit better. It's a cliché but I think the hard part is un-learning, and understanding what something like this doesn't do. So here's where it stands now -- not finished by any means, but coming along, with painful slowness as I continue to learn:

data Dir = North | East | South | West
    deriving (Show, Eq)

data Pos y x = Pos Int Int
    deriving (Show, Eq)

-- N.B.: capitalization of initial letters in posY, posX is
-- semantically important!
posY ( Pos y x ) = y
posX ( Pos y x ) = x

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

-- Different types of tiles have different properties in
-- different interaction contexts: 

-- The penguin can walk through empty tiles or trees (forest)
walkable :: Tile -> Bool
walkable t = ( t == Empty ) || ( t == Tree )

-- But everything except empty tiles will block sliding objects
blocking :: Tile -> Bool
blocking t = ( t /= Empty )

-- A subset of tiles are movable (and will slide until blocked)
movable :: Tile -> Bool
movable t = ( t == Bomb ) || ( t == Heart ) || ( t == Ice_Block )

-- A subset of tiles aren't movable; note that this set
-- overlaps blocking and that Tree is both walkable and fixed
fixed :: Tile -> Bool
fixed t = ( t == House ) || ( t == Mountain ) || ( t == Edge )

That all should be fairly non-controversial, I think. The predicate approach to classifying tiles in different contexts may actually make more sense in Haskell, given that I can then use these predicates as guards. The replacement for a simple struct, Pos, still feels awkward -- I haven't really dug into whether it could be improved with record syntax, or some other technique. For now it's there because it works.

All the beginner tutorials say "don't use arrays, don't use arrays, don't use arrays!" At least not until I reach the stage where I need to optimize the implementation. So I'll try that. Let's try a list, and I'll extract "slices" from it, lists starting at a given Pos going in one of four different directions. Eventually I want the slice function to terminate the slices with Edge tiles that aren't actually stored in the list. So... I have to think about this some more, but here's a single case, sort of taken care of:

type Board = [[Tile]]

slice :: Board -> Pos y x -> Dir -> [Tile]
slice board pos East = drop ( posX pos )
    $ head $ drop ( posY pos ) board
slice _ _ _ = error "slice: not handled yet!"

I don't have slide finished, but here's a version of collide that works, at least a little:

collide :: [Tile] -> [Tile]
collide (t:(Empty:ts)) | movable t =
    [Empty] ++ collide (t:ts)
collide (Bomb:(Mountain:ts)) = [Empty, Empty] ++ ts
collide (Heart:House:ts) = [Empty, House] ++ ts
collide (_) = error "collide: unexpected case!"

The nested pattern (Bomb:(Mountain:ts)) was sort of a flash of inspiration -- but it appears that maybe both this version and the (Heart:House:ts) version work the same -- I think -- so perhaps it's kind of pointless. It seemed to go along with the "destructure it the way you would structure it" idea, although I would normally not build a list out of cons cells unless it was irregular in some way.

Here's the penguin step function, returning True if the penguin can move onto the tile at the head of the list:

step :: [Tile] -> ( Bool, [Tile] )
step [] = error "step: empty list!"
step ts = if walkable (head ts) then ( True, ts )
                                else ( False, collide ts )

And there's a move, which "absorbs" the case where the penguin is turned to face a different direction. It's not really done; the idea is that it will give back the board, basically generating a new world. For now we kind of punt on the question of how to rebuild the board out of the existing board and the modified "slice" -- and so the I just return a list as the first element of the tuple. In the first case where the penguin hasn't moved, that doesn't actually make sense, but it satisfies GHC for now (wow, she's kind of a harsh mistress, but you've got to love those thigh-high black leather boots!)

move :: Board -> Pos y x -> Dir -> Dir ->
    ( [Tile], Pos y x, Dir, Dir )
move board pos move_dir penguin_dir =
    if move_dir /= penguin_dir
    then ( head board, pos, move_dir, move_dir )
    else ( collide $ slice board (Pos 1 0) penguin_dir,
        pos, penguin_dir, penguin_dir )

Boy, that's tuple-icious... not sure I like it, but it's a start. So:

*Main> walkable Tree
*Main> :t Pos
Pos :: Int -> Int -> Pos y x
*Main> let slice = [Heart, House]
*Main> collide slice
*Main> let slice = [Bomb, Empty, Mountain]
*Main> collide slice
*Main> let board = [[Empty, Tree, Empty, Edge],
    [Bomb, Empty, Mountain, Edge]]
*Main> move board (Pos 1 0) West East
([Empty,Tree,Empty,Edge],Pos 1 0,West,West)
*Main> move board (Pos 1 0) East East
([Empty,Empty,Empty,Edge],Pos 1 0,East,East)

More tomorrow if I can manage it! Oh, and it's here, such as it is: https://github.com/paulrpotts/arctic-slide-haskell


BMeph said...

I'm pretty sure that "data Pos y x = ..." line doesn't do what you think it does. Unless, you don't mind people using "Pos String Double" types in their code.

I like watching the process of a programmer getting a grip on what Haskell can, can't, does and doesn't do - please, keep it up!

Paul R. Potts said...

Thanks, BMeph. I am still wrestling with what "data" actually does. There are lots of examples that show using it but the only thing I've seen that strictly describes what it does is the formal language definition, and I struggle with the formal semantics a little.

Unknown said...

I would suggest "data Pos = Pos { posX :: Int, posY :: Int}" instead. This constructs the posX and posY for you automatically, and removes the two type parameters x and y, which like BMeph said, you don't really want.

Paul R. Potts said...

Thanks, Noah. I had moved to Pos Int Int. I'd like to be rid of having to write getters. If you have a minute, do you think you could explain what the type parameters are for/do? Not explain like I'm five, but like I'm more accustomed to C, Java, Dylan, or Scheme.

Paul R. Potts said...

I was just reading this http://echo.rsmw.net/n00bfaq.html

which talks about the different namespaces that the parts of the data declaration use, but that doesn't seem to tell the whole story, and I'm still looking for that whole story on "data."

Paul R. Potts said...

If I can collect up enough pieces and get to the point where I feel I really understand all the options, I am volunteering to write "data for noobs" or some such.

Yukarin-chan said...

I am just going to describe the default Haskell98 syntax, GADTs and records and empty data types change things, but aren't important at first. (Though in someways the syntax for GADTs is clearer. I often find my self using it even when it is unnecessary.)

Well with a data declaration you are defining a 'type constructor' on lhs of the = and 1 or more 'Data constructors' on the right hand side.

So the simplest possible data declaration is:

data T = U

Defining a constant 'type constructor' T, and a constant 'data constructor'. Note that the type constructor and the data constructor are in different namespaces so they can but do not have to be the same lexicographically.

In fact the Haskell type () the 0-tuple is defined as:

data () = ()

The next complication is that you can have multiple Data constructors for the same type:

data Bool = True | False

The | is meant to be reminiscent of 'or' a Bool can be either True or False.

Now the next complication is that 'data constructors' can be 'higher-typed', like your Pos example:

data Pos = Pos Int Int

This means that the data constructor Pos has type Int -> Int -> Pos. So in order to construct an element of the type Pos (type namespace) we use the Pos (data namespace) on two Ints

Pos 3 4 :: Pos

Or the type of Peano natural numbers, which are hideously inefficient but mathematically simple.

data Peano = Zero | Succ Peano
So Zero is an constant data constructor, but Succ is a function from Peano to Peano.

Now you can also make the type constructor a function and not a constant, but the syntax is a little different. We put (type) variable names after the Type constructor, and the compiler figures out their "type" (really kind) for us. For example lets look at Maybe:

data Maybe a = Nothing | Just a

This means that the Maybe type constructor is not usable as a type by its self. Its 'higher-kind-ed' it takes a type, and gives you a new type. So Maybe isn't a type, but Maybe Int is. The compilar sees that you are using a directly as a type, and so gives it Kind *, which means Maybe has kind * -> *. (* is just the kind notation for the kind of a actual type, (as opposed to a type function).

Now type variables, despite their name, do not actually have to have kind *.

So if you took out the record syntax sugar, StateT's data declaration would be writen:

data StateT s m a = StateT (m (a, s))

where s and a have kind *, but m has kind * -> *.

Does that help at all?

Paul R. Potts said...

Yukarin-chan, that helps a lot! It seems to put together in one place bits and pieces I've seen in several different places. I will study on that for a while -- it usually takes me a couple times, and then actually using it more than once, to really understand something in Haskell. But I'm getting there!

Jedaï said...

Since you're familiar with Java, Maybe a is analog to generic types in Java. This is in fact very common in Haskell though we call it polymorphism.