0

如何在使用单子时避免空间泄漏foldM？mapMState

去年的第 20 天代码出现有一个难题，即根据如何穿过迷宫的说明生成迷宫地图。例如，说明NN给出了迷宫

   |
   |
   *

（一条笔直的走廊往北两步），指示NNN(EE|WW)S给了迷宫

 +-+-+
 | | |
   |
   *

（向北走一点，然后向东然后向南或向西然后向南）。

我试图解决这个问题的方法包括有一个State单子，其中状态是Set所有走廊部分的状态（Door下面称为 s），值是您可以工作的位置列表。

如果你只是沿着一条走廊走Path，我foldM会沿着它走，更新当前位置。如果你在一个路口，沿着路口的每个分支，收集你最终到达的所有位置。

此代码在小测试输入上产生正确的结果，但在处理完整示例时存在巨大的空间泄漏。

分析表明它大部分时间都花在includeDoor.

所以，问题。

  1. 有空间泄漏吗？如果是这样，在哪里，你怎么知道。
  2. 我如何解决它？

（我认为正在发生的事情是 Haskell 并没有尽快将完全评估Door的 s 添加到 s 中Set。在这种情况下，我不想在任何地方有任何懒惰。）

（我将输入解析为一组二元素向量，这些向量指示每条指令要执行的步骤。该代码运行良好且快速。）

import qualified Data.Set as S

import Linear (V2(..))

import Control.Monad.State.Strict
import Control.Monad.Extra (concatMapM)

type Coord = V2 Integer -- x, y, with north and east incresing values (origin a bottom left)
data Door = Door Coord Coord deriving (Show, Eq, Ord)
type Doors = S.Set Door

data MazeSection = Path [Coord] | Junction [Maze] deriving (Show, Eq)
type Maze = [MazeSection]

type Mapper = State Doors [Coord]

makeDoor :: Coord -> Coord -> Door
makeDoor !a !b 
    | a < b = Door a b
    | otherwise = Door b a

emptyMap = S.empty

part1 maze = 
    do 
        let start = V2 0 0
        let doors = execState (mapMaze [start] maze) emptyMap
        print $ length doors

mapMaze :: [Coord] -> Maze -> Mapper
mapMaze !starts !sections =
    foldM (\heres section -> mapMazeSection heres section) starts sections

mapMazeSection :: [Coord] -> MazeSection -> Mapper
mapMazeSection !starts (Junction mazes) = 
    concatMapM (\maze -> mapMaze starts maze) mazes
mapMazeSection !starts (Path steps) = 
    mapM mapPath starts
    where mapPath start = foldM (\here step -> includeDoor here step) start steps

includeDoor :: Coord -> Coord -> State Doors Coord
includeDoor !here !step = 
    do let there = (here + step)
       let door = there `seq` makeDoor here there
       modify' (door `seq` S.insert door)
       return there
4

2 回答 2

0

在 Haskell 中很难检测到空间泄漏。我不是专家，但我听说 State monad 和空间泄漏存在很多问题。我通常避免State/StateT并使用IORef, MVarorTVar代替，但这会将其更改为IO. 您可以尝试的第一件事是添加!各种 let 绑定和类型定义。

data Door = Door !Coord !Coord
data Maze = Path ![Coord] | Junction ![Maze]

如果这不能解决问题，有一些工具可以帮助您查明它在本文中出现的位置。

其他资源

这里有一些其他资源可能会有所帮助。

于 2019-11-21T12:17:04.967 回答
0

原来，这不是空间泄漏！是我没有处理一些病态的输入。一旦我弄清楚如何处理它，它就奏效了，而且速度非常快。

于 2019-11-21T16:25:24.250 回答