时间戳

首页 > 解决方案 > 带有 foldl 的列表列表并替换之前出现的元素？

haskell - 带有 foldl 的列表列表并替换之前出现的元素？

问题描述

我正在开发一个吃豆人游戏，我需要压缩迷宫。因此，例如，如果迷宫的一个走廊是：

[(1, Wall),(1, Wall),(1, Wall),(1, Empty),(1, Food),(1, Food),(1, Empty),(1, Wall)]

我们压缩它以避免重复，所以它看起来像这样：

[(3, Wall),(1, Empty),(2, Food),(1, Empty),(1, Wall)]

到目前为止，我已经以这种格式压缩了迷宫：

[
  [(5, Wall)],
 [(1, Wall), (2, Food Little), (1, Food Big), (1, Wall)],
  [(1, Wall), (3, Food Little), (1, Wall)],
  [(1, Wall), (3, Food Little), (1, Wall)],
 [(1, Wall), (1, Food Little), (1, Food Big), (1, Food Little), (1, Wall)],
  [(5, Wall)],
]

但正如我们所见，有些走廊（线）是重复的。所以为了避免它，最终压缩的迷宫需要看起来像这样：

[ [(5, Wall)], 
 [(1, Wall), (2, Food Little), (1, Food Big), (1, Wall)],
[(1, Wall), (3, Food Little), (1, Wall)],
  Repeat 2,
 [(1, Wall), (1, Food Little), (1, Food Big), (1, Food Little), (1, Wall)],
  Repeat 0,
]

因此，如果迷宫中已经出现过走廊，它将返回重复 n，其中 n 是它第一次出现的位置。

我考虑过 foldl 来遍历列表，但同时我可能需要一个 aux 函数，但我在开发它时遇到了麻烦，因为我只是 haskell 和编程 xd 的初学者所以我接受任何建议、提示、文章可以帮助我！太感谢了！

如果可能有帮助，这里是使用的类型和数据类型：

type Instructions = [Instruction]
data Instruction = Instruct [(Int, Piece)]
               | Repeat Int

标签： haskellfold

解决方案

给定数据类型：

type Instructions = [Instruction]
data Piece = Wall | Food Size
data Size = Little | Big
data Instruction = Instruct [(Int, Piece)]
                 | Repeat Int

和一个部分压实的迷宫：

maze1 :: [[(Int, Piece)]]
maze1 =
  [ [(5, Wall)],
    [(1, Wall), (2, Food Little), (1, Food Big), (1, Wall)],
    [(1, Wall), (3, Food Little), (1, Wall)],
    [(1, Wall), (3, Food Little), (1, Wall)],
    [(1, Wall), (1, Food Little), (1, Food Big), (1, Food Little), (1, Wall)],
    [(5, Wall)]
  ]

您可以使用递归压缩它。在每个递归步骤中，您需要检查下[(Int, Piece)]一项是否已经输出（这样您就可以决定它是否是重复的），为此，您需要跟踪您已输出的指令列表，所以远的。最简单的方法是将您已经生成的指令作为递归函数的参数，因此您的递归函数将如下所示：

compact' :: Instructions -> [[(Int, Piece)]] -> Instructions
compact' done (x:xs) = ...

该定义的右侧将x :: [(Int, Piece)]使用我们已经完成的指令列表来处理下一个，即done :: Instructions.

我们将通过将next指令添加到列表中done并递归来做到这一点：

compact' done (x:xs) = compact' (done ++ [next]) xs

然后，当我们用完输入时，返回完整列表：

compact' done [] = done

剩下的唯一步骤是定义next. 我们可以使用elemIndexfromData.List来查找xin的位置done，如果它是重复的，就像这样：

where next = case elemIndex (Instruct x) done of
               Just pos -> Repeat pos

如果找不到，我们只需将其添加为Instruct指令：

               Nothing -> Instruct x

首先，我们将编写一个compact以空开头的递归done = []：

compact :: [[(Int, Piece)]] -> Instructions
compact input = compact' [] input

可以更简单地写成：

compact = compact' []

要编译完整的程序，我们需要向deriving数据类型添加适当的导入和一些子句。（Eq需要在列表中查找指令done。）完整的程序如下所示：

import Data.List

type Instructions = [Instruction]
data Piece = Wall | Food Size deriving (Show, Eq)
data Size = Little | Big deriving (Show, Eq)
data Instruction = Instruct [(Int, Piece)]
                 | Repeat Int
                 deriving (Show, Eq)

maze1 :: [[(Int, Piece)]]
maze1 =
  [ [(5, Wall)],
    [(1, Wall), (2, Food Little), (1, Food Big), (1, Wall)],
    [(1, Wall), (3, Food Little), (1, Wall)],
    [(1, Wall), (3, Food Little), (1, Wall)],
    [(1, Wall), (1, Food Little), (1, Food Big), (1, Food Little), (1, Wall)],
    [(5, Wall)]
  ]

compact :: [[(Int, Piece)]] -> Instructions
compact = compact' []
  where compact' :: Instructions -> [[(Int, Piece)]] -> Instructions
        compact' done (x:xs) = compact' (done ++ [next]) xs
          where next = case elemIndex (Instruct x) done of
                         Just pos -> Repeat pos
                         Nothing  -> Instruct x
        compact' done [] = done

main = print (compact maze1)

这不是一个非常有效的实现，因为它运行在二次时间搜索和重新搜索done列表中添加的每个元素，并使用done ++ [next]线性时间追加元素。但是，您必须编写一个非常庞大的吃豆人游戏才能让这种糟糕的性能成为一个真正的问题。

使用 aMap来有效查找位置的替代实现可能如下所示。它展示了一种用于递归的替代技术，我们不是建立一个done列表然后在最后返回它，而是建立一个done映射，但单独返回列表，逐个元素地返回，而不是等到最后。这里的类型级技术（例如，Compact a由 type 参数化的定义a）稍微高级一些，但您可能会发现这种方法很有趣。我认为大多数 Haskell 程序员会认为这是一个合理的生产级实现（尽管有些人可能会使用mapAccumL而不是递归）。无论如何，这可能是我用“真实代码”编写它的方式。

import Data.List
import qualified Data.Map as Map

-- A general representation for lists of repeatable objects
type Compact a = [Repeatable a]
data Repeatable a = First a | Repeat Int deriving (Show)

data Piece = Wall | Food Size deriving (Show, Eq, Ord)
data Size = Little | Big deriving (Show, Eq, Ord)

compact :: (Ord a) => [a] -> Compact a
compact = compact' 0 Map.empty
  where compact' :: (Ord a) => Int -> Map.Map a Int -> [a] -> Compact a
        compact' pos done (x:xs) = next : compact' (pos + 1) done' xs
          where (next, done') = case Map.lookup x done of
                  Just pos -> (Repeat pos, done)
                  Nothing  -> (First x, Map.insert x pos done)
        compact' _ _ [] = []

maze1 :: [[(Int, Piece)]]
maze1 =
  [ [(5, Wall)],
    [(1, Wall), (2, Food Little), (1, Food Big), (1, Wall)],
    [(1, Wall), (3, Food Little), (1, Wall)],
    [(1, Wall), (3, Food Little), (1, Wall)],
    [(1, Wall), (1, Food Little), (1, Food Big), (1, Food Little), (1, Wall)],
    [(5, Wall)]
  ]

main = do
  print (compact maze1)
  print (compact ["it","is","what","it","is"])

mapAccumL版本如下所示：

compact :: (Ord a) => [a] -> Compact a
compact = snd . mapAccumL step (0, Map.empty)
  where step (pos, done) x = ((pos + 1, done'), next)
          where (next, done') = case Map.lookup x done of
                  Just pos -> (Repeat pos, done)
                  Nothing  -> (First x, Map.insert x pos done)

推荐阅读