重复状态直到它不改变/稳定

Repeat state until it doesn't change / is stable

我正在尝试 运行 反复变换状态,直到状态不变。我 searched Hoogle

Eq s => State s () -> State s ()

但没有找到合适的内容。

我怎样才能运行 一个状态反复变换直到它不再改变?

您可以使用 get and unless

滚动您自己的更高级别的递归转换
untilStable :: Eq s => State s () -> State s ()
untilStable stateTransform = do
  before <- get
  stateTransform
  after <- get
  unless (before == after) $ untilStable stateTransform

您可以在 State 中执行此操作,但没有特别的好处。为什么不呢:

idempotently :: Eq a => (a -> a) -> a -> a
idempotently f a = if a' == a then a else idempotently f a' where a' = f a

idempotentlyM :: Eq s => (s -> s) -> State s ()
idempotentlyM f = modify (idempotently f)

如果你从 State s () 开始,你可以 execState 它来得到你的 s -> s

当然,不能保证 f 不发散,所以 idempotently f 可能永远不会终止。

您正在计算状态转换的固定点。 但是我们不能使用 fix 因为我们处于单子上下文中。 因此,让我们改用 monadic 定点组合器。 输入 mfix:

import Control.Monad (unless)
import Control.Monad.State (MonadState, StateT, get, put)
import Control.Monad.Fix (mfix)
import Control.Monad.IO.Class (liftIO)

untilStable :: MonadState s m => (s -> s -> Bool) -> m a -> m ()
untilStable p = mfix $ \f st -> p <$> get <* st <*> get >>= (`unless` f)

我还冒昧地将您的函数概括为,以便您可以提供用户提供的二进制谓词。

使用ghci runState (untilStable (==) $ modify (+1)) 2 永远不会终止。 但是:

comp :: StateT Int IO ()
comp = do
  s1 <- (+1) <$> get
  liftIO $ print s1
  let s2 = if s1 >= 3 then 3 else s1
  put s2

你得到:

> runStateT (untilStable (==) comp) 0
1
2
3
4
((),3)

这个untilStable可以进一步概括为:

untilStable :: MonadState s m => (s -> s -> Bool) -> m a -> m a
untilStable p = mfix $ \f st -> do
  before <- get
  a <- st
  after  <- get
  if p before after then pure a else f

现在我们已经释放了计算结果的类型。

修复你想用fix实现idempotently,你可以这样做:

import Data.Function (fix)

idempotently :: Eq a => (a -> a) -> a -> a
idempotently = fix $ \i f a ->
  let a' = f a
  in if a' == a then a else i f a'

and 中汲取灵感,您可以 State 做到这一点,但使用一些函数 monad 魔法...

untilStable :: Eq a => (a -> a) -> a -> a
untilStable = until =<< ((==) =<<)

...使用 execState

从状态中提取 s -> s
untilStable (execState stateTransformToRunRepeatedly) initialState

扩展 , so keeping the iteration out of State, but avoiding the function monad magic with a clearer use of until

的答案
untilStable :: Eq a => (a -> a) -> a -> a
untilStable f a = until (\w -> f w == w) f a

... 并类似地使用 execState

从状态中提取 s -> s
untilStable (execState stateTransformToRunRepeatedly) initialState

没有使用无点样式,但对我来说更清楚发生了什么。

此外,我想知道这是否揭示了 this 和 的低效率,其中 f a 可能被计算了两次:一次在 until 内部私下进行,一次在使用的谓词中进行测试是否停止。