The Polar Game in Haskell, Day 4 1/2: Folding a Penguin

So, just a quick update today. While I was cooking bacon this morning I looked at comments and tried to implement an idea I had last night. Roland suggested I could get rid of Edge. I had already been asking myself this. Using a special flag value for the edge-of-board case came from the Objective-C version where I wanted to avoid reading tiles outside the bounds of the board array. When using lists there is a built-in termination condition, so Edge is gone completely.

Roland also suggested a simplified next_ppos, like so:

next_ppos :: Pos -> Dir -> Pos
next_ppos pos dir = Pos ( posY pos + fst step ) ( posX pos + snd step )
    where step = delta dir
          delta East = ( 0, 1 )
          delta South = ( 1, 0 )
          delta West = ( 0, -1 )
          delta North = ( -1, 0 )

So that's in there now. Thanks, Roland!

The next thing I wanted to do is get rid of that ugly test code with all the nested calls to next_world. I was re-reading Learn You a Haskell and it occurred to me that this sort of thing -- distilling a list -- is what folds are for. And then, a minute later, that I don't actually want to fold the worlds down to one final world -- I want to capture all the intermediate worlds as we process a list of moves. And that's what a scan is for. So we're conducting surveillance on the penguin as he goes about his business. GHCI tells me that the type of scanl is (a -> b -> a) -> a -> [b] -> [a]. So I'm calling it with a function that takes a World and a Dir and returns a World. That's the (a -> b -> a) part. Then it gets an initial World, that's the a, and a list of elements of type Dir, that's the [b], and returns a list of elements of type World, that's [a].

moves_to_dirs :: [(Dir, Int)] -> [Dir]
moves_to_dirs [] = []
moves_to_dirs (m:ms) = replicate ( snd m ) ( fst m ) ++ moves_to_dirs ms

moves_board_1 = [(East,21),(South,2), (East,3),(North,2),(West,2)]

move_sequence :: [(Dir,Int)] -> [World]
move_sequence repeats = scanl next_world init_world steps
    where steps = moves_to_dirs repeats

main :: IO ()
main = do
    mapM_ putStrLn pretty_worlds
    where worlds = move_sequence moves_board_1

And that gives me the whole shebang, ending in:

penguin @: Pos {posY = 0, posX = 22}, facing: West, hearts: 3
tr __________________________________________tr _______________ic ______
tr ___bo ___mt ___he ic he ___________________________tr ______tr ______
tr _____________________________________________he _________mt ho ______
tr tr ____________tr ___________________________________________________

penguin @: Pos {posY = 0, posX = 21}, facing: West, hearts: 3
tr __________________________________________tr ic _____________________
tr ___bo ___mt ___he ic he ___________________________tr ______tr ______
tr _____________________________________________he _________mt ho ______
tr tr ____________tr ___________________________________________________

Oh, if you just want to see the final result, foldl will work here. Their types are identical, except that foldl returns a single a (in this case, a World) instead of a list of elements of type World. So a function to make use of that just returns a single World, but everything else is the same. Like so:

move_sequence' :: [(Dir,Int)] -> World
move_sequence' repeats = foldl next_world init_world steps
    where steps = moves_to_dirs repeats

And then I can display both:

main :: IO ()
main = do
    mapM_ putStrLn pretty_worlds 
    putStrLn pretty_final_world
    where worlds = move_sequence moves_board_1
          final_world = move_sequence' moves_board_1
          pretty_worlds = map pretty_world worlds

I like it -- examples of fold and scan that are a little more complex than the usual textbook examples. Personally I'd rather read more of those and less about how we can implement some simple math operation that can be trivially implemented in a dozen other, more readable ways.

Oh, and it's not thoroughly tested or finished by any means, but if you'd like to play with this code, it's on github now: https://github.com/paulrpotts/arctic-slide-haskell. Comments are welcome as always.