29 June 2013

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.


Jeff Licquia said...

Hi! Fellow Haskell newbie here, so please don't take this as "advice from the sages" as much as "blatherings from the potentially confused".

I was fascinated by the series of blog posts, mostly because your next_board function bothered me. It seemed to me like it did too much, and could be factored down a bit more. In my experience, Haskell is about splitting actions down to little nubs, and re-composing them in fancy ways, and it seemed that next_board could do that.

So first I factored out the multiple-return-value part:

next_board :: Board -> Pos -> Dir -> ( Bool, Board )
next_board board pos dir =
let ( penguin_could_move, updated_view ) = step $ view board pos dir
in ( penguin_could_move, update_board_from_view board pos dir updated_view )

After cutting-n-pasting my way to a working update_board_from view, I recognized that there are basically two operations: applying a view to a row forwards, and applying a view to a row backwards. That looked like this:

apply_view_to_row :: [Tile] -> Int -> Bool -> [Tile] -> [Tile]
apply_view_to_row orig pos True update =
take ( pos + 1 ) orig ++ ( init update )
apply_view_to_row orig pos False update =
( reverse ( init update ) ) ++ ( drop pos orig )

That takes care of moving East and West. For North and South, I noticed that the operations were exactly the same once you ignored the transposes and swapped the X and Y parameters. So:

apply_view_to_rows :: Board -> Int -> Int -> Bool -> [Tile] -> Board
apply_view_to_rows orig row pos is_forward update =
take row orig ++
nest ( apply_view_to_row ( orig !! row ) pos is_forward update ) ++
drop ( row + 1) orig

update_board_from_view :: Board -> Pos -> Dir -> [Tile] -> Board
update_board_from_view board pos dir updated_view
| is_eastwest
= apply_view_to_rows board ( posY pos ) ( posX pos ) is_forward updated_view
| otherwise
= transpose ( apply_view_to_rows ( transpose board ) ( posX pos ) ( posY pos ) is_forward updated_view )
where is_forward = elem dir [East, South]
is_eastwest = elem dir [East, West]

There's probably more interesting refactorings that could be done, but this looks a lot better to me.

Thanks for the brain teaser!

Paul Potts said...

Thanks, Jeff! Some good ideas there. I was not really happy with the original functions. I had it in mind that I wanted to come back and work on them later, but once it worked I wanted to push on first to get to the point where I could exercise the game play. I am hoping there will be a major simplification possible by moving to an array type. It seems like there should be a way to express extracting or replacing a whole (or partial) row or column from an a 2-D array in one line of code. If so then all the game logic outside of pretty-printing and maybe a GUI ought to fit on a page, and read as simple as the concept is.

Amy de Buitléir said...

Since you're implementing this game at least partly as a learning exercise, you may not be interested in using any other libraries. However, I do have a library for working with all kinds of grids/tiles for board games. You can install it using the command "cabal install grid".

https://github.com/mhwombat/grid (Github)
https://github.com/mhwombat/grid/wiki (userguide)