haskell - 用状态单子(monad)重构不纯递归？

Question

我一直在剖析this one-liner solution对于 aoc day 14并遇到了一个优雅的不纯递归解决方案:

def s(x,y):
    if y > h: return True
    if (x, y) in m: return False
    return next((r for d in (0,-1,1) if (r:=s(x+d,y+1))), None) or m.add((x,y))

full solution on godbolt

可以使其变得纯粹的一种方法是从函数 s 显式传递并返回集合 m (即 s::int -> int -> 设置 -> (bool, set))。

但是，我还阅读了 reader/writer 如何/state monad 使您不必传递额外的参数并处理元组结果，并且我有兴趣将此递归移植到 haskell。

我找到了一个haskell solution在 reddit 上看起来它可能会执行相同的递归(以及 two more 但不会)。

fill :: (MArray a Bool (ST s), Ix i, Num i, Show i) => a (i, i) Bool -> i -> ST s (Int, Int)
fill blocks maxY = do
    counterAtMaxY <- newSTRef Nothing
    counter <- newSTRef 0
    let fill' (x, y) = readArray blocks (x, y) >>= flip bool (pure ()) do
            when (y == maxY) $ readSTRef counterAtMaxY >>= maybe
                (readSTRef counter >>= writeSTRef counterAtMaxY . Just) (const $ pure ())
            when (y <= maxY) $ fill' (x, y + 1) >> fill' (x - 1, y + 1) >> fill' (x + 1, y + 1)
            writeArray blocks (x, y) True >> modifySTRef' counter (+ 1)
    fill' (500, 0)
    counterAtMaxY <- readSTRef counterAtMaxY
    counter <- readSTRef counter
    pure (fromMaybe counter counterAtMaxY, counter)

full solution on godbolt

有人可以确认这确实是 python 解决方案的端口吗？如果是这样，他们可以让我了解递归是如何发生的吗？

我仍然不懂 Haskell。我可以看出 fill' (500, 0) 的意思是 m >>=\_ -> fill' (500, 0)，这意味着丢弃当前的状态，并独立创建一个新的单子(monad)(有些东西被保留，但我很困惑是什么)？？我也根本不理解 monad 转换器。

Haskell 解决方案同时执行问题的第二部分，因此也许有人可以将其分解出来，这样笛卡尔坐标和包含解决方案的一对整数之间就不会混淆。

Answer 1

下面是 Python 代码到 Haskell 的相当接近的翻译。关于差异的一些评论:

• 全局 h 成为局部参数，并且 m::Set (Int, Int) 在 State monad 中隐式传递，使用 get 和 modify 访问。
• Haskell 中没有提前返回(调用 return/pure 不会中止函数的其余部分，您必须将其放在 block 的末尾)。另一方面，if 表达式必须有 else 子句，这样无论如何都会迫使您做正确的事情。
• 生成器表达式可以编写为一个高阶函数，它尝试列表中的每个操作，一旦返回 True 就停止。
• Python 中的 add 函数返回 None，它在条件中被解释为 False。在 Haskell 中，我们不喜欢这种重载；相反，我们显式地将 False 值附加到无值操作 add (x, y)，add (x, y) *> pure False.
• 使用execState以初始状态m0“运行单子(monad)程序”s h0 500 0，获取其最终状态。那个“程序”s h0 500 0::M Bool实际上是一个纯函数Set (Int, Int) -> (Bool, Set (Int, Int))， execState 所做的就是将其应用于初始状态并投影出输出对的第二个组件。 “状态单子(monad)”的要点是这样的函数可以用命令式语言的语法(“do-notation”)来定义。

module Main where

import Control.Monad.State
import Data.Set (Set)
import qualified Data.Set as Set

type M = State (Set (Int, Int))

s :: Int -> Int -> Int -> M Bool
s h x y =
  if y > h then pure True
  else do
    m <- get
    if Set.member (x, y) m then
      pure False
    else
      orM ([s h (x+d) (y+1) | d <- [0, -1, 1]] ++ [add (x, y) *> pure False])

orM :: Monad m => [m Bool] -> m Bool
orM [] = pure False
orM (x : xs) = do
  b <- x
  if b then pure True
  else orM xs

add :: (Int, Int) -> M ()
add (x, y) = modify (Set.insert (x, y))

-- Example from https://adventofcode.com/2022/day/14

m0 :: Set (Int, Int)
m0 = vline 498 4 6 <> hline 498 496 6 <> hline 503 502 4 <> vline 502 4 9 <> hline 494 502 9

vline, hline :: Int -> Int -> Int -> Set (Int, Int)
vline x y1 y2 | y1 > y2 = vline x y2 y1
vline x y1 y2 = Set.fromList [(x, y) | y <- [y1 .. y2]]

hline x1 x2 y | x1 > x2 = hline x2 x1 y
hline x1 x2 y = Set.fromList [(x, y) | x <- [x1 .. x2]]

h0 :: Int
h0 = 9

main :: IO ()
main =
  print (Set.size (execState (s h0 500 0) m0) - Set.size m0)
  -- Output: 24