content: {-# LANGUAGE NoImplicitPrelude #-}
  
  -- | This module provides destination arrays
  --
  -- == What are destination arrays? What are they good for?
  --
  -- Destination arrays are write-only arrays that are only allocated once,
  -- thereby avoiding your reliance on GHC's fusion mechanisms to remove
  -- unneccessary allocations.
  --
  -- The current status-quo for computations that have a write-only array
  -- threaded along is to rely on fusion. While the optimizations in say,
  -- `Data.Vector` are quite good at ensuring GHC fuses, they aren't
  -- foolproof and can sometimes break by simple refactorings.
  --
  -- Avoiding extra allocations of a write-only array is easy in C, with
  -- something the functional programming world calls destination passing style,
  -- or DPS for short.
  --
  -- Here is a C function that manipulates an array written in DPS style; it
  -- takes in the destiniation array @res@ and writes to it:
  --
  -- @
  -- // ((a + b) * c) for vectors a,b and scalar c
  -- void apbxc(int size, int *a, int *b, int c, int *res){
  --   for (int i=0; i<size;++i){res[i]=a[i]+b[i];}
  --   mult(size, c, res);
  -- }
  --
  -- void mult(int size, int scalar, int* vec){
  --   for (int i=0; i<size; ++i){vec[i] *= scalar;}
  -- }
  -- @
  --
  -- == Example: Stencil computation
  --
  -- One possible use of destination arrays could be the stencil computation
  -- typically called
  -- [jacobi](https://en.wikipedia.org/wiki/Iterative_Stencil_Loops#Example:_2D_Jacobi_iteration).
  -- Here we show one time step of this computation in a single dimension:
  --
  -- @
  -- jacobi1d :: Int -> Vector Double -> Vector Double
  -- jacobi1d n oldA = case stepArr n oldA of
  --   newB -> stepArr n newB
  --
  -- -- @jacobi1d N A[N] B[N] = (new_A[N], new_B[N])@.
  -- stepArr :: Int -> Vector Double -> Vector Double
  -- stepArr n oldArr = alloc n $ \newArr -> fillArr newArr oldArr 1
  --   where
  --     fillArr :: DArray Double %1-> Vector Double -> Int -> ()
  --     fillArr newA oldA ix
  --       | ix == (n-1) = newA &
  --           fill (0.33 * ((oldA ! (ix-1)) + (oldA ! ix) + (oldA ! (ix+1))))
  --       | True = split 1 newA & \(fst, rest) ->
  --           fill (0.33 * ((oldA ! (ix-1)) + (oldA ! ix) + (oldA ! (ix+1)))) fst &
  --             \() -> fillArr rest oldA (ix+1)
  -- @
  --
  -- We can be sure that @stepArr@ only allocates one array. In certain
  -- variations and implementations of the jacobi kernel or similar dense array
  -- computations, ensuring one allocation with @Data.Vector@'s fusion oriented
  -- implementation may not be trivial.
  --
  -- For reference, the C equivalent of this code is the following:
  --
  -- @
  -- static void jacobi_1d_time_step(int n, int *A, int *B){
  --   int t, i;
  --   for (i = 1; i < _PB_N - 1; i++)
  --     B[i] = 0.33333 * (A[i-1] + A[i] + A[i + 1]);
  --   for (i = 1; i < _PB_N - 1; i++)
  --     A[i] = 0.33333 * (B[i-1] + B[i] + B[i + 1]);
  -- }
  -- @
  --
  -- This example is taken from the
  -- [polybench test-suite](https://web.cse.ohio-state.edu/~pouchet.2/software/polybench/)
  -- of dense array codes.
  --
  -- == Aside: Why do we need linear types?
  --
  -- Linear types avoids ambiguous writes to the destination array.
  -- For example, this function could never be linear and hence we avoid
  -- ambiguity:
  --
  -- @
  --  nonLinearUse :: DArray Int -> ()
  --  nonLinearUse arr = case (replicate 3 arr, replicate 4 arr) of
  --    ((),()) -> ()
  -- @
  --
  -- Furthermore, this API is safely implemented by mutating an underlying array
  -- which is good for performance. The API is safe because linear types
  -- enforce the fact that each reference to an underlying mutable array
  -- (and there can be more than one by using @split@) is
  -- linearly threaded through functions and at the end consumed by one of our
  -- write functions.
  --
  -- Lastly, linear types are used to ensure that each cell in the destination
  -- array is written to exactly once. This is because the only way to create and
  -- use a destination array is via
  --
  -- @
  -- alloc :: Int -> (DArray a %1-> ()) %1-> Vector a
  -- @
  --
  -- and the only way to really consume a @DArray@ is via our API
  -- which requires you to completely fill the array.
  module Data.Array.Destination
    ( -- * The Data Type
      DArray,
  
      -- * Create and use a @DArray@
      alloc,
      size,
  
      -- * Ways to write to a @DArray@
      replicate,
      split,
      mirror,
      fromFunction,
      fill,
      dropEmpty,
    )
  where
  
  import Data.Array.Destination.Internal
  