-- | The iterative fixed-point function.
module Data.Cfg.FixedPoint
  ( fixedPoint
  ) where

-- | Given a function and an initial value, find the fixed point of
-- the function.
fixedPoint :: Eq a => (a -> a) -> a -> a
fixedPoint :: (a -> a) -> a -> a
fixedPoint a -> a
f a
a = [a] -> a
forall a. Eq a => [a] -> a
go ([a] -> a) -> [a] -> a
forall a b. (a -> b) -> a -> b
$ (a -> a) -> a -> [a]
forall a. (a -> a) -> a -> [a]
iterate a -> a
f a
a
  where
    go :: [a] -> a
go as :: [a]
as@(a
a':a
a'':[a]
_) =
      if a
a' a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
a''
        then a
a'
        else [a] -> a
go ([a] -> a) -> [a] -> a
forall a b. (a -> b) -> a -> b
$ [a] -> [a]
forall a. [a] -> [a]
tail [a]
as
    go [a]
_ = [Char] -> a
forall a. HasCallStack => [Char] -> a
error [Char]
"fixedPoint: impossible"