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

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.


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..]

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}]

Tags:

Haskell

Recent Posts