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'