重复状态直到它不改变/稳定
Repeat state until it doesn't change / is stable
我正在尝试 运行 反复变换状态,直到状态不变。我 searched Hoogle
Eq s => State s () -> State s ()
但没有找到合适的内容。
我怎样才能运行 一个状态反复变换直到它不再改变?
滚动您自己的更高级别的递归转换
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
内部私下进行,一次在使用的谓词中进行测试是否停止。
我正在尝试 运行 反复变换状态,直到状态不变。我 searched Hoogle
Eq s => State s () -> State s ()
但没有找到合适的内容。
我怎样才能运行 一个状态反复变换直到它不再改变?
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'
从 State
做到这一点,但使用一些函数 monad 魔法...
untilStable :: Eq a => (a -> a) -> a -> a
untilStable = until =<< ((==) =<<)
...使用 execState
s -> s
untilStable (execState stateTransformToRunRepeatedly) initialState
扩展 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 -> suntilStable (execState stateTransformToRunRepeatedly) initialState
没有使用无点样式,但对我来说更清楚发生了什么。
此外,我想知道这是否揭示了 this 和 f a
可能被计算了两次:一次在 until
内部私下进行,一次在使用的谓词中进行测试是否停止。