Repeat state until it doesn't change / is stable

Question

I'm trying to run a state transform repeatedly until the state doesn't change. I've searched Hoogle for

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

but found nothing that looks appropriate.

How can I run a state transform repeatedly until it doesn't change?

Answer 1

You can do this in State, but there's no particular benefit. Why not:

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)

If you start with a State s (), you can execState it to get your s -> s out.

Of course, there's no guarantee that f doesn't diverge, so idempotently f may never terminate.

Answer 2

You are computing the fix-point of your state transform. But we can't use fix since we are in a monadic context. So let's use a monadic fix-point combinator instead. Enter 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)

I also took the liberty of generalizing your function to so that you can provide a user supplied binary predicate.

Using ghci runState (untilStable (==) $ modify (+1)) 2 will never terminate. But with:

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

You get:

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

This untilStable can be generalized further into:

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

Now we have freed up what types the computations can result in.

Fix you want to implement idempotently with fix, you can do it like so:

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 3

You can roll-your-own higher level recursive transform, using get and unless

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

Answer 4

Taking inspiration from https://stackoverflow.com/a/44378096/1319998 and https://stackoverflow.com/a/23924238/1319998, you can do this out of State but using some function monad magic...

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

... extracting the s -> s from a state using execState

untilStable (execState stateTransformToRunRepeatedly) initialState

Answer 5

Expanding on the answer from https://stackoverflow.com/a/44381834/1319998, 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

... and similarly extracting the s -> s from a state using execState

untilStable (execState stateTransformToRunRepeatedly) initialState

Point-free style isn't used, but to me it is clearer what's going on.

Also, I wonder if this reveals an inefficiency of both this and https://stackoverflow.com/a/44381834/1319998, where f a may be computed twice: once privately inside until, and once in the predicate used to test whether to stop.