    {-# LANGUAGE DeriveGeneric, DeriveTraversable, TupleSections #-}
    -- | A list of entities with relative frequencies of appearance.
    module Game.LambdaHack.Core.Frequency
      ( -- * The @Frequency@ type
        Frequency
        -- * Construction
      , uniformFreq, toFreq, maxBoundInt32
        -- * Transformation
      , scaleFreq
        -- * Consumption
      , nullFreq, runFrequency, nameFrequency
      ) where

    import Prelude ()

    import Game.LambdaHack.Core.Prelude

    import Control.Applicative
    import Data.Int (Int32)
    import GHC.Generics (Generic)

    maxBoundInt32 :: Int
    maxBoundInt32 :: Int
    maxBoundInt32 = Int32 -> Int
    forall a b. (Integral a, Integral b, Bits a, Bits b) => a -> b
    toIntegralCrash (Int32
    forall a. Bounded a => a
    maxBound :: Int32)

    -- | The frequency distribution type. Not normalized (operations may
    -- or may not group the same elements and sum their frequencies). However,
    -- elements with less than zero frequency are removed upon construction.
    --
    -- The @Eq@ instance compares raw representations, not relative,
    -- normalized frequencies, so operations don't need to preserve
    -- the expected equalities.
    data Frequency a = Frequency
      { forall a. Frequency a -> [(Int, a)]
    runFrequency  :: [(Int, a)]  -- ^ give acces to raw frequency values
      , forall a. Frequency a -> Text
    nameFrequency :: Text        -- ^ short description for debug, etc.
      }
      deriving (Int -> Frequency a -> ShowS
    [Frequency a] -> ShowS
    Frequency a -> String
    (Int -> Frequency a -> ShowS)
    -> (Frequency a -> String)
    -> ([Frequency a] -> ShowS)
    -> Show (Frequency a)
    forall a. Show a => Int -> Frequency a -> ShowS
    forall a. Show a => [Frequency a] -> ShowS
    forall a. Show a => Frequency a -> String
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    $cshowsPrec :: forall a. Show a => Int -> Frequency a -> ShowS
    showsPrec :: Int -> Frequency a -> ShowS
    $cshow :: forall a. Show a => Frequency a -> String
    show :: Frequency a -> String
    $cshowList :: forall a. Show a => [Frequency a] -> ShowS
    showList :: [Frequency a] -> ShowS
    Show, Frequency a -> Frequency a -> Bool
    (Frequency a -> Frequency a -> Bool)
    -> (Frequency a -> Frequency a -> Bool) -> Eq (Frequency a)
    forall a. Eq a => Frequency a -> Frequency a -> Bool
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    $c== :: forall a. Eq a => Frequency a -> Frequency a -> Bool
    == :: Frequency a -> Frequency a -> Bool
    $c/= :: forall a. Eq a => Frequency a -> Frequency a -> Bool
    /= :: Frequency a -> Frequency a -> Bool
    Eq, Eq (Frequency a)
    Eq (Frequency a) =>
    (Frequency a -> Frequency a -> Ordering)
    -> (Frequency a -> Frequency a -> Bool)
    -> (Frequency a -> Frequency a -> Bool)
    -> (Frequency a -> Frequency a -> Bool)
    -> (Frequency a -> Frequency a -> Bool)
    -> (Frequency a -> Frequency a -> Frequency a)
    -> (Frequency a -> Frequency a -> Frequency a)
    -> Ord (Frequency a)
    Frequency a -> Frequency a -> Bool
    Frequency a -> Frequency a -> Ordering
    Frequency a -> Frequency a -> Frequency a
    forall a.
    Eq a =>
    (a -> a -> Ordering)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> a)
    -> (a -> a -> a)
    -> Ord a
    forall a. Ord a => Eq (Frequency a)
    forall a. Ord a => Frequency a -> Frequency a -> Bool
    forall a. Ord a => Frequency a -> Frequency a -> Ordering
    forall a. Ord a => Frequency a -> Frequency a -> Frequency a
    $ccompare :: forall a. Ord a => Frequency a -> Frequency a -> Ordering
    compare :: Frequency a -> Frequency a -> Ordering
    $c< :: forall a. Ord a => Frequency a -> Frequency a -> Bool
    < :: Frequency a -> Frequency a -> Bool
    $c<= :: forall a. Ord a => Frequency a -> Frequency a -> Bool
    <= :: Frequency a -> Frequency a -> Bool
    $c> :: forall a. Ord a => Frequency a -> Frequency a -> Bool
    > :: Frequency a -> Frequency a -> Bool
    $c>= :: forall a. Ord a => Frequency a -> Frequency a -> Bool
    >= :: Frequency a -> Frequency a -> Bool
    $cmax :: forall a. Ord a => Frequency a -> Frequency a -> Frequency a
    max :: Frequency a -> Frequency a -> Frequency a
    $cmin :: forall a. Ord a => Frequency a -> Frequency a -> Frequency a
    min :: Frequency a -> Frequency a -> Frequency a
    Ord, (forall m. Monoid m => Frequency m -> m)
    -> (forall m a. Monoid m => (a -> m) -> Frequency a -> m)
    -> (forall m a. Monoid m => (a -> m) -> Frequency a -> m)
    -> (forall a b. (a -> b -> b) -> b -> Frequency a -> b)
    -> (forall a b. (a -> b -> b) -> b -> Frequency a -> b)
    -> (forall b a. (b -> a -> b) -> b -> Frequency a -> b)
    -> (forall b a. (b -> a -> b) -> b -> Frequency a -> b)
    -> (forall a. (a -> a -> a) -> Frequency a -> a)
    -> (forall a. (a -> a -> a) -> Frequency a -> a)
    -> (forall a. Frequency a -> [a])
    -> (forall a. Frequency a -> Bool)
    -> (forall a. Frequency a -> Int)
    -> (forall a. Eq a => a -> Frequency a -> Bool)
    -> (forall a. Ord a => Frequency a -> a)
    -> (forall a. Ord a => Frequency a -> a)
    -> (forall a. Num a => Frequency a -> a)
    -> (forall a. Num a => Frequency a -> a)
    -> Foldable Frequency
    forall a. Eq a => a -> Frequency a -> Bool
    forall a. Num a => Frequency a -> a
    forall a. Ord a => Frequency a -> a
    forall m. Monoid m => Frequency m -> m
    forall a. Frequency a -> Bool
    forall a. Frequency a -> Int
    forall a. Frequency a -> [a]
    forall a. (a -> a -> a) -> Frequency a -> a
    forall m a. Monoid m => (a -> m) -> Frequency a -> m
    forall b a. (b -> a -> b) -> b -> Frequency a -> b
    forall a b. (a -> b -> b) -> b -> Frequency a -> b
    forall (t :: * -> *).
    (forall m. Monoid m => t m -> m)
    -> (forall m a. Monoid m => (a -> m) -> t a -> m)
    -> (forall m a. Monoid m => (a -> m) -> t a -> m)
    -> (forall a b. (a -> b -> b) -> b -> t a -> b)
    -> (forall a b. (a -> b -> b) -> b -> t a -> b)
    -> (forall b a. (b -> a -> b) -> b -> t a -> b)
    -> (forall b a. (b -> a -> b) -> b -> t a -> b)
    -> (forall a. (a -> a -> a) -> t a -> a)
    -> (forall a. (a -> a -> a) -> t a -> a)
    -> (forall a. t a -> [a])
    -> (forall a. t a -> Bool)
    -> (forall a. t a -> Int)
    -> (forall a. Eq a => a -> t a -> Bool)
    -> (forall a. Ord a => t a -> a)
    -> (forall a. Ord a => t a -> a)
    -> (forall a. Num a => t a -> a)
    -> (forall a. Num a => t a -> a)
    -> Foldable t
    $cfold :: forall m. Monoid m => Frequency m -> m
    fold :: forall m. Monoid m => Frequency m -> m
    $cfoldMap :: forall m a. Monoid m => (a -> m) -> Frequency a -> m
    foldMap :: forall m a. Monoid m => (a -> m) -> Frequency a -> m
    $cfoldMap' :: forall m a. Monoid m => (a -> m) -> Frequency a -> m
    foldMap' :: forall m a. Monoid m => (a -> m) -> Frequency a -> m
    $cfoldr :: forall a b. (a -> b -> b) -> b -> Frequency a -> b
    foldr :: forall a b. (a -> b -> b) -> b -> Frequency a -> b
    $cfoldr' :: forall a b. (a -> b -> b) -> b -> Frequency a -> b
    foldr' :: forall a b. (a -> b -> b) -> b -> Frequency a -> b
    $cfoldl :: forall b a. (b -> a -> b) -> b -> Frequency a -> b
    foldl :: forall b a. (b -> a -> b) -> b -> Frequency a -> b
    $cfoldl' :: forall b a. (b -> a -> b) -> b -> Frequency a -> b
    foldl' :: forall b a. (b -> a -> b) -> b -> Frequency a -> b
    $cfoldr1 :: forall a. (a -> a -> a) -> Frequency a -> a
    foldr1 :: forall a. (a -> a -> a) -> Frequency a -> a
    $cfoldl1 :: forall a. (a -> a -> a) -> Frequency a -> a
    foldl1 :: forall a. (a -> a -> a) -> Frequency a -> a
    $ctoList :: forall a. Frequency a -> [a]
    toList :: forall a. Frequency a -> [a]
    $cnull :: forall a. Frequency a -> Bool
    null :: forall a. Frequency a -> Bool
    $clength :: forall a. Frequency a -> Int
    length :: forall a. Frequency a -> Int
    $celem :: forall a. Eq a => a -> Frequency a -> Bool
    elem :: forall a. Eq a => a -> Frequency a -> Bool
    $cmaximum :: forall a. Ord a => Frequency a -> a
    maximum :: forall a. Ord a => Frequency a -> a
    $cminimum :: forall a. Ord a => Frequency a -> a
    minimum :: forall a. Ord a => Frequency a -> a
    $csum :: forall a. Num a => Frequency a -> a
    sum :: forall a. Num a => Frequency a -> a
    $cproduct :: forall a. Num a => Frequency a -> a
    product :: forall a. Num a => Frequency a -> a
    Foldable, Functor Frequency
    Foldable Frequency
    (Functor Frequency, Foldable Frequency) =>
    (forall (f :: * -> *) a b.
     Applicative f =>
     (a -> f b) -> Frequency a -> f (Frequency b))
    -> (forall (f :: * -> *) a.
        Applicative f =>
        Frequency (f a) -> f (Frequency a))
    -> (forall (m :: * -> *) a b.
        Monad m =>
        (a -> m b) -> Frequency a -> m (Frequency b))
    -> (forall (m :: * -> *) a.
        Monad m =>
        Frequency (m a) -> m (Frequency a))
    -> Traversable Frequency
    forall (t :: * -> *).
    (Functor t, Foldable t) =>
    (forall (f :: * -> *) a b.
     Applicative f =>
     (a -> f b) -> t a -> f (t b))
    -> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a))
    -> (forall (m :: * -> *) a b.
        Monad m =>
        (a -> m b) -> t a -> m (t b))
    -> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a))
    -> Traversable t
    forall (m :: * -> *) a.
    Monad m =>
    Frequency (m a) -> m (Frequency a)
    forall (f :: * -> *) a.
    Applicative f =>
    Frequency (f a) -> f (Frequency a)
    forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> Frequency a -> m (Frequency b)
    forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> Frequency a -> f (Frequency b)
    $ctraverse :: forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> Frequency a -> f (Frequency b)
    traverse :: forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> Frequency a -> f (Frequency b)
    $csequenceA :: forall (f :: * -> *) a.
    Applicative f =>
    Frequency (f a) -> f (Frequency a)
    sequenceA :: forall (f :: * -> *) a.
    Applicative f =>
    Frequency (f a) -> f (Frequency a)
    $cmapM :: forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> Frequency a -> m (Frequency b)
    mapM :: forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> Frequency a -> m (Frequency b)
    $csequence :: forall (m :: * -> *) a.
    Monad m =>
    Frequency (m a) -> m (Frequency a)
    sequence :: forall (m :: * -> *) a.
    Monad m =>
    Frequency (m a) -> m (Frequency a)
    Traversable, (forall x. Frequency a -> Rep (Frequency a) x)
    -> (forall x. Rep (Frequency a) x -> Frequency a)
    -> Generic (Frequency a)
    forall x. Rep (Frequency a) x -> Frequency a
    forall x. Frequency a -> Rep (Frequency a) x
    forall a.
    (forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
    forall a x. Rep (Frequency a) x -> Frequency a
    forall a x. Frequency a -> Rep (Frequency a) x
    $cfrom :: forall a x. Frequency a -> Rep (Frequency a) x
    from :: forall x. Frequency a -> Rep (Frequency a) x
    $cto :: forall a x. Rep (Frequency a) x -> Frequency a
    to :: forall x. Rep (Frequency a) x -> Frequency a
    Generic)

    instance Monad Frequency where
      Frequency [(Int, a)]
    xs Text
    name >>= :: forall a b. Frequency a -> (a -> Frequency b) -> Frequency b
    >>= a -> Frequency b
    f =
        [(Int, b)] -> Text -> Frequency b
    forall a. [(Int, a)] -> Text -> Frequency a
    Frequency [
    #ifdef WITH_EXPENSIVE_ASSERTIONS
                    assert (toInteger p * toInteger q <= toInteger maxBoundInt32
                            `blame` (name, map fst xs))
    #endif
                    (Int
    p Int -> Int -> Int
    forall a. Num a => a -> a -> a
    * Int
    q, b
    y)
                  | (Int
    p, a
    x) <- [(Int, a)]
    xs
                  , (Int
    q, b
    y) <- Frequency b -> [(Int, b)]
    forall a. Frequency a -> [(Int, a)]
    runFrequency (a -> Frequency b
    f a
    x)
                  ]
                  (Text
    "bind (" Text -> Text -> Text
    forall a. Semigroup a => a -> a -> a
    <> Text
    name Text -> Text -> Text
    forall a. Semigroup a => a -> a -> a
    <> Text
    ")")

    instance Functor Frequency where
      fmap :: forall a b. (a -> b) -> Frequency a -> Frequency b
    fmap a -> b
    f (Frequency [(Int, a)]
    xs Text
    name) = [(Int, b)] -> Text -> Frequency b
    forall a. [(Int, a)] -> Text -> Frequency a
    Frequency (((Int, a) -> (Int, b)) -> [(Int, a)] -> [(Int, b)]
    forall a b. (a -> b) -> [a] -> [b]
    map ((a -> b) -> (Int, a) -> (Int, b)
    forall b c d. (b -> c) -> (d, b) -> (d, c)
    forall (a :: * -> * -> *) b c d.
    Arrow a =>
    a b c -> a (d, b) (d, c)
    second a -> b
    f) [(Int, a)]
    xs) Text
    name

    instance Applicative Frequency where
      {-# INLINE pure #-}
      pure :: forall a. a -> Frequency a
    pure a
    x = [(Int, a)] -> Text -> Frequency a
    forall a. [(Int, a)] -> Text -> Frequency a
    Frequency [(Int
    1, a
    x)] Text
    "pure"
      Frequency [(Int, a -> b)]
    fs Text
    fname <*> :: forall a b. Frequency (a -> b) -> Frequency a -> Frequency b
    <*> Frequency [(Int, a)]
    ys Text
    yname =
        [(Int, b)] -> Text -> Frequency b
    forall a. [(Int, a)] -> Text -> Frequency a
    Frequency [
    #ifdef WITH_EXPENSIVE_ASSERTIONS
                    assert (toInteger p * toInteger q <= toInteger maxBoundInt32
                            `blame` (fname, map fst fs, yname, map fst ys))
    #endif
                    (Int
    p Int -> Int -> Int
    forall a. Num a => a -> a -> a
    * Int
    q, a -> b
    f a
    y)
                  | (Int
    p, a -> b
    f) <- [(Int, a -> b)]
    fs
                  , (Int
    q, a
    y) <- [(Int, a)]
    ys
                  ]
                  (Text
    "(" Text -> Text -> Text
    forall a. Semigroup a => a -> a -> a
    <> Text
    fname Text -> Text -> Text
    forall a. Semigroup a => a -> a -> a
    <> Text
    ") <*> (" Text -> Text -> Text
    forall a. Semigroup a => a -> a -> a
    <> Text
    yname Text -> Text -> Text
    forall a. Semigroup a => a -> a -> a
    <> Text
    ")")

    instance MonadPlus Frequency where
      mplus :: forall a. Frequency a -> Frequency a -> Frequency a
    mplus (Frequency [(Int, a)]
    xs Text
    xname) (Frequency [(Int, a)]
    ys Text
    yname) =
        let name :: Text
    name = case ([(Int, a)]
    xs, [(Int, a)]
    ys) of
              ([], []) -> Text
    "[]"
              ([], [(Int, a)]
    _) -> Text
    yname
              ([(Int, a)]
    _, []) -> Text
    xname
              ([(Int, a)], [(Int, a)])
    _ -> Text
    "(" Text -> Text -> Text
    forall a. Semigroup a => a -> a -> a
    <> Text
    xname Text -> Text -> Text
    forall a. Semigroup a => a -> a -> a
    <> Text
    ") ++ (" Text -> Text -> Text
    forall a. Semigroup a => a -> a -> a
    <> Text
    yname Text -> Text -> Text
    forall a. Semigroup a => a -> a -> a
    <> Text
    ")"
        in [(Int, a)] -> Text -> Frequency a
    forall a. [(Int, a)] -> Text -> Frequency a
    Frequency ([(Int, a)]
    xs [(Int, a)] -> [(Int, a)] -> [(Int, a)]
    forall a. [a] -> [a] -> [a]
    ++ [(Int, a)]
    ys) Text
    name
      mzero :: forall a. Frequency a
    mzero = [(Int, a)] -> Text -> Frequency a
    forall a. [(Int, a)] -> Text -> Frequency a
    Frequency [] Text
    "[]"

    instance Alternative Frequency where
      <|> :: forall a. Frequency a -> Frequency a -> Frequency a
    (<|>) = Frequency a -> Frequency a -> Frequency a
    forall a. Frequency a -> Frequency a -> Frequency a
    forall (m :: * -> *) a. MonadPlus m => m a -> m a -> m a
    mplus
      empty :: forall a. Frequency a
    empty = Frequency a
    forall a. Frequency a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero

    -- | Uniform discrete frequency distribution.
    uniformFreq :: Text -> [a] -> Frequency a
    uniformFreq :: forall a. Text -> [a] -> Frequency a
    uniformFreq Text
    name [a]
    l = [(Int, a)] -> Text -> Frequency a
    forall a. [(Int, a)] -> Text -> Frequency a
    Frequency ((a -> (Int, a)) -> [a] -> [(Int, a)]
    forall a b. (a -> b) -> [a] -> [b]
    map (Int
    1,) [a]
    l) Text
    name

    -- | Takes a name and a list of frequencies and items
    -- into the frequency distribution.
    toFreq :: Text -> [(Int, a)] -> Frequency a
    toFreq :: forall a. Text -> [(Int, a)] -> Frequency a
    toFreq Text
    name [(Int, a)]
    l =
    #ifdef WITH_EXPENSIVE_ASSERTIONS
      assert (all (\(p, _) -> toInteger p <= toInteger maxBoundInt32) l
              `blame` (name, map fst l)) $
    #endif
      [(Int, a)] -> Text -> Frequency a
    forall a. [(Int, a)] -> Text -> Frequency a
    Frequency (((Int, a) -> Bool) -> [(Int, a)] -> [(Int, a)]
    forall a. (a -> Bool) -> [a] -> [a]
    filter ((Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    > Int
    0 ) (Int -> Bool) -> ((Int, a) -> Int) -> (Int, a) -> Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . (Int, a) -> Int
    forall a b. (a, b) -> a
    fst) [(Int, a)]
    l) Text
    name

    -- | Scale frequency distribution, multiplying it
    -- by a positive integer constant.
    scaleFreq :: Show a => Int -> Frequency a -> Frequency a
    scaleFreq :: forall a. Show a => Int -> Frequency a -> Frequency a
    scaleFreq Int
    n (Frequency [(Int, a)]
    xs Text
    name) =
      Bool -> Frequency a -> Frequency a
    forall a. (?callStack::CallStack) => Bool -> a -> a
    assert (Int
    n Int -> Int -> Bool
    forall a. Ord a => a -> a -> Bool
    > Int
    0 Bool -> (String, (Text, Int, [(Int, a)])) -> Bool
    forall v. Show v => Bool -> v -> Bool
    `blame` String
    "non-positive frequency scale" String
    -> (Text, Int, [(Int, a)]) -> (String, (Text, Int, [(Int, a)]))
    forall v. String -> v -> (String, v)
    `swith` (Text
    name, Int
    n, [(Int, a)]
    xs)) (Frequency a -> Frequency a) -> Frequency a -> Frequency a
    forall a b. (a -> b) -> a -> b
    $
      let multN :: Int -> Int
    multN Int
    p =
    #ifdef WITH_EXPENSIVE_ASSERTIONS
                    assert (toInteger p * toInteger n <= toInteger maxBoundInt32
                            `blame` (n, Frequency xs name)) $
    #endif
                    Int
    p Int -> Int -> Int
    forall a. Num a => a -> a -> a
    * Int
    n
      in [(Int, a)] -> Text -> Frequency a
    forall a. [(Int, a)] -> Text -> Frequency a
    Frequency (((Int, a) -> (Int, a)) -> [(Int, a)] -> [(Int, a)]
    forall a b. (a -> b) -> [a] -> [b]
    map ((Int -> Int) -> (Int, a) -> (Int, a)
    forall b c d. (b -> c) -> (b, d) -> (c, d)
    forall (a :: * -> * -> *) b c d.
    Arrow a =>
    a b c -> a (b, d) (c, d)
    first Int -> Int
    multN) [(Int, a)]
    xs) Text
    name

    -- | Test if the frequency distribution is empty.
    nullFreq :: Frequency a -> Bool
    nullFreq :: forall a. Frequency a -> Bool
    nullFreq (Frequency [(Int, a)]
    fs Text
    _) = [(Int, a)] -> Bool
    forall a. [a] -> Bool
    null [(Int, a)]
    fs