用状态单子重构不纯递归?

Question

我在第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))

godbolt的全解

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

然而，我也读到reader/writer/state单子是如何让你不必传递额外的参数和处理元组结果的，我有兴趣将这种递归移植到haskell。

我在reddit上找到了一个haskell解决方案，看起来它可能会做同样的递归(以及另外两个不这样做的)。

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)

godbolt的全解

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

我仍然不懂Haskell。我可以看出fill' (500, 0)意味着m >>= _ -> fill' (500, 0)，这意味着放弃当前状态，并独立创建一个新的单子(有些东西被保留，但我很困惑什么)?? ?我也完全不懂单轴变压器。

Haskell解决方案同时解决了问题的第二部分，所以也许有人可以把它提出来，这样笛卡尔坐标和包含解决方案的整数对之间就不会混淆了。

Answer 1

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

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

Answer 2

(仅部分回答:下面我只澄清了Haskell代码，但我没有将其与Python代码或任务进行比较)

我有点不喜欢Haskell代码。我认为它过于注重无点风格。我的意思是，flip bool避免变量?maybe在两个复杂分支之间?不，我会使用普通的if/case。

仍然，它在ST s单子中工作，所以它读起来像命令式代码。状态永远不会被丢弃，只会像命令式语言一样被修改。a >>= b与result = a() ; b(result)大致相同，只是代码固执地避免引入变量result。

这是代码，重写(IMHO)提高可读性。

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) = do
-- test the boolean flag at (x,y)
b <- readArray blocks (x, y)
-- if false, we did not visit (x,y) before
when (not b) $ do
when (y == maxY) $ do
-- if counterAtMaxY is Nothing,
-- replace it with counter
mayc <- readSTRef counterAtMaxY
case mayc of
Nothing -> do
c <- readSTRef counter
writeSTRef counterAtMaxY (Just c)
Just _ -> pure ()
when (y <= maxY) $ do
-- recurse thrice
fill' (x, y + 1)
fill' (x - 1, y + 1)
fill' (x + 1, y + 1)
-- mark (x,y) as visited
writeArray blocks (x, y) True
-- increment counter
modifySTRef' counter (+ 1)
fill' (500, 0)
counterAtMaxY <- readSTRef counterAtMaxY
counter <- readSTRef counter
pure (fromMaybe counter counterAtMaxY, counter)

我也会重写y == maxY的情况如下:

when (y == maxY) $ do
-- if counterAtMaxY is Nothing,
-- replace it with counter
c <- readSTRef counter       
modify counterAtMaxY $ mayc ->
case mayc of
Nothing -> Just c
Just _ -> mayc

或者

when (y == maxY) $ do
-- if counterAtMaxY is Nothing,
-- replace it with counter
c <- readSTRef counter       
modify counterAtMaxY (<|> Just c)

其中(<|> Just c)是一个函数，作为Just _值的标识，但将Nothing映射到Just c，这类似于Python的... or c。