Haskell Iterate over 2d list, filter, output 1d list

Question

I thought I was smooth sailing in my Haskell studies, until...

I have a [[Int]]

tiles = [[1,0,0]
        ,[0,1,0]
        ,[0,1,0]
        ]

and a data type:

data Coord = Coord
    { x :: Int
    , y :: Int 
    } deriving (Eq)

Based on the input tiles, I've been trying to output a [Coord], such that a Coord is only generated when the value of tiles is 1, and the Coord will store it's position in the 2d list:

blackBox :: [[Int]] -> [Coord]
blackBox tiles = <magic> 
-- given the above example I would expect:
-- [(Coord 0 0),(Coord 1 1),(Coord 1 2)]

I have tried things like first converting [[Int]] to a [Int], via:

foldTiles :: [[Int]] -> [Int]
foldTiles tiles = foldr (++) [] tiles

but after that I'm not really sure how to pass the indices along. I suppose if I could map over the "folded tiles", outputting a tuple (value, index), I could easily figure out the rest.

update In case anyone's interested, I got it working and here is a demo of it (with source code and link to GitHub)! I will have to take more time to understand each of the answers as this is my first time programming a game using FP. Thanks a lot!

http://kennycason.com/posts/2013-10-10-haskell-sdl-gameboy-boxxle.html

Answer 1

This is a place where list comprehensions shine.

blackBox tiles =
  [Coord x y                         -- generate a Coord pair
    | (y, row) <- enumerate tiles    -- for each row with its coordinate
    , (x, tile) <- enumerate row     -- for each tile in the row (with coordinate)
    , tile == 1]                     -- if the tile is 1

Or you could go for the equivalent do notation (since list is a monad), which requires importing Control.Monad (for guard.)

blackBox tiles = do
  (y, row) <- enumerate tiles    -- for each row with its coordinate
  (x, tile) <- enumerate row     -- for each tile in the row (with coordinate)
  guard (tile == 1)              -- as long as the tile is 1
  return (Coord x y)             -- return a coord pair

To aid with understanding, this latter function works like the following Python function.

def black_box(tiles):
    for y, row in enumerate(tiles):
        for x, tile in enumerate(row):
            if tile == 1:
                 yield Coord(x, y)

do notation for the list monad is incredibly handy for processing lists, I think, so it's worth wrapping your head around!

---

In both of these examples I have used the definition

enumerate = zip [0..]

Answer 2

Here's a simple solution (not guarantee that it's viable for tiles of size 10000x10000, that's something for you to check ;)

The approach is, as usual in Haskell, a top-down development. You think: what should blackBox do? For every row of tiles it should collect the Coords of the tiles with 1 for that row, and concatenate them.

This gives you another function, blackBoxRow, for rows only. What should it do? Remove zeros from the row, and wrap the rest in Coords, so there's filter and then map. Also you want to keep the row and column numbers, so you map tiles joined with their respective coordinates.

This gives you:

tiles :: [[Int]]
tiles = [[1,0,0]
        ,[0,1,0]
        ,[0,1,0]
        ]

data Coord = Coord {
    x :: Int
    ,y :: Int
} deriving (Eq, Show)

blackBox :: [[Int]] -> [Coord]
blackBox tiles2d = concat (map blackBoxRow (zip [0..] tiles2d))

blackBoxRow :: (Int, [Int]) -> [Coord]
blackBoxRow (row, tiles1d) = map toCoord $ filter pickOnes (zip [0..] tiles1d) where
    pickOnes (_, value) = value == 1
    toCoord (col, _) = Coord {x=col, y=row}


main = print $ blackBox tiles

Results in:

~> runhaskell t.hs
[Coord {x = 0, y = 0},Coord {x = 1, y = 1},Coord {x = 1, y = 2}]

Answer 3

The way I see it, you could put your 2D list through a series of transformations. The first one we'll need is one that can replace the 1 in your list with something more useful, such as its row:

assignRow :: Int -> [Int] -> [Int]
assignRow n xs = map (\x -> if x == 1 then n else x) xs

We can now use zipWith and [1..] to perform the first step:

assignRows :: [[Int]] -> [[Int]]
assignRows matrix = zipWith assignRow [1..] matrix

What's handy about this is that it'll work even if the matrix isn't square, and it terminates as soon as the matrix does.

Next we need to assign the column number, and here I'll do a few steps at once. This makes the tuples of the coordinates, but there are invalid ones where r == 0 (this is why I used [1..], otherwise, you'll lose the first row), so we filter them out. Next, we uncurry Coord to make a function that takes a tuple instead, and then we use flip on it, then map this thing over the list of tuples.

assignCol :: [Int] -> [Coord]
assignCol xs = map (uncurry (flip Coord)) $ filter (\(c, r) -> r /= 0) $ zip [1..] xs

And we can build our assignCols:

assignCols :: [[Int]] -> [Coord]
assignCols matrix = concatMap assignCol matrix 

which allows us to build the final function

assignCoords :: [[Int]] -> [Coord]
assignCoords = assignCols . assignRows

You could compress this quite a bit with some eta reduction, too.

If you want 0-indexed coordinates, I'll leave you to modify this solution to do so.