17

我以为我在 Haskell 学习中一帆风顺，直到...

我有一个 [[Int]]

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

和数据类型：

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

根据输入tiles，我一直在尝试输出 a [Coord]，这样 aCoord仅在值为tiles1 时生成，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

4

6 回答 6

18

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

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（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

为了帮助理解，后一个函数的工作方式类似于以下 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我认为，list monad 的符号对于处理列表非常方便，所以值得一试！

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

enumerate = zip [0..]
于 2013-10-11T06:18:03.663 回答
2

快速而肮脏的解决方案：

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

s将ziptile 值（我指的是k）与 x 和 y 坐标配对（我们正在处理列表，因此如果需要它们，我们必须添加索引）。很方便，因此我们可以在一个步骤中mapMaybe进行映射（以构造）和过滤（以删除零图块）。这里还做了两件事：它映射一个函数（括号内的匿名函数）生成一个列表列表，然后将其展平。请务必检查中间函数的类型和结果，以便更清楚地了解转换。 CoordsconcatMap

于 2013-10-11T02:20:22.140 回答
2

在这里，使用列表推导。

blackBox :: [[Integer]] -> [Coord]
blackBox ts = [Coord x y | (t,y) <- zip ts [0..], (e,x) <- zip t [0..], e == 1]
于 2013-10-11T05:52:51.563 回答
2

这是一个简单的解决方案（不保证它适用于tiles10000x10000 的大小，这需要您检查；）

与 Haskell 中的往常一样，这种方法是自上而下的开发。你想：应该blackBox怎么办？对于它的每一行，tiles都应该为该行收集Coord瓦片的 s 1，并将它们连接起来。

这为您提供了另一个功能，blackBoxRow，仅适用于行。它应该怎么做？从行中删除零，并将其余部分包装在Coords 中，因此有filterand then map。此外，您还想保留行号和列号，因此您可以将贴图与其各自的坐标连接起来。

这给了你：

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}]
于 2013-10-11T02:10:30.410 回答
2

在我看来，您可以通过一系列转换来放置您的 2D 列表。我们需要的第一个是可以用1更有用的东西替换列表中的，例如它的行：

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

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

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

这样做的方便之处在于，即使矩阵不是方形的，它也会起作用，并且它会在矩阵出现时立即终止。

接下来我们需要分配列号，这里我将一次性执行几个步骤。这使得坐标的元组，但是有无效的 where r == 0（这就是我使用 的原因[1..]，否则你会丢失第一行），所以我们将它们过滤掉。接下来，我们uncurry Coord创建一个接受元组的函数，然后我们在它上面使用翻转，然后将这个东西映射到元组列表上。

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 减少来压缩它。

如果你想要 0 索引坐标，我会让你修改这个解决方案来做到这一点。

于 2013-10-11T02:11:08.153 回答
0

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

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

然后我过滤每一行以仅保留带有 a 的元素1，然后删除1（因为它不再有用）：

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

这会产生一些 type [[Int]]，这是 s 曾经是 s 的x行1。然后我在每一行中映射ys ，翻转对所以我留下(x,y)而不是(y,x). 作为最后一步，我将行展平为一个列表，因为我不再需要将它们分开：

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

map最后，我通过ping转换每个元素Coord。uncurry是必要的，因为Coord不将元组作为参数。

于 2013-10-12T22:26:48.867 回答