-- | anamorphism

module Autolib.Ana where

import Control.Monad ( guard )

-- | compute anamorphism (construct list)
ana :: ( a -> Maybe (b, a) ) -> a -> [b]
ana :: forall a b. (a -> Maybe (b, a)) -> a -> [b]
ana a -> Maybe (b, a)
f a
x = case a -> Maybe (b, a)
f a
x of
    Just (b
y, a
z) -> b
y b -> [b] -> [b]
forall a. a -> [a] -> [a]
: (a -> Maybe (b, a)) -> a -> [b]
forall a b. (a -> Maybe (b, a)) -> a -> [b]
ana a -> Maybe (b, a)
f a
z
    Maybe (b, a)
Nothing     -> []

-- | find list of digits w.r.t. base
based :: Integral b => b -> b -> [b]
based :: forall b. Integral b => b -> b -> [b]
based b
b = [b] -> [b]
forall a. [a] -> [a]
reverse ([b] -> [b]) -> (b -> [b]) -> b -> [b]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (b -> Maybe (b, b)) -> b -> [b]
forall a b. (a -> Maybe (b, a)) -> a -> [b]
ana ( \ b
x -> do
		       Bool -> Maybe ()
forall (f :: * -> *). Alternative f => Bool -> f ()
guard (Bool -> Maybe ()) -> Bool -> Maybe ()
forall a b. (a -> b) -> a -> b
$ b
x b -> b -> Bool
forall a. Ord a => a -> a -> Bool
> b
0
		       let (b
q,b
r) = b -> b -> (b, b)
forall a. Integral a => a -> a -> (a, a)
divMod b
x b
b
		       (b, b) -> Maybe (b, b)
forall a. a -> Maybe a
forall (m :: * -> *) a. Monad m => a -> m a
return (b
r,b
q)
             )

-- | convert from list of digits to number
unbased :: Integral b => b -> [b] -> b
unbased :: forall b. Integral b => b -> [b] -> b
unbased b
b = (b -> b -> b) -> b -> [b] -> b
forall b a. (b -> a -> b) -> b -> [a] -> b
forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl ( \ b
x b
y -> b
b b -> b -> b
forall a. Num a => a -> a -> a
* b
x b -> b -> b
forall a. Num a => a -> a -> a
+ b
y ) b
0