    -- | It is occasionally useful to define generic functions that can
    -- not only compute their result as an integer, but also as a symbolic
    -- expression in the form of an AST.
    --
    -- There are some Haskell hacks for this - it is for example not hard
    -- to define an instance of 'Num' that constructs an AST.  However,
    -- this falls down for some other interesting classes, like
    -- 'Integral', which requires both the problematic method
    -- 'fromInteger', and also that the type is an instance of 'Enum'.
    --
    -- We can always just define hobbled instances that call 'error' for
    -- those methods that are impractical, but this is ugly.
    --
    -- Hence, this module defines similes to standard Haskell numeric
    -- typeclasses that have been modified to make generic functions
    -- slightly easier to write.
    module Futhark.Util.IntegralExp
      ( IntegralExp (..),
        Wrapped (..),
      )
    where

    import Data.Int
    import Prelude

    -- | A twist on the 'Integral' type class that is more friendly to
    -- symbolic representations.
    class (Num e) => IntegralExp e where
      quot :: e -> e -> e
      rem :: e -> e -> e
      div :: e -> e -> e
      mod :: e -> e -> e
      sgn :: e -> Maybe Int
      pow :: e -> e -> e

      -- | Like 'Futhark.Util.IntegralExp.div', but rounds towards
      -- positive infinity.
      divUp :: e -> e -> e
      divUp e
    x e
    y =
        (e
    x e -> e -> e
    forall a. Num a => a -> a -> a
    + e
    y e -> e -> e
    forall a. Num a => a -> a -> a
    - e
    1) e -> e -> e
    forall e. IntegralExp e => e -> e -> e
    `Futhark.Util.IntegralExp.div` e
    y

      nextMul :: e -> e -> e
      nextMul e
    x e
    y = e
    x e -> e -> e
    forall e. IntegralExp e => e -> e -> e
    `divUp` e
    y e -> e -> e
    forall a. Num a => a -> a -> a
    * e
    y

    -- | This wrapper allows you to use a type that is an instance of the
    -- true class whenever the simile class is required.
    newtype Wrapped a = Wrapped {forall a. Wrapped a -> a
    wrappedValue :: a}
      deriving (Wrapped a -> Wrapped a -> Bool
    (Wrapped a -> Wrapped a -> Bool)
    -> (Wrapped a -> Wrapped a -> Bool) -> Eq (Wrapped a)
    forall a. Eq a => Wrapped a -> Wrapped a -> Bool
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    $c== :: forall a. Eq a => Wrapped a -> Wrapped a -> Bool
    == :: Wrapped a -> Wrapped a -> Bool
    $c/= :: forall a. Eq a => Wrapped a -> Wrapped a -> Bool
    /= :: Wrapped a -> Wrapped a -> Bool
    Eq, Eq (Wrapped a)
    Eq (Wrapped a) =>
    (Wrapped a -> Wrapped a -> Ordering)
    -> (Wrapped a -> Wrapped a -> Bool)
    -> (Wrapped a -> Wrapped a -> Bool)
    -> (Wrapped a -> Wrapped a -> Bool)
    -> (Wrapped a -> Wrapped a -> Bool)
    -> (Wrapped a -> Wrapped a -> Wrapped a)
    -> (Wrapped a -> Wrapped a -> Wrapped a)
    -> Ord (Wrapped a)
    Wrapped a -> Wrapped a -> Bool
    Wrapped a -> Wrapped a -> Ordering
    Wrapped a -> Wrapped a -> Wrapped 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 (Wrapped a)
    forall a. Ord a => Wrapped a -> Wrapped a -> Bool
    forall a. Ord a => Wrapped a -> Wrapped a -> Ordering
    forall a. Ord a => Wrapped a -> Wrapped a -> Wrapped a
    $ccompare :: forall a. Ord a => Wrapped a -> Wrapped a -> Ordering
    compare :: Wrapped a -> Wrapped a -> Ordering
    $c< :: forall a. Ord a => Wrapped a -> Wrapped a -> Bool
    < :: Wrapped a -> Wrapped a -> Bool
    $c<= :: forall a. Ord a => Wrapped a -> Wrapped a -> Bool
    <= :: Wrapped a -> Wrapped a -> Bool
    $c> :: forall a. Ord a => Wrapped a -> Wrapped a -> Bool
    > :: Wrapped a -> Wrapped a -> Bool
    $c>= :: forall a. Ord a => Wrapped a -> Wrapped a -> Bool
    >= :: Wrapped a -> Wrapped a -> Bool
    $cmax :: forall a. Ord a => Wrapped a -> Wrapped a -> Wrapped a
    max :: Wrapped a -> Wrapped a -> Wrapped a
    $cmin :: forall a. Ord a => Wrapped a -> Wrapped a -> Wrapped a
    min :: Wrapped a -> Wrapped a -> Wrapped a
    Ord, Int -> Wrapped a -> ShowS
    [Wrapped a] -> ShowS
    Wrapped a -> String
    (Int -> Wrapped a -> ShowS)
    -> (Wrapped a -> String)
    -> ([Wrapped a] -> ShowS)
    -> Show (Wrapped a)
    forall a. Show a => Int -> Wrapped a -> ShowS
    forall a. Show a => [Wrapped a] -> ShowS
    forall a. Show a => Wrapped a -> String
    forall a.
    (Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
    $cshowsPrec :: forall a. Show a => Int -> Wrapped a -> ShowS
    showsPrec :: Int -> Wrapped a -> ShowS
    $cshow :: forall a. Show a => Wrapped a -> String
    show :: Wrapped a -> String
    $cshowList :: forall a. Show a => [Wrapped a] -> ShowS
    showList :: [Wrapped a] -> ShowS
    Show)

    instance (Enum a) => Enum (Wrapped a) where
      toEnum :: Int -> Wrapped a
    toEnum Int
    a = a -> Wrapped a
    forall a. a -> Wrapped a
    Wrapped (a -> Wrapped a) -> a -> Wrapped a
    forall a b. (a -> b) -> a -> b
    $ Int -> a
    forall a. Enum a => Int -> a
    toEnum Int
    a
      fromEnum :: Wrapped a -> Int
    fromEnum (Wrapped a
    a) = a -> Int
    forall a. Enum a => a -> Int
    fromEnum a
    a

    liftOp ::
      (a -> a) ->
      Wrapped a ->
      Wrapped a
    liftOp :: forall a. (a -> a) -> Wrapped a -> Wrapped a
    liftOp a -> a
    op (Wrapped a
    x) = a -> Wrapped a
    forall a. a -> Wrapped a
    Wrapped (a -> Wrapped a) -> a -> Wrapped a
    forall a b. (a -> b) -> a -> b
    $ a -> a
    op a
    x

    liftOp2 ::
      (a -> a -> a) ->
      Wrapped a ->
      Wrapped a ->
      Wrapped a
    liftOp2 :: forall a. (a -> a -> a) -> Wrapped a -> Wrapped a -> Wrapped a
    liftOp2 a -> a -> a
    op (Wrapped a
    x) (Wrapped a
    y) = a -> Wrapped a
    forall a. a -> Wrapped a
    Wrapped (a -> Wrapped a) -> a -> Wrapped a
    forall a b. (a -> b) -> a -> b
    $ a
    x a -> a -> a
    `op` a
    y

    instance (Num a) => Num (Wrapped a) where
      + :: Wrapped a -> Wrapped a -> Wrapped a
    (+) = (a -> a -> a) -> Wrapped a -> Wrapped a -> Wrapped a
    forall a. (a -> a -> a) -> Wrapped a -> Wrapped a -> Wrapped a
    liftOp2 a -> a -> a
    forall a. Num a => a -> a -> a
    (Prelude.+)
      (-) = (a -> a -> a) -> Wrapped a -> Wrapped a -> Wrapped a
    forall a. (a -> a -> a) -> Wrapped a -> Wrapped a -> Wrapped a
    liftOp2 a -> a -> a
    forall a. Num a => a -> a -> a
    (Prelude.-)
      * :: Wrapped a -> Wrapped a -> Wrapped a
    (*) = (a -> a -> a) -> Wrapped a -> Wrapped a -> Wrapped a
    forall a. (a -> a -> a) -> Wrapped a -> Wrapped a -> Wrapped a
    liftOp2 a -> a -> a
    forall a. Num a => a -> a -> a
    (Prelude.*)
      abs :: Wrapped a -> Wrapped a
    abs = (a -> a) -> Wrapped a -> Wrapped a
    forall a. (a -> a) -> Wrapped a -> Wrapped a
    liftOp a -> a
    forall a. Num a => a -> a
    Prelude.abs
      signum :: Wrapped a -> Wrapped a
    signum = (a -> a) -> Wrapped a -> Wrapped a
    forall a. (a -> a) -> Wrapped a -> Wrapped a
    liftOp a -> a
    forall a. Num a => a -> a
    Prelude.signum
      fromInteger :: Integer -> Wrapped a
    fromInteger = a -> Wrapped a
    forall a. a -> Wrapped a
    Wrapped (a -> Wrapped a) -> (Integer -> a) -> Integer -> Wrapped a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Integer -> a
    forall a. Num a => Integer -> a
    Prelude.fromInteger
      negate :: Wrapped a -> Wrapped a
    negate = (a -> a) -> Wrapped a -> Wrapped a
    forall a. (a -> a) -> Wrapped a -> Wrapped a
    liftOp a -> a
    forall a. Num a => a -> a
    Prelude.negate

    instance (Integral a) => IntegralExp (Wrapped a) where
      quot :: Wrapped a -> Wrapped a -> Wrapped a
    quot = (a -> a -> a) -> Wrapped a -> Wrapped a -> Wrapped a
    forall a. (a -> a -> a) -> Wrapped a -> Wrapped a -> Wrapped a
    liftOp2 a -> a -> a
    forall a. Integral a => a -> a -> a
    Prelude.quot
      rem :: Wrapped a -> Wrapped a -> Wrapped a
    rem = (a -> a -> a) -> Wrapped a -> Wrapped a -> Wrapped a
    forall a. (a -> a -> a) -> Wrapped a -> Wrapped a -> Wrapped a
    liftOp2 a -> a -> a
    forall a. Integral a => a -> a -> a
    Prelude.rem
      div :: Wrapped a -> Wrapped a -> Wrapped a
    div = (a -> a -> a) -> Wrapped a -> Wrapped a -> Wrapped a
    forall a. (a -> a -> a) -> Wrapped a -> Wrapped a -> Wrapped a
    liftOp2 a -> a -> a
    forall a. Integral a => a -> a -> a
    Prelude.div
      mod :: Wrapped a -> Wrapped a -> Wrapped a
    mod = (a -> a -> a) -> Wrapped a -> Wrapped a -> Wrapped a
    forall a. (a -> a -> a) -> Wrapped a -> Wrapped a -> Wrapped a
    liftOp2 a -> a -> a
    forall a. Integral a => a -> a -> a
    Prelude.mod
      sgn :: Wrapped a -> Maybe Int
    sgn = Int -> Maybe Int
    forall a. a -> Maybe a
    Just (Int -> Maybe Int) -> (Wrapped a -> Int) -> Wrapped a -> Maybe Int
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Integer -> Int
    forall a b. (Integral a, Num b) => a -> b
    fromIntegral (Integer -> Int) -> (Wrapped a -> Integer) -> Wrapped a -> Int
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Integer -> Integer
    forall a. Num a => a -> a
    signum (Integer -> Integer)
    -> (Wrapped a -> Integer) -> Wrapped a -> Integer
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> Integer
    forall a. Integral a => a -> Integer
    toInteger (a -> Integer) -> (Wrapped a -> a) -> Wrapped a -> Integer
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Wrapped a -> a
    forall a. Wrapped a -> a
    wrappedValue
      pow :: Wrapped a -> Wrapped a -> Wrapped a
    pow = (a -> a -> a) -> Wrapped a -> Wrapped a -> Wrapped a
    forall a. (a -> a -> a) -> Wrapped a -> Wrapped a -> Wrapped a
    liftOp2 a -> a -> a
    forall a b. (Num a, Integral b) => a -> b -> a
    (Prelude.^)