-- |
-- Module:      Data.Chimera
-- Copyright:   (c) 2018-2019 Andrew Lelechenko
-- Licence:     MIT
-- Maintainer:  Andrew Lelechenko <andrew.lelechenko@gmail.com>
--
-- Lazy infinite streams with O(1) indexing.

{-# LANGUAGE BangPatterns          #-}
{-# LANGUAGE CPP                   #-}
{-# LANGUAGE DeriveTraversable     #-}
{-# LANGUAGE FlexibleContexts      #-}
{-# LANGUAGE FlexibleInstances     #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE ScopedTypeVariables   #-}
{-# LANGUAGE TypeApplications      #-}
{-# LANGUAGE TypeFamilies          #-}

module Data.Chimera
  ( -- * Memoization
    memoize
  , memoizeFix

  -- * Chimera
  , Chimera
  , VChimera
  , UChimera

  -- * Construction
  , tabulate
  , tabulateFix
  , tabulateFix'
  , iterate
  , cycle

  -- * Elimination
  , index
  , toList

  -- * Monadic construction
  -- $monadic
  , tabulateM
  , tabulateFixM
  , iterateM

  -- * Subvectors
  -- $subvectors
  , mapSubvectors
  , zipSubvectors
  ) where

import Prelude hiding ((^), (*), div, fromIntegral, not, and, or, cycle, iterate, drop)
import Control.Applicative
import Control.Monad.Fix
import Control.Monad.Zip
import Data.Bits
import Data.Functor.Identity
import qualified Data.Vector as V
import qualified Data.Vector.Generic as G
import qualified Data.Vector.Unboxed as U

#ifdef MIN_VERSION_mtl
import Control.Monad.Reader (MonadReader, ask, local)
#endif
#ifdef MIN_VERSION_distributive
import Data.Distributive
#ifdef MIN_VERSION_adjunctions
import qualified Data.Functor.Rep as Rep
#endif
#endif

import Data.Chimera.Compat
import Data.Chimera.FromIntegral

-- $monadic
-- Be careful: the stream is infinite, so
-- monadic effects must be lazy
-- in order to be executed in a finite time.
--
-- For instance, lazy state monad works fine:
--
-- >>> import Control.Monad.State.Lazy
-- >>> ch = evalState (tabulateM (\i -> do modify (+ i); get)) 0 :: UChimera Word
-- >>> take 10 (toList ch)
-- [0,1,3,6,10,15,21,28,36,45]
--
-- But the same computation in the strict state
-- monad "Control.Monad.State.Strict" diverges.

-- $subvectors
-- Internally 'Chimera' consists of a number of subvectors.
-- Following functions provide a low-level access to them.
-- This ability is especially important for streams of booleans.
--
-- Let us use 'Chimera' to memoize predicates @f1@, @f2@ @::@ 'Word' @->@ 'Bool'.
-- Imagine them both already
-- caught in amber as @ch1@, @ch2@ @::@ 'UChimera' 'Bool',
-- and now we want to memoize @f3 x = f1 x && f2 x@ as @ch3@.
-- One can do it in as follows:
--
-- > ch3 = tabulate (\i -> index ch1 i && index ch2 i)
--
-- There are two unsatisfactory things here. Firstly,
-- even unboxed vectors store only one boolean per byte.
-- We would rather reach out for 'Data.Bit.Bit' wrapper,
-- which provides an instance of unboxed vector
-- with one boolean per bit. Secondly, combining
-- existing predicates by indexing them and tabulating again
-- becomes relatively expensive, given how small and simple
-- our data is. Fortunately, there is an ultra-fast 'Data.Bit.zipBits'
-- to zip bit vectors. We can combine it altogether like this:
--
-- > import Data.Bit
-- > import Data.Bits
-- > ch1 = tabulate (Bit . f1)
-- > ch2 = tabulate (Bit . f2)
-- > ch3 = zipSubvectors (zipBits (.&.)) ch1 ch2

-- | Lazy infinite streams with elements from @a@,
-- backed by a 'G.Vector' @v@ (boxed, unboxed, storable, etc.).
-- Use 'tabulate', 'tabulateFix', etc. to create a stream
-- and 'index' to access its arbitrary elements
-- in constant time.
newtype Chimera v a = Chimera { Chimera v a -> Vector (v a)
_unChimera :: V.Vector (v a) }
  deriving (a -> Chimera v b -> Chimera v a
(a -> b) -> Chimera v a -> Chimera v b
(forall a b. (a -> b) -> Chimera v a -> Chimera v b)
-> (forall a b. a -> Chimera v b -> Chimera v a)
-> Functor (Chimera v)
forall a b. a -> Chimera v b -> Chimera v a
forall a b. (a -> b) -> Chimera v a -> Chimera v b
forall (v :: * -> *) a b.
Functor v =>
a -> Chimera v b -> Chimera v a
forall (v :: * -> *) a b.
Functor v =>
(a -> b) -> Chimera v a -> Chimera v b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: a -> Chimera v b -> Chimera v a
$c<$ :: forall (v :: * -> *) a b.
Functor v =>
a -> Chimera v b -> Chimera v a
fmap :: (a -> b) -> Chimera v a -> Chimera v b
$cfmap :: forall (v :: * -> *) a b.
Functor v =>
(a -> b) -> Chimera v a -> Chimera v b
Functor, Chimera v a -> Bool
(a -> m) -> Chimera v a -> m
(a -> b -> b) -> b -> Chimera v a -> b
(forall m. Monoid m => Chimera v m -> m)
-> (forall m a. Monoid m => (a -> m) -> Chimera v a -> m)
-> (forall m a. Monoid m => (a -> m) -> Chimera v a -> m)
-> (forall a b. (a -> b -> b) -> b -> Chimera v a -> b)
-> (forall a b. (a -> b -> b) -> b -> Chimera v a -> b)
-> (forall b a. (b -> a -> b) -> b -> Chimera v a -> b)
-> (forall b a. (b -> a -> b) -> b -> Chimera v a -> b)
-> (forall a. (a -> a -> a) -> Chimera v a -> a)
-> (forall a. (a -> a -> a) -> Chimera v a -> a)
-> (forall a. Chimera v a -> [a])
-> (forall a. Chimera v a -> Bool)
-> (forall a. Chimera v a -> Int)
-> (forall a. Eq a => a -> Chimera v a -> Bool)
-> (forall a. Ord a => Chimera v a -> a)
-> (forall a. Ord a => Chimera v a -> a)
-> (forall a. Num a => Chimera v a -> a)
-> (forall a. Num a => Chimera v a -> a)
-> Foldable (Chimera v)
forall a. Eq a => a -> Chimera v a -> Bool
forall a. Num a => Chimera v a -> a
forall a. Ord a => Chimera v a -> a
forall m. Monoid m => Chimera v m -> m
forall a. Chimera v a -> Bool
forall a. Chimera v a -> Int
forall a. Chimera v a -> [a]
forall a. (a -> a -> a) -> Chimera v a -> a
forall m a. Monoid m => (a -> m) -> Chimera v a -> m
forall b a. (b -> a -> b) -> b -> Chimera v a -> b
forall a b. (a -> b -> b) -> b -> Chimera v a -> b
forall (v :: * -> *) a.
(Foldable v, Eq a) =>
a -> Chimera v a -> Bool
forall (v :: * -> *) a. (Foldable v, Num a) => Chimera v a -> a
forall (v :: * -> *) a. (Foldable v, Ord a) => Chimera v a -> a
forall (v :: * -> *) m. (Foldable v, Monoid m) => Chimera v m -> m
forall (v :: * -> *) a. Foldable v => Chimera v a -> Bool
forall (v :: * -> *) a. Foldable v => Chimera v a -> Int
forall (v :: * -> *) a. Foldable v => Chimera v a -> [a]
forall (v :: * -> *) a.
Foldable v =>
(a -> a -> a) -> Chimera v a -> a
forall (v :: * -> *) m a.
(Foldable v, Monoid m) =>
(a -> m) -> Chimera v a -> m
forall (v :: * -> *) b a.
Foldable v =>
(b -> a -> b) -> b -> Chimera v a -> b
forall (v :: * -> *) a b.
Foldable v =>
(a -> b -> b) -> b -> Chimera v 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
product :: Chimera v a -> a
$cproduct :: forall (v :: * -> *) a. (Foldable v, Num a) => Chimera v a -> a
sum :: Chimera v a -> a
$csum :: forall (v :: * -> *) a. (Foldable v, Num a) => Chimera v a -> a
minimum :: Chimera v a -> a
$cminimum :: forall (v :: * -> *) a. (Foldable v, Ord a) => Chimera v a -> a
maximum :: Chimera v a -> a
$cmaximum :: forall (v :: * -> *) a. (Foldable v, Ord a) => Chimera v a -> a
elem :: a -> Chimera v a -> Bool
$celem :: forall (v :: * -> *) a.
(Foldable v, Eq a) =>
a -> Chimera v a -> Bool
length :: Chimera v a -> Int
$clength :: forall (v :: * -> *) a. Foldable v => Chimera v a -> Int
null :: Chimera v a -> Bool
$cnull :: forall (v :: * -> *) a. Foldable v => Chimera v a -> Bool
toList :: Chimera v a -> [a]
$ctoList :: forall (v :: * -> *) a. Foldable v => Chimera v a -> [a]
foldl1 :: (a -> a -> a) -> Chimera v a -> a
$cfoldl1 :: forall (v :: * -> *) a.
Foldable v =>
(a -> a -> a) -> Chimera v a -> a
foldr1 :: (a -> a -> a) -> Chimera v a -> a
$cfoldr1 :: forall (v :: * -> *) a.
Foldable v =>
(a -> a -> a) -> Chimera v a -> a
foldl' :: (b -> a -> b) -> b -> Chimera v a -> b
$cfoldl' :: forall (v :: * -> *) b a.
Foldable v =>
(b -> a -> b) -> b -> Chimera v a -> b
foldl :: (b -> a -> b) -> b -> Chimera v a -> b
$cfoldl :: forall (v :: * -> *) b a.
Foldable v =>
(b -> a -> b) -> b -> Chimera v a -> b
foldr' :: (a -> b -> b) -> b -> Chimera v a -> b
$cfoldr' :: forall (v :: * -> *) a b.
Foldable v =>
(a -> b -> b) -> b -> Chimera v a -> b
foldr :: (a -> b -> b) -> b -> Chimera v a -> b
$cfoldr :: forall (v :: * -> *) a b.
Foldable v =>
(a -> b -> b) -> b -> Chimera v a -> b
foldMap' :: (a -> m) -> Chimera v a -> m
$cfoldMap' :: forall (v :: * -> *) m a.
(Foldable v, Monoid m) =>
(a -> m) -> Chimera v a -> m
foldMap :: (a -> m) -> Chimera v a -> m
$cfoldMap :: forall (v :: * -> *) m a.
(Foldable v, Monoid m) =>
(a -> m) -> Chimera v a -> m
fold :: Chimera v m -> m
$cfold :: forall (v :: * -> *) m. (Foldable v, Monoid m) => Chimera v m -> m
Foldable, Functor (Chimera v)
Foldable (Chimera v)
Functor (Chimera v)
-> Foldable (Chimera v)
-> (forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> Chimera v a -> f (Chimera v b))
-> (forall (f :: * -> *) a.
    Applicative f =>
    Chimera v (f a) -> f (Chimera v a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> Chimera v a -> m (Chimera v b))
-> (forall (m :: * -> *) a.
    Monad m =>
    Chimera v (m a) -> m (Chimera v a))
-> Traversable (Chimera v)
(a -> f b) -> Chimera v a -> f (Chimera v b)
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 (v :: * -> *). Traversable v => Functor (Chimera v)
forall (v :: * -> *). Traversable v => Foldable (Chimera v)
forall (v :: * -> *) (m :: * -> *) a.
(Traversable v, Monad m) =>
Chimera v (m a) -> m (Chimera v a)
forall (v :: * -> *) (f :: * -> *) a.
(Traversable v, Applicative f) =>
Chimera v (f a) -> f (Chimera v a)
forall (v :: * -> *) (m :: * -> *) a b.
(Traversable v, Monad m) =>
(a -> m b) -> Chimera v a -> m (Chimera v b)
forall (v :: * -> *) (f :: * -> *) a b.
(Traversable v, Applicative f) =>
(a -> f b) -> Chimera v a -> f (Chimera v b)
forall (m :: * -> *) a.
Monad m =>
Chimera v (m a) -> m (Chimera v a)
forall (f :: * -> *) a.
Applicative f =>
Chimera v (f a) -> f (Chimera v a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Chimera v a -> m (Chimera v b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Chimera v a -> f (Chimera v b)
sequence :: Chimera v (m a) -> m (Chimera v a)
$csequence :: forall (v :: * -> *) (m :: * -> *) a.
(Traversable v, Monad m) =>
Chimera v (m a) -> m (Chimera v a)
mapM :: (a -> m b) -> Chimera v a -> m (Chimera v b)
$cmapM :: forall (v :: * -> *) (m :: * -> *) a b.
(Traversable v, Monad m) =>
(a -> m b) -> Chimera v a -> m (Chimera v b)
sequenceA :: Chimera v (f a) -> f (Chimera v a)
$csequenceA :: forall (v :: * -> *) (f :: * -> *) a.
(Traversable v, Applicative f) =>
Chimera v (f a) -> f (Chimera v a)
traverse :: (a -> f b) -> Chimera v a -> f (Chimera v b)
$ctraverse :: forall (v :: * -> *) (f :: * -> *) a b.
(Traversable v, Applicative f) =>
(a -> f b) -> Chimera v a -> f (Chimera v b)
$cp2Traversable :: forall (v :: * -> *). Traversable v => Foldable (Chimera v)
$cp1Traversable :: forall (v :: * -> *). Traversable v => Functor (Chimera v)
Traversable)

-- | Streams backed by boxed vectors.
type VChimera = Chimera V.Vector

-- | Streams backed by unboxed vectors.
type UChimera = Chimera U.Vector

-- | 'pure' creates a constant stream.
instance Applicative (Chimera V.Vector) where
  pure :: a -> Chimera Vector a
pure   = (Word -> a) -> Chimera Vector a
forall (v :: * -> *) a. Vector v a => (Word -> a) -> Chimera v a
tabulate   ((Word -> a) -> Chimera Vector a)
-> (a -> Word -> a) -> a -> Chimera Vector a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Word -> a
forall a b. a -> b -> a
const
  <*> :: Chimera Vector (a -> b) -> Chimera Vector a -> Chimera Vector b
(<*>)  = (Vector (a -> b) -> Vector a -> Vector b)
-> Chimera Vector (a -> b) -> Chimera Vector a -> Chimera Vector b
forall (u :: * -> *) a (v :: * -> *) b (w :: * -> *) c.
(Vector u a, Vector v b, Vector w c) =>
(u a -> v b -> w c) -> Chimera u a -> Chimera v b -> Chimera w c
zipSubvectors Vector (a -> b) -> Vector a -> Vector b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
(<*>)
#if __GLASGOW_HASKELL__ > 801
  liftA2 :: (a -> b -> c)
-> Chimera Vector a -> Chimera Vector b -> Chimera Vector c
liftA2 a -> b -> c
f = (Vector a -> Vector b -> Vector c)
-> Chimera Vector a -> Chimera Vector b -> Chimera Vector c
forall (u :: * -> *) a (v :: * -> *) b (w :: * -> *) c.
(Vector u a, Vector v b, Vector w c) =>
(u a -> v b -> w c) -> Chimera u a -> Chimera v b -> Chimera w c
zipSubvectors ((a -> b -> c) -> Vector a -> Vector b -> Vector c
forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> f a -> f b -> f c
liftA2 a -> b -> c
f)
#endif

instance Monad (Chimera V.Vector) where
  Chimera Vector a
m >>= :: Chimera Vector a -> (a -> Chimera Vector b) -> Chimera Vector b
>>= a -> Chimera Vector b
f = (Word -> b) -> Chimera Vector b
forall (v :: * -> *) a. Vector v a => (Word -> a) -> Chimera v a
tabulate ((Word -> b) -> Chimera Vector b)
-> (Word -> b) -> Chimera Vector b
forall a b. (a -> b) -> a -> b
$ \Word
w -> Chimera Vector b -> Word -> b
forall (v :: * -> *) a. Vector v a => Chimera v a -> Word -> a
index (a -> Chimera Vector b
f (Chimera Vector a -> Word -> a
forall (v :: * -> *) a. Vector v a => Chimera v a -> Word -> a
index Chimera Vector a
m Word
w)) Word
w

instance MonadFix (Chimera V.Vector) where
  mfix :: (a -> Chimera Vector a) -> Chimera Vector a
mfix = (Word -> a) -> Chimera Vector a
forall (v :: * -> *) a. Vector v a => (Word -> a) -> Chimera v a
tabulate ((Word -> a) -> Chimera Vector a)
-> ((a -> Chimera Vector a) -> Word -> a)
-> (a -> Chimera Vector a)
-> Chimera Vector a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Word -> a) -> Word -> a
forall (m :: * -> *) a. MonadFix m => (a -> m a) -> m a
mfix ((a -> Word -> a) -> Word -> a)
-> ((a -> Chimera Vector a) -> a -> Word -> a)
-> (a -> Chimera Vector a)
-> Word
-> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Chimera Vector a -> Word -> a)
-> (a -> Chimera Vector a) -> a -> Word -> a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap Chimera Vector a -> Word -> a
forall (v :: * -> *) a. Vector v a => Chimera v a -> Word -> a
index

instance MonadZip (Chimera V.Vector) where
  mzip :: Chimera Vector a -> Chimera Vector b -> Chimera Vector (a, b)
mzip Chimera Vector a
as Chimera Vector b
bs = (Word -> (a, b)) -> Chimera Vector (a, b)
forall (v :: * -> *) a. Vector v a => (Word -> a) -> Chimera v a
tabulate (\Word
w -> (Chimera Vector a -> Word -> a
forall (v :: * -> *) a. Vector v a => Chimera v a -> Word -> a
index Chimera Vector a
as Word
w, Chimera Vector b -> Word -> b
forall (v :: * -> *) a. Vector v a => Chimera v a -> Word -> a
index Chimera Vector b
bs Word
w))
  mzipWith :: (a -> b -> c)
-> Chimera Vector a -> Chimera Vector b -> Chimera Vector c
mzipWith a -> b -> c
f Chimera Vector a
as Chimera Vector b
bs = (Word -> c) -> Chimera Vector c
forall (v :: * -> *) a. Vector v a => (Word -> a) -> Chimera v a
tabulate ((Word -> c) -> Chimera Vector c)
-> (Word -> c) -> Chimera Vector c
forall a b. (a -> b) -> a -> b
$ \Word
w -> a -> b -> c
f (Chimera Vector a -> Word -> a
forall (v :: * -> *) a. Vector v a => Chimera v a -> Word -> a
index Chimera Vector a
as Word
w) (Chimera Vector b -> Word -> b
forall (v :: * -> *) a. Vector v a => Chimera v a -> Word -> a
index Chimera Vector b
bs Word
w)

#ifdef MIN_VERSION_mtl
instance MonadReader Word (Chimera V.Vector) where
  ask :: Chimera Vector Word
ask = (Word -> Word) -> Chimera Vector Word
forall (v :: * -> *) a. Vector v a => (Word -> a) -> Chimera v a
tabulate Word -> Word
forall a. a -> a
id
  local :: (Word -> Word) -> Chimera Vector a -> Chimera Vector a
local = (Chimera Vector a -> (Word -> Word) -> Chimera Vector a)
-> (Word -> Word) -> Chimera Vector a -> Chimera Vector a
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((Chimera Vector a -> (Word -> Word) -> Chimera Vector a)
 -> (Word -> Word) -> Chimera Vector a -> Chimera Vector a)
-> (Chimera Vector a -> (Word -> Word) -> Chimera Vector a)
-> (Word -> Word)
-> Chimera Vector a
-> Chimera Vector a
forall a b. (a -> b) -> a -> b
$ ((Word -> a) -> Chimera Vector a
forall (v :: * -> *) a. Vector v a => (Word -> a) -> Chimera v a
tabulate ((Word -> a) -> Chimera Vector a)
-> ((Word -> Word) -> Word -> a)
-> (Word -> Word)
-> Chimera Vector a
forall b c a. (b -> c) -> (a -> b) -> a -> c
.) (((Word -> Word) -> Word -> a)
 -> (Word -> Word) -> Chimera Vector a)
-> (Chimera Vector a -> (Word -> Word) -> Word -> a)
-> Chimera Vector a
-> (Word -> Word)
-> Chimera Vector a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Word -> a) -> (Word -> Word) -> Word -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
(.) ((Word -> a) -> (Word -> Word) -> Word -> a)
-> (Chimera Vector a -> Word -> a)
-> Chimera Vector a
-> (Word -> Word)
-> Word
-> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Chimera Vector a -> Word -> a
forall (v :: * -> *) a. Vector v a => Chimera v a -> Word -> a
index
#endif

#ifdef MIN_VERSION_distributive
instance Distributive (Chimera V.Vector) where
  distribute :: f (Chimera Vector a) -> Chimera Vector (f a)
distribute = (Word -> f a) -> Chimera Vector (f a)
forall (v :: * -> *) a. Vector v a => (Word -> a) -> Chimera v a
tabulate ((Word -> f a) -> Chimera Vector (f a))
-> (f (Chimera Vector a) -> Word -> f a)
-> f (Chimera Vector a)
-> Chimera Vector (f a)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Word -> f (Chimera Vector a) -> f a)
-> f (Chimera Vector a) -> Word -> f a
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((Chimera Vector a -> a) -> f (Chimera Vector a) -> f a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap ((Chimera Vector a -> a) -> f (Chimera Vector a) -> f a)
-> (Word -> Chimera Vector a -> a)
-> Word
-> f (Chimera Vector a)
-> f a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Chimera Vector a -> Word -> a) -> Word -> Chimera Vector a -> a
forall a b c. (a -> b -> c) -> b -> a -> c
flip Chimera Vector a -> Word -> a
forall (v :: * -> *) a. Vector v a => Chimera v a -> Word -> a
index)
  collect :: (a -> Chimera Vector b) -> f a -> Chimera Vector (f b)
collect a -> Chimera Vector b
f = (Word -> f b) -> Chimera Vector (f b)
forall (v :: * -> *) a. Vector v a => (Word -> a) -> Chimera v a
tabulate ((Word -> f b) -> Chimera Vector (f b))
-> (f a -> Word -> f b) -> f a -> Chimera Vector (f b)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Word -> f a -> f b) -> f a -> Word -> f b
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((a -> b) -> f a -> f b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
(<$>) ((a -> b) -> f a -> f b) -> (Word -> a -> b) -> Word -> f a -> f b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Chimera Vector b -> b) -> (a -> Chimera Vector b) -> a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Chimera Vector b
f) ((Chimera Vector b -> b) -> a -> b)
-> (Word -> Chimera Vector b -> b) -> Word -> a -> b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Chimera Vector b -> Word -> b) -> Word -> Chimera Vector b -> b
forall a b c. (a -> b -> c) -> b -> a -> c
flip Chimera Vector b -> Word -> b
forall (v :: * -> *) a. Vector v a => Chimera v a -> Word -> a
index)

#ifdef MIN_VERSION_adjunctions
instance Rep.Representable (Chimera V.Vector) where
  type Rep (Chimera V.Vector) = Word
  tabulate :: (Rep (Chimera Vector) -> a) -> Chimera Vector a
tabulate = (Rep (Chimera Vector) -> a) -> Chimera Vector a
forall (v :: * -> *) a. Vector v a => (Word -> a) -> Chimera v a
tabulate
  index :: Chimera Vector a -> Rep (Chimera Vector) -> a
index = Chimera Vector a -> Rep (Chimera Vector) -> a
forall (v :: * -> *) a. Vector v a => Chimera v a -> Word -> a
index
#endif
#endif

bits :: Int
bits :: Int
bits = Word -> Int
fbs (Word
0 :: Word)

-- | Create a stream of values of a given function.
-- Once created it can be accessed via 'index' or 'toList'.
--
-- >>> ch = tabulate (^ 2) :: UChimera Word
-- >>> index ch 9
-- 81
-- >>> take 10 (toList ch)
-- [0,1,4,9,16,25,36,49,64,81]
tabulate :: G.Vector v a => (Word -> a) -> Chimera v a
tabulate :: (Word -> a) -> Chimera v a
tabulate Word -> a
f = Identity (Chimera v a) -> Chimera v a
forall a. Identity a -> a
runIdentity (Identity (Chimera v a) -> Chimera v a)
-> Identity (Chimera v a) -> Chimera v a
forall a b. (a -> b) -> a -> b
$ (Word -> Identity a) -> Identity (Chimera v a)
forall (m :: * -> *) (v :: * -> *) a.
(Monad m, Vector v a) =>
(Word -> m a) -> m (Chimera v a)
tabulateM (a -> Identity a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (a -> Identity a) -> (Word -> a) -> Word -> Identity a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word -> a
f)

-- | Monadic version of 'tabulate'.
tabulateM
  :: forall m v a.
     (Monad m, G.Vector v a)
  => (Word -> m a)
  -> m (Chimera v a)
tabulateM :: (Word -> m a) -> m (Chimera v a)
tabulateM Word -> m a
f = Vector (v a) -> Chimera v a
forall (v :: * -> *) a. Vector (v a) -> Chimera v a
Chimera (Vector (v a) -> Chimera v a)
-> m (Vector (v a)) -> m (Chimera v a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Int -> (Int -> m (v a)) -> m (Vector (v a))
forall (m :: * -> *) a.
Monad m =>
Int -> (Int -> m a) -> m (Vector a)
V.generateM (Int
bits Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) Int -> m (v a)
tabulateSubVector
  where
    tabulateSubVector :: Int -> m (v a)
    tabulateSubVector :: Int -> m (v a)
tabulateSubVector Int
0 = a -> v a
forall (v :: * -> *) a. Vector v a => a -> v a
G.singleton (a -> v a) -> m a -> m (v a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Word -> m a
f Word
0
    tabulateSubVector Int
i = Int -> (Int -> m a) -> m (v a)
forall (m :: * -> *) (v :: * -> *) a.
(Monad m, Vector v a) =>
Int -> (Int -> m a) -> m (v a)
G.generateM Int
ii (\Int
j -> Word -> m a
f (Int -> Word
int2word (Int
ii Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
j)))
      where
        ii :: Int
ii = Int
1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`unsafeShiftL` (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)

{-# SPECIALIZE tabulateM :: G.Vector v a => (Word -> Identity a) -> Identity (Chimera v a) #-}

-- | For a given @f@ create a stream of values of a recursive function 'fix' @f@.
-- Once created it can be accessed via 'index' or 'toList'.
--
-- For example, imagine that we want to tabulate
-- <https://en.wikipedia.org/wiki/Catalan_number Catalan numbers>:
--
-- >>> catalan n = if n == 0 then 1 else sum [ catalan i * catalan (n - 1 - i) | i <- [0 .. n - 1] ]
--
-- Can we find @catalanF@ such that @catalan@ = 'fix' @catalanF@?
-- Just replace all recursive calls to @catalan@ with @f@:
--
-- >>> catalanF f n = if n == 0 then 1 else sum [ f i * f (n - 1 - i) | i <- [0 .. n - 1] ]
--
-- Now we are ready to use 'tabulateFix':
--
-- >>> ch = tabulateFix catalanF :: VChimera Integer
-- >>> index ch 9
-- 4862
-- >>> take 10 (toList ch)
-- [1,1,2,5,14,42,132,429,1430,4862]
--
-- __Note__: Only recursive function calls with decreasing arguments are memoized.
-- If full memoization is desired, use 'tabulateFix'' instead.
tabulateFix :: G.Vector v a => ((Word -> a) -> Word -> a) -> Chimera v a
tabulateFix :: ((Word -> a) -> Word -> a) -> Chimera v a
tabulateFix (Word -> a) -> Word -> a
uf = Identity (Chimera v a) -> Chimera v a
forall a. Identity a -> a
runIdentity (Identity (Chimera v a) -> Chimera v a)
-> Identity (Chimera v a) -> Chimera v a
forall a b. (a -> b) -> a -> b
$ ((Word -> Identity a) -> Word -> Identity a)
-> Identity (Chimera v a)
forall (m :: * -> *) (v :: * -> *) a.
(Monad m, Vector v a) =>
((Word -> m a) -> Word -> m a) -> m (Chimera v a)
tabulateFixM ((a -> Identity a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (a -> Identity a) -> (Word -> a) -> Word -> Identity a
forall b c a. (b -> c) -> (a -> b) -> a -> c
.) ((Word -> a) -> Word -> Identity a)
-> ((Word -> Identity a) -> Word -> a)
-> (Word -> Identity a)
-> Word
-> Identity a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Word -> a) -> Word -> a
uf ((Word -> a) -> Word -> a)
-> ((Word -> Identity a) -> Word -> a)
-> (Word -> Identity a)
-> Word
-> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Identity a -> a
forall a. Identity a -> a
runIdentity (Identity a -> a) -> (Word -> Identity a) -> Word -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
.))

-- | Fully memoizing version of 'tabulateFix'.
-- This function will tabulate every recursive call,
-- but might allocate a lot of memory in doing so.
-- For example, the following piece of code calculates the
-- highest number reached by the
-- <https://en.wikipedia.org/wiki/Collatz_conjecture#Statement_of_the_problem Collatz sequence>
-- of a given number, but also allocates tens of gigabytes of memory,
-- because the Collatz sequence will spike to very high numbers.
--
-- >>> collatzF :: (Word -> Word) -> (Word -> Word)
-- >>> collatzF _ 0 = 0
-- >>> collatzF f n = if n <= 2 then 4 else n `max` f (if even n then n `quot` 2 else 3 * n + 1)
-- >>>
-- >>> maximumBy (comparing $ index $ tabulateFix' collatzF) [0..1000000]
-- ...
--
-- Using 'memoizeFix' instead fixes the problem:
--
-- >>> maximumBy (comparing $ memoizeFix collatzF) [0..1000000]
-- 56991483520
tabulateFix' :: G.Vector v a => ((Word -> a) -> Word -> a) -> Chimera v a
tabulateFix' :: ((Word -> a) -> Word -> a) -> Chimera v a
tabulateFix' (Word -> a) -> Word -> a
uf = Identity (Chimera v a) -> Chimera v a
forall a. Identity a -> a
runIdentity (Identity (Chimera v a) -> Chimera v a)
-> Identity (Chimera v a) -> Chimera v a
forall a b. (a -> b) -> a -> b
$ ((Word -> Identity a) -> Word -> Identity a)
-> Identity (Chimera v a)
forall (m :: * -> *) (v :: * -> *) a.
(Monad m, Vector v a) =>
((Word -> m a) -> Word -> m a) -> m (Chimera v a)
tabulateFixM' ((a -> Identity a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (a -> Identity a) -> (Word -> a) -> Word -> Identity a
forall b c a. (b -> c) -> (a -> b) -> a -> c
.) ((Word -> a) -> Word -> Identity a)
-> ((Word -> Identity a) -> Word -> a)
-> (Word -> Identity a)
-> Word
-> Identity a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Word -> a) -> Word -> a
uf ((Word -> a) -> Word -> a)
-> ((Word -> Identity a) -> Word -> a)
-> (Word -> Identity a)
-> Word
-> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Identity a -> a
forall a. Identity a -> a
runIdentity (Identity a -> a) -> (Word -> Identity a) -> Word -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
.))

-- | Monadic version of 'tabulateFix'.
-- There are no particular guarantees about the order of recursive calls:
-- they may be executed more than once or executed in different order.
-- That said, monadic effects must be idempotent and commutative.
tabulateFixM
  :: forall m v a.
     (Monad m, G.Vector v a)
  => ((Word -> m a) -> Word -> m a)
  -> m (Chimera v a)
tabulateFixM :: ((Word -> m a) -> Word -> m a) -> m (Chimera v a)
tabulateFixM = Strategy -> ((Word -> m a) -> Word -> m a) -> m (Chimera v a)
forall (m :: * -> *) (v :: * -> *) a.
(Monad m, Vector v a) =>
Strategy -> ((Word -> m a) -> Word -> m a) -> m (Chimera v a)
tabulateFixM_ Strategy
Downwards

{-# SPECIALIZE tabulateFixM :: G.Vector v a => ((Word -> Identity a) -> Word -> Identity a) -> Identity (Chimera v a) #-}

-- | Monadic version of 'tabulateFix''.
tabulateFixM'
  :: forall m v a.
     (Monad m, G.Vector v a)
  => ((Word -> m a) -> Word -> m a)
  -> m (Chimera v a)
tabulateFixM' :: ((Word -> m a) -> Word -> m a) -> m (Chimera v a)
tabulateFixM' = Strategy -> ((Word -> m a) -> Word -> m a) -> m (Chimera v a)
forall (m :: * -> *) (v :: * -> *) a.
(Monad m, Vector v a) =>
Strategy -> ((Word -> m a) -> Word -> m a) -> m (Chimera v a)
tabulateFixM_ Strategy
Full

-- | Memoization strategy, only used by 'tabulateFixM_'.
data Strategy = Full | Downwards

-- | Internal implementation for 'tabulateFixM' and 'tabulateFixM''.
tabulateFixM_
  :: forall m v a.
     (Monad m, G.Vector v a)
  => Strategy
  -> ((Word -> m a) -> Word -> m a)
  -> m (Chimera v a)
tabulateFixM_ :: Strategy -> ((Word -> m a) -> Word -> m a) -> m (Chimera v a)
tabulateFixM_ Strategy
strat (Word -> m a) -> Word -> m a
f = m (Chimera v a)
result
  where
    result :: m (Chimera v a)
    result :: m (Chimera v a)
result = Vector (v a) -> Chimera v a
forall (v :: * -> *) a. Vector (v a) -> Chimera v a
Chimera (Vector (v a) -> Chimera v a)
-> m (Vector (v a)) -> m (Chimera v a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Int -> (Int -> m (v a)) -> m (Vector (v a))
forall (m :: * -> *) a.
Monad m =>
Int -> (Int -> m a) -> m (Vector a)
V.generateM (Int
bits Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
1) Int -> m (v a)
tabulateSubVector

    tabulateSubVector :: Int -> m (v a)
    tabulateSubVector :: Int -> m (v a)
tabulateSubVector Int
0 = a -> v a
forall (v :: * -> *) a. Vector v a => a -> v a
G.singleton (a -> v a) -> m a -> m (v a)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> case Strategy
strat of
      Strategy
Downwards -> ((Word -> m a) -> Word -> m a) -> Word -> m a
forall a. (a -> a) -> a
fix (Word -> m a) -> Word -> m a
f Word
0
      Strategy
Full      -> (Word -> m a) -> Word -> m a
f (\Word
k -> (Chimera v a -> Word -> a) -> Word -> Chimera v a -> a
forall a b c. (a -> b -> c) -> b -> a -> c
flip Chimera v a -> Word -> a
forall (v :: * -> *) a. Vector v a => Chimera v a -> Word -> a
index Word
k (Chimera v a -> a) -> m (Chimera v a) -> m a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> m (Chimera v a)
result) Word
0
    tabulateSubVector Int
i = m (v a)
subResult
      where
        subResult :: m (v a)
subResult      = Int -> (Int -> m a) -> m (v a)
forall (m :: * -> *) (v :: * -> *) a.
(Monad m, Vector v a) =>
Int -> (Int -> m a) -> m (v a)
G.generateM Int
ii (\Int
j -> (Word -> m a) -> Word -> m a
f Word -> m a
fixF (Int -> Word
int2word (Int
ii Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
j)))
        subResultBoxed :: m (Vector a)
subResultBoxed = Int -> (Int -> m a) -> m (Vector a)
forall (m :: * -> *) a.
Monad m =>
Int -> (Int -> m a) -> m (Vector a)
V.generateM Int
ii (\Int
j -> (Word -> m a) -> Word -> m a
f Word -> m a
fixF (Int -> Word
int2word (Int
ii Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
j)))
        ii :: Int
ii = Int
1 Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`unsafeShiftL` (Int
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)

        fixF :: Word -> m a
        fixF :: Word -> m a
fixF Word
k
          | Word
k Word -> Word -> Bool
forall a. Ord a => a -> a -> Bool
< Int -> Word
int2word Int
ii
          = (Chimera v a -> Word -> a) -> Word -> Chimera v a -> a
forall a b c. (a -> b -> c) -> b -> a -> c
flip Chimera v a -> Word -> a
forall (v :: * -> *) a. Vector v a => Chimera v a -> Word -> a
index Word
k (Chimera v a -> a) -> m (Chimera v a) -> m a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> m (Chimera v a)
result
          | Word
k Word -> Word -> Bool
forall a. Ord a => a -> a -> Bool
<= Int -> Word
int2word Int
ii Word -> Int -> Word
forall a. Bits a => a -> Int -> a
`shiftL` Int
1 Word -> Word -> Word
forall a. Num a => a -> a -> a
- Word
1
          = (Vector a -> Int -> a
forall a. Vector a -> Int -> a
`V.unsafeIndex` (Word -> Int
word2int Word
k Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
ii)) (Vector a -> a) -> m (Vector a) -> m a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> m (Vector a)
subResultBoxed
          | Bool
otherwise
          = case Strategy
strat of
              Strategy
Downwards -> (Word -> m a) -> Word -> m a
f Word -> m a
fixF Word
k
              Strategy
Full      -> (Chimera v a -> Word -> a) -> Word -> Chimera v a -> a
forall a b c. (a -> b -> c) -> b -> a -> c
flip Chimera v a -> Word -> a
forall (v :: * -> *) a. Vector v a => Chimera v a -> Word -> a
index Word
k (Chimera v a -> a) -> m (Chimera v a) -> m a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> m (Chimera v a)
result

-- | 'iterate' @f@ @x@ returns an infinite stream
-- of repeated applications of @f@ to @x@.
--
-- >>> ch = iterate (+ 1) 0 :: UChimera Int
-- >>> take 10 (toList ch)
-- [0,1,2,3,4,5,6,7,8,9]
iterate :: G.Vector v a => (a -> a) -> a -> Chimera v a
iterate :: (a -> a) -> a -> Chimera v a
iterate a -> a
f = Identity (Chimera v a) -> Chimera v a
forall a. Identity a -> a
runIdentity (Identity (Chimera v a) -> Chimera v a)
-> (a -> Identity (Chimera v a)) -> a -> Chimera v a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Identity a) -> a -> Identity (Chimera v a)
forall (m :: * -> *) (v :: * -> *) a.
(Monad m, Vector v a) =>
(a -> m a) -> a -> m (Chimera v a)
iterateM (a -> Identity a
forall (f :: * -> *) a. Applicative f => a -> f a
pure (a -> Identity a) -> (a -> a) -> a -> Identity a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> a
f)

-- | Monadic version of 'iterate'.
iterateM :: forall m v a. (Monad m, G.Vector v a) => (a -> m a) -> a -> m (Chimera v a)
iterateM :: (a -> m a) -> a -> m (Chimera v a)
iterateM a -> m a
f a
seed = do
  a
nextSeed <- a -> m a
f a
seed
  let z :: v a
z = a -> v a
forall (v :: * -> *) a. Vector v a => a -> v a
G.singleton a
seed
  Vector (v a)
zs <- Int -> (v a -> m (v a)) -> v a -> m (Vector (v a))
forall (m :: * -> *) a.
Monad m =>
Int -> (a -> m a) -> a -> m (Vector a)
V.iterateNM Int
bits v a -> m (v a)
go (a -> v a
forall (v :: * -> *) a. Vector v a => a -> v a
G.singleton a
nextSeed)
  Chimera v a -> m (Chimera v a)
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Chimera v a -> m (Chimera v a)) -> Chimera v a -> m (Chimera v a)
forall a b. (a -> b) -> a -> b
$ Vector (v a) -> Chimera v a
forall (v :: * -> *) a. Vector (v a) -> Chimera v a
Chimera (Vector (v a) -> Chimera v a) -> Vector (v a) -> Chimera v a
forall a b. (a -> b) -> a -> b
$ v a
z v a -> Vector (v a) -> Vector (v a)
forall a. a -> Vector a -> Vector a
`V.cons` Vector (v a)
zs
  where
    go :: v a -> m (v a)
    go :: v a -> m (v a)
go v a
vec = do
      a
nextSeed <- a -> m a
f (v a -> a
forall (v :: * -> *) a. Vector v a => v a -> a
G.unsafeLast v a
vec)
      Int -> (a -> m a) -> a -> m (v a)
forall (m :: * -> *) (v :: * -> *) a.
(Monad m, Vector v a) =>
Int -> (a -> m a) -> a -> m (v a)
G.iterateNM (v a -> Int
forall (v :: * -> *) a. Vector v a => v a -> Int
G.length v a
vec Int -> Int -> Int
forall a. Bits a => a -> Int -> a
`shiftL` Int
1) a -> m a
f a
nextSeed

{-# SPECIALIZE iterateM :: G.Vector v a => (a -> Identity a) -> a -> Identity (Chimera v a) #-}

-- | Index a stream in a constant time.
--
-- >>> ch = tabulate (^ 2) :: UChimera Word
-- >>> index ch 9
-- 81
index :: G.Vector v a => Chimera v a -> Word -> a
index :: Chimera v a -> Word -> a
index (Chimera Vector (v a)
vs) Word
i =
  (Vector (v a)
vs Vector (v a) -> Int -> v a
forall a. Vector a -> Int -> a
`V.unsafeIndex` (Word -> Int
fbs Word
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
lz))
  v a -> Int -> a
forall (v :: * -> *) a. Vector v a => v a -> Int -> a
`G.unsafeIndex`
  Word -> Int
word2int (Word
i Word -> Word -> Word
forall a. Bits a => a -> a -> a
.&. Word -> Word
forall a. Bits a => a -> a
complement ((Word
1 Word -> Int -> Word
forall a. Bits a => a -> Int -> a
`shiftL` (Word -> Int
fbs Word
i Int -> Int -> Int
forall a. Num a => a -> a -> a
- Int
1)) Word -> Int -> Word
forall a. Bits a => a -> Int -> a
`unsafeShiftR` Int
lz))
  where
    lz :: Int
    !lz :: Int
lz = Word -> Int
word2int (Word -> Word
clz Word
i)
{-# INLINE index #-}

-- | Convert a stream to an infinite list.
--
-- >>> ch = tabulate (^ 2) :: UChimera Word
-- >>> take 10 (toList ch)
-- [0,1,4,9,16,25,36,49,64,81]
toList :: G.Vector v a => Chimera v a -> [a]
toList :: Chimera v a -> [a]
toList (Chimera Vector (v a)
vs) = (v a -> [a]) -> Vector (v a) -> [a]
forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap v a -> [a]
forall (v :: * -> *) a. Vector v a => v a -> [a]
G.toList Vector (v a)
vs

-- | Return an infinite repetion of a given vector.
-- Throw an error on an empty vector.
--
-- >>> ch = cycle (Data.Vector.fromList [4, 2]) :: VChimera Int
-- >>> take 10 (toList ch)
-- [4,2,4,2,4,2,4,2,4,2]
cycle :: G.Vector v a => v a -> Chimera v a
cycle :: v a -> Chimera v a
cycle v a
vec = case Word
l of
  Word
0 -> [Char] -> Chimera v a
forall a. HasCallStack => [Char] -> a
error [Char]
"Data.Chimera.cycle: empty list"
  Word
_ -> (Word -> a) -> Chimera v a
forall (v :: * -> *) a. Vector v a => (Word -> a) -> Chimera v a
tabulate (v a -> Int -> a
forall (v :: * -> *) a. Vector v a => v a -> Int -> a
G.unsafeIndex v a
vec (Int -> a) -> (Word -> Int) -> Word -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Word -> Int
word2int (Word -> Int) -> (Word -> Word) -> Word -> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Word -> Word -> Word
forall a. Integral a => a -> a -> a
`rem` Word
l))
  where
    l :: Word
l = Int -> Word
int2word (Int -> Word) -> Int -> Word
forall a b. (a -> b) -> a -> b
$ v a -> Int
forall (v :: * -> *) a. Vector v a => v a -> Int
G.length v a
vec

-- | Memoize a function:
-- repeating calls to 'memoize' @f@ @n@
-- would compute @f@ @n@ only once
-- and cache the result in 'VChimera'.
-- This is just a shortcut for 'index' '.' 'tabulate'.
-- When @a@ is 'U.Unbox', it is faster to use
-- 'index' ('tabulate' @f@ :: 'UChimera' @a@).
--
-- prop> memoize f n = f n
memoize :: (Word -> a) -> (Word -> a)
memoize :: (Word -> a) -> Word -> a
memoize = forall a. Vector Vector a => Chimera Vector a -> Word -> a
forall (v :: * -> *) a. Vector v a => Chimera v a -> Word -> a
index @V.Vector (Chimera Vector a -> Word -> a)
-> ((Word -> a) -> Chimera Vector a) -> (Word -> a) -> Word -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Word -> a) -> Chimera Vector a
forall (v :: * -> *) a. Vector v a => (Word -> a) -> Chimera v a
tabulate

-- | For a given @f@ memoize a recursive function 'fix' @f@,
-- caching results in 'VChimera'.
-- This is just a shortcut for 'index' '.' 'tabulateFix'.
-- When @a@ is 'U.Unbox', it is faster to use
-- 'index' ('tabulateFix' @f@ :: 'UChimera' @a@).
--
-- prop> memoizeFix f n = fix f n
--
-- For example, imagine that we want to memoize
-- <https://en.wikipedia.org/wiki/Fibonacci_number Fibonacci numbers>:
--
-- >>> fibo n = if n < 2 then toInteger n else fibo (n - 1) + fibo (n - 2)
--
-- Can we find @fiboF@ such that @fibo@ = 'fix' @fiboF@?
-- Just replace all recursive calls to @fibo@ with @f@:
--
-- >>> fiboF f n = if n < 2 then toInteger n else f (n - 1) + f (n - 2)
--
-- Now we are ready to use 'memoizeFix':
--
-- >>> memoizeFix fiboF 10
-- 55
-- >>> memoizeFix fiboF 100
-- 354224848179261915075
--
-- This function can be used even when arguments
-- of recursive calls are not strictly decreasing,
-- but they might not get memoized. If this is not desired
-- use 'tabulateFix'' instead.
-- For example, here is a routine to measure the length of
-- <https://oeis.org/A006577 Collatz sequence>:
--
-- >>> collatzF f n = if n <= 1 then 0 else 1 + f (if even n then n `quot` 2 else 3 * n + 1)
-- >>> memoizeFix collatzF 27
-- 111
memoizeFix :: ((Word -> a) -> Word -> a) -> (Word -> a)
memoizeFix :: ((Word -> a) -> Word -> a) -> Word -> a
memoizeFix = forall a. Vector Vector a => Chimera Vector a -> Word -> a
forall (v :: * -> *) a. Vector v a => Chimera v a -> Word -> a
index @V.Vector (Chimera Vector a -> Word -> a)
-> (((Word -> a) -> Word -> a) -> Chimera Vector a)
-> ((Word -> a) -> Word -> a)
-> Word
-> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Word -> a) -> Word -> a) -> Chimera Vector a
forall (v :: * -> *) a.
Vector v a =>
((Word -> a) -> Word -> a) -> Chimera v a
tabulateFix

-- | Map subvectors of a stream, using a given length-preserving function.
mapSubvectors
  :: (G.Vector u a, G.Vector v b)
  => (u a -> v b)
  -> Chimera u a
  -> Chimera v b
mapSubvectors :: (u a -> v b) -> Chimera u a -> Chimera v b
mapSubvectors u a -> v b
f (Chimera Vector (u a)
bs) = Vector (v b) -> Chimera v b
forall (v :: * -> *) a. Vector (v a) -> Chimera v a
Chimera ((u a -> v b) -> Vector (u a) -> Vector (v b)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap u a -> v b
f Vector (u a)
bs)

-- | Zip subvectors from two streams, using a given length-preserving function.
zipSubvectors
  :: (G.Vector u a, G.Vector v b, G.Vector w c)
  => (u a -> v b -> w c)
  -> Chimera u a
  -> Chimera v b
  -> Chimera w c
zipSubvectors :: (u a -> v b -> w c) -> Chimera u a -> Chimera v b -> Chimera w c
zipSubvectors u a -> v b -> w c
f (Chimera Vector (u a)
bs1) (Chimera Vector (v b)
bs2) = Vector (w c) -> Chimera w c
forall (v :: * -> *) a. Vector (v a) -> Chimera v a
Chimera ((u a -> v b -> w c) -> Vector (u a) -> Vector (v b) -> Vector (w c)
forall (m :: * -> *) a b c.
MonadZip m =>
(a -> b -> c) -> m a -> m b -> m c
mzipWith u a -> v b -> w c
f Vector (u a)
bs1 Vector (v b)
bs2)