module Utility.Fixpoint (
    fix
  , fixUnbounded
  , fixMaybe
  ) where

--------------------------------------------------------------

fix :: (Show a, Eq a) => Int -> (a -> a) -> a -> a
fix :: Int -> (a -> a) -> a -> a
fix (-1)     a -> a
_ a
_ = [Char] -> a
forall a. HasCallStack => [Char] -> a
error [Char]
"fix: Exceeded maxIters"
fix Int
maxIters a -> a
f a
x = let x' :: a
x' = a -> a
f a
x in
                   if a
x' a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
x then
                     a
x
                   else
                     Int -> (a -> a) -> a -> a
forall a. (Show a, Eq a) => Int -> (a -> a) -> a -> a
fix (Int
maxIters Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1) a -> a
f a
x'

fixUnbounded :: (Eq a) => (a -> a) -> a -> a
fixUnbounded :: (a -> a) -> a -> a
fixUnbounded a -> a
f a
x = let x' :: a
x' = a -> a
f a
x in
                   if a
x' a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
x then
                     a
x
                   else
                     (a -> a) -> a -> a
forall a. Eq a => (a -> a) -> a -> a
fixUnbounded a -> a
f a
x'

fixMaybe :: (Eq a) => (a -> Maybe a) -> a -> Maybe a
fixMaybe :: (a -> Maybe a) -> a -> Maybe a
fixMaybe a -> Maybe a
f a
x = case a -> Maybe a
f a
x of
                 Maybe a
Nothing -> Maybe a
forall a. Maybe a
Nothing
                 Just a
x' -> if a
x' a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
x then
                              a -> Maybe a
forall a. a -> Maybe a
Just a
x
                            else
                              (a -> Maybe a) -> a -> Maybe a
forall a. Eq a => (a -> Maybe a) -> a -> Maybe a
fixMaybe a -> Maybe a
f a
x'