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

Question

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

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

但没有找到合适的内容。

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

Answer 1

您可以使用 get and unless

滚动您自己的更高级别的递归转换

untilStable :: Eq s => State s () -> State s ()
untilStable stateTransform = do
  before <- get
  stateTransform
  after <- get
  unless (before == after) $ untilStable stateTransform

Answer 2

您可以在 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 可能永远不会终止。

Answer 3

您正在计算状态转换的固定点。但是我们不能使用 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'

Answer 4

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

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

...使用 execState

从状态中提取 s -> s

untilStable (execState stateTransformToRunRepeatedly) initialState

Answer 5

扩展 , 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 内部私下进行，一次在使用的谓词中进行测试是否停止。

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

Repeat state until it doesn't change / is stable

monads

haskell