    module Data.Function.HT.Private where

    import Data.List (genericReplicate, )

    {- |
    Compositional power of a function,
    i.e. apply the function @n@ times to a value.
    It is rather the same as @iter@
    in Simon Thompson: \"The Craft of Functional Programming\", page 172
    -}
    {-# INLINE nest #-}
    nest, nest1, nest2 :: Int -> (a -> a) -> a -> a
    nest 0 _ x = x
    nest n f x = f (nest (n-1) f x)

    nest1 n f = foldr (.) id (replicate n f)
    nest2 n f x = iterate f x !! n

    propNest :: (Eq a) => Int -> (a -> a) -> a -> Bool
    propNest n f x =
       nest n f x == nest1 n f x

    {- |
    @powerAssociative@ is an auxiliary function that,
    for an associative operation @op@,
    computes the same value as

      @powerAssociative op a0 a n = foldr op a0 (genericReplicate n a)@

    but applies "op" O(log n) times and works for large n.
    -}

    {-# INLINE powerAssociative #-}
    {-# INLINE powerAssociative1 #-}
    powerAssociative, powerAssociative1 ::
       (a -> a -> a) -> a -> a -> Integer -> a
    powerAssociative _  a0 _ 0 = a0
    powerAssociative op a0 a n =
       if even n
         then powerAssociative op a0 (op a a) (div n 2)
         else powerAssociative op (op a0 a) (op a a) (div n 2)

    powerAssociative1 op a0 a n =
       foldr op a0 (genericReplicate n a)