Haskell Iterar en la lista 2d, filtro, lista de salida 1d

Question

Pensé que estaba navegando suavemente en mis estudios de Haskell, hasta que ...

Tengo un [[Int]]

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

y un tipo de datos:

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

Basándome en los tiles entrada, he estado intentando generar un [Coord] , de modo que un Coord solo se genera cuando el valor de los tiles es 1, y el Coord almacenará su posición en la lista 2d:

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

He intentado cosas como convertir primero [[Int]] a [Int], a través de:

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

pero después de eso no estoy muy seguro de cómo pasar los índices. Supongo que si pudiera hacer un mapa sobre los "mosaicos plegados", generando una tupla (valor, índice), podría averiguar fácilmente el resto.

actualización En caso de que alguien esté interesado, lo puse en funcionamiento y aquí hay una demostración (con el código fuente y el enlace a GitHub). Tendré que tomarme más tiempo para comprender cada una de las respuestas, ya que esta es la primera vez que programo un juego con FP. ¡Muchas gracias!

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

Answer 1

A mi modo de ver, puedes poner tu lista 2D a través de una serie de transformaciones. El primero que necesitaremos es uno que pueda reemplazar el 1 en su lista con algo más útil, como su fila:

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

Ahora podemos usar zipWith y [1..] para realizar el primer paso:

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

Lo práctico de esto es que funcionará incluso si la matriz no es cuadrada, y termina tan pronto como lo hace la matriz.

A continuación, debemos asignar el número de columna, y aquí haré algunos pasos a la vez. Esto hace que las tuplas de las coordenadas, pero hay inválidas donde r == 0 (es por eso que usé [1..] , de lo contrario, perderá la primera fila), así que las filtramos. A continuación, uncurry Coord para hacer una función que tome una tupla en su lugar, y luego usamos voltear en ella, luego mapeamos esto sobre la lista de tuplas.

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

Y podemos construir nuestros assignCols :

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

Lo que nos permite construir la función final.

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

Podrías comprimir esto bastante con un poco de reducción eta también.

Si desea coordenadas con índice 0, le dejaré que modifique esta solución para hacerlo.

Answer 2

Aquí está, utilizando listas de comprensión.

blackBox :: [[Integer]] -> [Coord]
blackBox ts = [Coord x y | (t,y) <- zip ts [0..], (e,x) <- zip t [0..], e == 1]

Answer 3

Aquí hay una solución simple (no se garantiza que sea viable para los tiles de tamaño 10000x10000, eso es algo para que lo compruebe;)

El enfoque es, como es habitual en Haskell, un desarrollo de arriba hacia abajo. Piensas: ¿qué debería hacer blackBox ? Por cada fila de tiles , debe reunir los Coord s de las fichas con 1 para esa fila y concatenarlas.

Esto te da otra función, blackBoxRow , solo para filas. ¿Qué debería hacer? Elimine los ceros de la fila y envuelva el resto en Coord s, de modo que haya un filter y luego un map . También desea mantener los números de fila y columna, por lo que asigna mosaicos unidos con sus respectivas coordenadas.

Esto te da:

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

Resultados en:

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

Answer 4

Este es un lugar donde brillan las listas de comprensión.

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

O puede ir a la notación do equivalente (ya que la lista es una mónada), que requiere importar Control.Monad (para 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

Para ayudar a comprender, esta última función funciona como la siguiente función de Python.

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

do notación para la lista de la mónada es increíblemente útil para procesar listas, creo, ¡así que vale la pena envolver la cabeza!

En ambos ejemplos he usado la definición

enumerate = zip [0..]

Answer 5

Mientras recopilemos respuestas, aquí hay otra:

blackBox :: [[Int]] -> [Coord]
blackBox ts = map (uncurry Coord) xsAndYs
    where
        xsAndYs = concat $ zipWith applyYs [0..] x1s
        applyYs i = map (flip (,) i)
        x1s = map (map fst . filter ((==1) . snd)) xs
        xs = map (zip [0..]) ts      

Explicación:

Esto asigna los índices x dentro de cada fila:

xs = map (zip [0..]) ts

Luego filtro cada fila para mantener solo los elementos con un 1 , y luego suelto el 1 (ya que ya no es útil):

x1s = map (map fst . filter ((==1) . snd)) xs

Lo que resulta en algo de tipo [[Int]] , que son las filas con x s donde solía estar 1 s. Luego asigno los y s dentro de cada fila, cambiando los pares, así que me quedo con (x,y) lugar de (y,x) . Como paso final, alise las filas en una sola lista, ya que ya no necesito mantenerlas separadas:

xsAndYs = concat $ zipWith applyYs [0..] x1s
applyYs i = map (flip (,) i)

Finalmente convierto cada elemento por el map ping Coord sobre él. uncurry se necesita uncurry porque Coord no toma una tupla como argumento.

Answer 6

Solución rápida y sucia:

import Data.Maybe (mapMaybe)

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

blackBox :: [[Int]] -> [Coord]
blackBox = concatMap (/(y, xks) -> mapMaybe (toMaybeCoord y) xks)
    . zip [0..] . map (zip [0..])
    where
    toMaybeCoord :: Int -> (Int, Int) -> Maybe Coord
    toMaybeCoord y (x, k) = if k == 1
        then Just (Coord x y)
        else Nothing

La zip empareja los valores de los mosaicos (a los que me refiero como k ) con las coordenadas x e y (estamos tratando con listas, así que tenemos que agregar los índices si los necesitamos). mapMaybe es conveniente para que podamos mapear (para construir los Coords ) y filtrar (para eliminar los mosaicos cero) en un solo paso. concatMap también hace dos cosas aquí: asigna una función (la función anónima entre paréntesis) generando una lista de listas y luego la aplana. Asegúrese de verificar los tipos de funciones y resultados intermedios para obtener una imagen más clara de las transformaciones.