使用 `mapM` 和 `foldM` 在 `State` monad 上避免 space 泄漏

Question

在 State monad 上使用 foldM 和 mapM 时如何避免 space 泄漏？

去年的 Advent of Code day 20 有一个难题，即根据如何走过迷宫的说明生成迷宫地图。例如，指令 NN 给出了迷宫

   |
   |
   *

（向北走两步的直线走廊），说明NNN(EE|WW)S给出了迷宫

 +-+-+
 | | |
   |
   *

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

我试图解决这个问题的方法涉及到有一个 State monad，其中状态是所有走廊部分的 Set（下面称为 Doors），值是您可以工作的职位列表。

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

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

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

所以，问题。

有space泄漏吗？如果有，在哪里，怎么知道。
我该如何解决？

（我认为发生的事情是 Haskell 并没有尽快严格地将完全评估的 Door 添加到 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

Answer 1

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

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

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

其他资源

以下是一些可能有用的其他资源。

Answer 2

事实证明，这不是 space 泄漏！是我没能处理一些病态的输入。一旦我弄清楚如何处理它，它就起作用了，而且非常快。

使用 `mapM` 和 `foldM` 在 `State` monad 上避免 space 泄漏

Avoiding space leaks with `mapM` and `foldM` over `State` monad

haskell

space-leak

所以，问题。

其他资源