Haskell如何遍历二维列表，筛选后输出一维列表？

Question

我曾以为自己在学习 Haskell 时很顺利，直到...

我有一个 [[Int]]

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

还有一个数据类型：

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

根据输入的 tiles，我一直在尝试输出一个 [Coord]，使得只有当 tiles 的值为1时才会生成一个 Coord，并且Coord将保存其在2D列表中的位置。

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

我尝试过将[[Int]]转换为[Int]，方法如下：

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

但是之后，我不确定如何传递索引。我想，如果我可以在“折叠的瓦片”上进行映射，输出一个元组（值，索引），那么我就可以轻松地解决其余的问题。

更新 如果有人感兴趣，我已经让它正常运行了，并在这里提供演示（包括源代码和链接到GitHub）！由于这是我第一次使用 FP 编写游戏，我需要花更多时间理解每个答案。非常感谢！

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

- Kenny Cason

Answer 1

这是列表推导式大放异彩的地方。

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

或者你可以选择等效的do符号（因为list是一个monad），这需要导入Control.Monad（用于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

为了帮助理解，这个后续函数的工作方式类似于以下的Python函数。

为了帮助理解，这个后续函数的工作方式类似于以下的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 符号在列表单子中非常方便，我认为值得掌握！

---

在这两个例子中，我都使用了这个定义。

enumerate = zip [0..]

- kqr

Answer 2

这里有一个简单的解决方案（不能保证对于10000x10000大小的瓷砖是可行的，这需要您自己检查 ;)）

这种方法通常在Haskell中采用自上而下的开发方式。您可以思考：blackBox应该做什么？对于每一行的tiles，它应该收集该行中值为1的tiles的Coord，并将它们连接起来。

这给您另一个函数blackBoxRow，只针对行。它应该做什么？从行中删除零，并将其余部分包装在Coord中，因此需要filter和map。此外，您还想保留行号和列号，因此您需要将tiles与它们各自的坐标连接起来。

这就给了你：

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

结果是：

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

- fjarri

---

非常感谢！我尝试了这个方法，它起作用了 :) 我需要更仔细地阅读它（以及其他答案），以进一步理解它。 - Kenny Cason

Answer 3

我认为，你可以对你的二维列表进行一系列的转换。我们需要的第一个转换是能够将列表中的1替换为更有用的内容，比如它所在的行：

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

我们现在可以使用zipWith和[1..]来执行第一步：

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

这里方便的是，即使矩阵不是正方形，它也能工作，并且一旦矩阵结束，它就会停止。

接下来我们需要指定列号，这里我会同时进行几个步骤。这将生成坐标元组，但其中有无效的元组，其中r == 0（这就是为什么我使用了[1..]，否则，您将失去第一行），所以我们要过滤掉它们。接下来，我们使用uncurry Coord创建一个接受元组的函数，然后在其上使用flip，然后将此函数映射到元组列表上。

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

我们可以构建我们的assignCols：

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

这使我们能够构建最终的函数。

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

你可以通过一些 eta reduction 来压缩这段代码。

如果你需要从 0 开始的索引坐标，你可以修改这个解决方案来实现。

- bheklilr

Answer 4

快速而简单的解决方案：

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

< p > zip 将瓷砖值（我称之为k）与 x 和 y 坐标配对（我们正在处理列表，因此如果需要它们，则必须添加索引）。mapMaybe 很方便，因此我们可以在单个步骤中映射（以构建 Coords）和过滤（以删除零瓷砖）。concatMap 在这里也执行了两件事：它映射一个生成列表的函数（括号内的匿名函数），然后将其展平。一定要检查中间函数和结果的类型，以获得更清晰的转换图片。

- duplode

Answer 5

这里使用列表推导式实现。

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

- Ankur

---

这将只选择每行中第一个“1”瓷砖。elemIndex是罪魁祸首。 - duplode

@duplode：也许我没有理解这个问题。那么当有一个具有多个1的瓦片，例如[1,1,1]时，它应该为每个1生成多个Coord吗？ - Ankur

这似乎是OP的意图 - 就如同一个游戏棋盘一样，其值为标志，指示一个瓷砖是否被占用。 - duplode

这看起来非常优美 :) - Kenny Cason

Answer 6

只要我们在收集答案，这里还有一个：

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      

解释：

这将在每行内分配x索引：

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

然后我筛选每一行，只保留有 1 的元素，然后将 1 删除（因为它已经没有用了）：

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

这会得到一个类型为[[Int]]的结果，这些是曾经有1的x所在的行。接着，我会将每一行中的y进行映射，翻转成(x, y)而不是(y, x)。最后一步，我将所有的行扁平化成一个列表，因为我不再需要将它们分开保留：

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

最后，我通过使用map将Coord映射到每个元素上进行转换。uncurry是必要的，因为Coord不接受元组作为参数。

- Andres F.