How to write a fixed point function in haskell

Question

I have a function with the following signature:

simCon :: [Constraint] -> Maybe [Constraint]

I would like to write a method which, incase simCon returns Just [Constraint], I want to feed them back into simCon and rerun the method, and to keep doing this until the input is the same as the output.

In case of Nothing, I would want to terminate the algorithm.

I have something that would work if both the input and output are the same type

fixed :: Eq a => (a -> a) -> a -> a
fixed f a 
  | a == a' = a
  | otherwise = fixed f a'
  where a' = f a

But this isn't going to work because I return a Maybe now. Can someone suggest a way to write a similar function but for a return type of Maybe?

Answer 1

We can make use of the bind function here:

import Data.Bool(bool)
import Control.Monad(liftM2)

fixedM :: (Eq a, Monad m) => (a -> m a) -> a -> m a
fixedM f = go
    where go x = f x >>= (liftM2 bool go pure <*> (x ==))

A more verbose implementation is:

fixedM :: (Eq a, Monad m) => (a -> m a) -> a -> m a
fixedM f x = do
    x' <- f x
    if x == x'
        then pure x'
        else fixedM f x'

We thus first calculate x' with f x. In case f x return Just x', then we continue. In case f x return Nothing, the fixedM will return Nothing as well. We then compare x with x'. In case the two are equal, we return pure x', otherwise we recurse on fixedM f x'.

Alternatively, we can make use of pattern matching, although this is basically making the bind operator explicit (and only working for a Maybe):

import Control.Monad(ap)

fixedM :: Eq a => (a -> Maybe a) -> a -> Maybe a
fixedM f = ap go f
    where go x (Just x') | x == x' = go x' (f x')
                         | otherwise = Just x'
          go _ _ = Nothing

we can make it more compact by using pattern guards:

fixedM :: Eq a => (a -> Maybe a) -> a -> Maybe a
fixedM f = go
    where go x | Just x' <- f x = bool (go x) (Just x) (x == x')
               | otherwise = Nothing