Comments, formatting and Haddock cleanups. No functional changes.
authorBen Lippmeier <benl@ouroborus.net>
Fri, 29 Apr 2011 09:24:34 +0000 (19:24 +1000)
committerBen Lippmeier <benl@ouroborus.net>
Fri, 29 Apr 2011 09:24:34 +0000 (19:24 +1000)
12 files changed:
dph-base/Data/Array/Parallel/Base.hs
dph-base/Data/Array/Parallel/Base/Debug.hs
dph-base/Data/Array/Parallel/Base/Text.hs
dph-base/Data/Array/Parallel/Base/TracePrim.hs
dph-base/Data/Array/Parallel/Base/Util.hs
dph-prim-interface/interface/DPH_Header.h
dph-prim-interface/interface/DPH_Interface.h
dph-prim-par/Data/Array/Parallel/Unlifted.hs
dph-prim-par/Data/Array/Parallel/Unlifted/Parallel/Segmented.hs
dph-prim-seq/Data/Array/Parallel/Unlifted/Sequential/Segmented.hs
dph-prim-seq/Data/Array/Parallel/Unlifted/Sequential/Segmented/Text.hs
dph-prim-seq/Data/Array/Parallel/Unlifted/Sequential/Segmented/USegd.hs

index 7cfe7a3..73468dc 100644 (file)
@@ -9,15 +9,24 @@
 -- Portability : non-portable (unboxed values and GHC libraries)
 --
 --
--- Interface to the Base modules
+-- Basic functionality, imported by most modules.
 --
 
 module Data.Array.Parallel.Base (
+  -- * Debugging infrastructure
   module Data.Array.Parallel.Base.Debug,
+
+  -- * Data constructor tags
   module Data.Array.Parallel.Base.Util,
+
+  -- * Utils for defining Read\/Show instances.
   module Data.Array.Parallel.Base.Text,
+
+  -- * Tracing infrastructure
   module Data.Array.Parallel.Base.DTrace,
   module Data.Array.Parallel.Base.TracePrim,
+  
+  -- * ST monad re-exported from GHC
   ST(..), runST
 ) where
 
index 5b0643d..3f960d4 100644 (file)
@@ -27,8 +27,11 @@ outOfBounds :: String -> Int -> Int -> a
 outOfBounds loc n i = error $ loc ++ ": Out of bounds (size = "
                               ++ show n ++ "; index = " ++ show i ++ ")"
 
--- Check that the second integer is greater or equal to `0' and less than the
--- first integer
+-- | Bounds check, enabled when `debug` = `True`.
+-- 
+--   The first integer is the length of the array, and the second
+--   is the index. The second must be greater or equal to '0' and less than the
+--   first integer. If the not then `error` with the `String`.
 --
 check :: String -> Int -> Int -> a -> a
 {-# INLINE check #-}
@@ -38,9 +41,14 @@ check loc n i v
 -- FIXME: Interestingly, ghc seems not to be able to optimise this if we test
 --       for `not debug' (it doesn't inline the `not'...)
 
--- Check that the second integer is greater or equal to `0' and less than the
--- first integer; this version is used to check operations that could corrupt
--- the heap
+
+-- | Bounds check, enabled when `debugCritical` = `True`.
+--
+--   This version is used to check operations that could corrupt the heap.
+-- 
+--   The first integer is the length of the array, and the second
+--   is the index. The second must be greater or equal to '0' and less than the
+--   first integer. If the not then `error` with the `String`.
 --
 checkCritical :: String -> Int -> Int -> a -> a
 {-# INLINE checkCritical #-}
@@ -48,8 +56,11 @@ checkCritical loc n i v
   | debugCritical = if (i >= 0 && i < n) then v else outOfBounds loc n i
   | otherwise     = v
 
--- Check that the second integer is greater or equal to `0' and less or equal
--- than the first integer
+
+-- | Length check, enabled when `debug` = `True`.
+-- 
+--   Check that the second integer is greater or equal to `0' and less or equal
+--   than the first integer. If the not then `error` with the `String`.
 --
 checkLen :: String -> Int -> Int -> a -> a
 {-# INLINE checkLen #-}
@@ -57,6 +68,13 @@ checkLen loc n i v
   | debug      = if (i >= 0 && i <= n) then v else outOfBounds loc n i
   | otherwise  = v
 
+
+-- | Equality check, enabled when `debug` = `True`.
+--   
+--   The two `a` values must be equal, else `error`.
+--
+--   The first `String` gives the location of the error, and the second some helpful message.
+--
 checkEq :: (Eq a, Show a) => String -> String -> a -> a -> b -> b
 checkEq loc msg x y v
   | debug     = if x == y then v else err
@@ -66,6 +84,8 @@ checkEq loc msg x y v
                   ++ " (first = " ++ show x
                   ++ "; second = " ++ show y ++ ")"
 
+
+-- | Given an array length, check it is not zero.
 checkNotEmpty :: String -> Int -> a -> a
 checkNotEmpty loc n v
   | debug     = if n /= 0 then v else err
@@ -73,6 +93,12 @@ checkNotEmpty loc n v
   where
     err = error $ loc ++ ": Empty array"
 
+
+-- | Throw an error saying something was not intitialised.
+--   
+--   The `String` must contain a helpful message saying what module the error occured in, 
+--   and the possible reasons for it. If not then a puppy dies at compile time.
+--
 uninitialised :: String -> a
 uninitialised loc = error $ loc ++ ": Touched an uninitialised value"
 
index d705adb..2bf4192 100644 (file)
@@ -13,7 +13,6 @@
 
 module Data.Array.Parallel.Base.Text (
   showsApp, readApp, readsApp,
-
   Read(..)
 ) where
 
index c000136..bf5611d 100644 (file)
@@ -1,9 +1,9 @@
 
--- | When dph-base/Data.Array.Parallel.Config.tracePrimEnabled is True, DPH programs will print
+-- | When `tracePrimEnabled` in "Data.Array.Parallel.Config" is @True@, DPH programs will print
 --   out what array primitives they're using at runtime. See `tracePrim` for details.
 module Data.Array.Parallel.Base.TracePrim
-        ( TracePrim(..)
-        , tracePrim)
+        ( tracePrim
+        , TracePrim(..))
 where
 import Data.Array.Parallel.Base.Config
 import qualified Debug.Trace
@@ -11,9 +11,9 @@ import qualified Debug.Trace
 -- | Print tracing information to console.
 --
 --    This function is used to wrap the calls to DPH primitives defined
---    in dph-prim-par/Data.Array.Parallel.Unlifted
+--    in @dph-prim-par@:"Data.Array.Parallel.Unlifted"
 --
---    Tracing is only enabled when dph-base/Data.Array.Parallel.Config.tracePrimEnabled is True,
+--    Tracing is only enabled when `tracePrimEnabled` in "Data.Array.Parallel.Base.Config"  is `True`,
 --    otherwise it's a no-op.
 --   
 tracePrim :: TracePrim -> a -> a
@@ -23,6 +23,7 @@ tracePrim tr x
  
 
 -- | Records information about the use of a primitive operator.
+--
 --    These are the operator names that the vectoriser introduces.
 --    The actual implementation of each operator varies depending on what DPH backend we're using.
 --    We only trace operators that are at least O(n) in complexity. 
index e17db9b..b72c28c 100644 (file)
@@ -4,23 +4,29 @@ module Data.Array.Parallel.Base.Util (
 
 import Data.Word ( Word8 )
 
+-- | Given a value of an algebraic type, the tag tells us what
+--   data constructor was used to create it.
 type Tag = Int
 
+-- | Get the `Tag` of a `Bool` value. `False` is 0, `True` is 1.
 fromBool :: Bool -> Tag
 fromBool False = 0
 fromBool True  = 1
 {-# INLINE fromBool #-}
 
+-- | Convert a `Tag` to a `Bool` value.
 toBool :: Tag -> Bool
 toBool n | n == 0    = False
          | otherwise = True
 {-# INLINE toBool #-}
 
+-- | Convert a `Tag` to an `Int`. This is identity at the value level.
 tagToInt :: Tag -> Int
-tagToInt = id -- fromEnum
+tagToInt = id
 {-# INLINE tagToInt #-}
 
+-- | Convert an `Int` to a `Tag`. This is identity at the value level.
 intToTag :: Int -> Tag
-intToTag = id -- toEnum
+intToTag = id
 {-# INLINE intToTag #-}
 
index f859895..8385465 100644 (file)
@@ -33,11 +33,12 @@ module Data.Array.Parallel.Unlifted (
   combine, combine2,
   interleave,
 
-  -- * Zips and ZipWith
-  zip,
-  unzip, fsts, snds,
+  -- * Map and ZipWith
   map, zipWith, zipWith3,
-  
+
+  -- * Zipping and Unzipping
+  zip, unzip, fsts, snds,
+    
   -- * Folds
   fold, fold1,
   and, sum, scan,
index c8f93f0..6d55f75 100644 (file)
@@ -14,7 +14,7 @@ infixl 9 !:
 infixr 5 +:+
 
 -- Basics ---------------------------------------------------------------------
--- | Take the number of elements in an array.
+-- | O(1). Take the number of elements in an array.
 length :: Elt a => Array a -> Int
 {-# INLINE_BACKEND length #-}
 
@@ -196,17 +196,19 @@ interleave :: Elt a => Array a -> Array a -> Array a
 {-# INLINE_BACKEND interleave #-}
 
 
--- Zips and ZipWith -----------------------------------------------------------
-map :: (Elt a, Elt b) => (a -> b) -> Array a -> Array b
-{-# INLINE_BACKEND map #-}
-
-
+-- Zipping and Unzipping ------------------------------------------------------
+-- | O(1). Takes two arrays and returns an array of corresponding pairs.
+--         If one array is short, excess elements of the longer array are discarded.
 zip :: (Elt a, Elt b) => Array a -> Array b -> Array (a, b)
 {-# INLINE CONLIKE PHASE_BACKEND zip #-}
 
+
+-- | O(1). Transform an array into an array of the first components,
+--         and an array of the second components.
 unzip :: (Elt a, Elt b) => Array (a, b) -> (Array a, Array b)
 {-# INLINE_BACKEND unzip #-}
 
+
 -- | O(1). Take the first elements of an array of pairs.
 fsts  :: (Elt a, Elt b) => Array (a, b) -> Array a
 {-# INLINE_BACKEND fsts #-}
@@ -217,12 +219,20 @@ snds :: (Elt a, Elt b) => Array (a, b) -> Array b
 {-# INLINE_BACKEND snds #-}
 
 
+-- Maps and zipWith -----------------------------------------------------------
+-- | O(n). Apply a worker function to each element of an array, yielding a new array.
+map     :: (Elt a, Elt b)
+        => (a -> b) -> Array a -> Array b
+{-# INLINE_BACKEND map #-}
+
+
+-- | O(n). zipWith generalises zip by zipping with the function given as the first
+--         argument, instead of a tupling function.
 zipWith :: (Elt a, Elt b, Elt c)
         => (a -> b -> c) -> Array a -> Array b -> Array c
 {-# INLINE_BACKEND zipWith #-}
 
 
--- Higher arity versions of zipWith ---
 zipWith3 :: (Elt a, Elt b, Elt c, Elt d)
           => (a -> b -> c -> d) -> Array a -> Array b -> Array c -> Array d
 {-# INLINE zipWith3 #-}
@@ -321,18 +331,26 @@ zipWith4 f as bs cs ds
 
 
 -- Folds ----------------------------------------------------------------------
+
+-- | Left fold over an array.
 fold :: Elt a => (a -> a -> a) -> a -> Array a -> a
 {-# INLINE_BACKEND fold #-}
 
+-- | Left fold over an array, using the first element to initialise the state.
 fold1 :: Elt a => (a -> a -> a) -> Array a -> a
 {-# INLINE_BACKEND fold1 #-}
 
+
+-- | Compute the conjunction of all elements in a boolean array.
 and :: Array Bool -> Bool
 {-# INLINE_BACKEND and #-}
 
+-- | Compute the sum of an array of numbers.
 sum :: (Num a, Elt a) => Array a -> a
 {-# INLINE_BACKEND sum #-}
 
+-- | Similar to `foldl` but return an array of the intermediate states, including
+--   the final state that is computed by `foldl`.
 scan :: Elt a => (a -> a -> a) -> a -> Array a -> Array a
 {-# INLINE_BACKEND scan #-}
 
index 239ee64..20f8fe1 100644 (file)
@@ -4,13 +4,13 @@
 --   Some of them don't actually have parallel implementations, so we bail out
 --   to the regular sequential ones.
 --
---   This set of combinators is used when the program is comiled with -fdph-par.
---   When compiling with -fdph-seq, the ones in the dph-prim-seq package are used
---   instead. The dph-prim-seq package exports the same names, but all combinators
+--   This set of combinators is used when the program is comiled with @-fdph-par@.
+--   When compiling with @-fdph-seq@, the ones in the @dph-prim-seq@ package are used
+--   instead. The @dph-prim-seq package@ exports the same names, but all combinators
 --   are implemented sequentially.
 --
---   The API is defined in DPH_Header.h and DPH_Interface.h to ensure that both
---   dph-prim-par and dph-prim-seq really do export the same symbols.
+--   The API is defined in @DPH_Header.h@ and @DPH_Interface.h@ to ensure that both
+--   @dph-prim-par@ and @dph-prim-seq@ really do export the same symbols.
 
 #include "DPH_Header.h"
 
index e91e060..45b7636 100644 (file)
@@ -39,11 +39,14 @@ import Data.Vector.Fusion.Stream.Monadic ( Stream(..), Step(..) )
 import Data.Vector.Fusion.Stream.Size    ( Size(..) )
 import Control.Monad.ST ( ST, runST )
 
+
+-- replicate ------------------------------------------------------------------
 replicateSUP :: Unbox a => UPSegd -> Vector a -> Vector a
 {-# INLINE_UP replicateSUP #-}
-replicateSUP segd !xs = joinD theGang balanced
-                      . mapD theGang rep
-                      $ distUPSegd segd
+replicateSUP segd !xs 
+  = joinD theGang balanced
+  . mapD theGang rep
+  $ distUPSegd segd
   where
     rep ((dsegd,di),_)
       = replicateSU dsegd (Seq.slice xs di (lengthUSegd dsegd))
@@ -51,24 +54,45 @@ replicateSUP segd !xs = joinD theGang balanced
 -- FIXME: make this efficient
 replicateRSUP :: Unbox a => Int -> Vector a -> Vector a
 {-# INLINE_UP replicateRSUP #-}
-replicateRSUP n xs = replicateSUP (lengthsToUPSegd (replicateUP (Seq.length xs) n)) xs
+replicateRSUP n xs
+        = replicateSUP (lengthsToUPSegd (replicateUP (Seq.length xs) n)) xs
 
 
-appendSUP :: Unbox a => UPSegd -> UPSegd -> Vector a -> UPSegd -> Vector a -> Vector a
+-- append ---------------------------------------------------------------------
+-- | Segmented append.
+appendSUP
+        :: Unbox a
+        => UPSegd       -- ^ segment descriptor of result array
+        -> UPSegd       -- ^ segment descriptor of first array
+        -> Vector a     -- ^ data of first array
+        -> UPSegd       -- ^ segment descriptor of second array
+        -> Vector a     -- ^ data of first array
+        -> Vector a
+
 {-# INLINE_UP appendSUP #-}
 appendSUP segd !xd !xs !yd !ys
   = joinD theGang balanced
-  . mapD theGang append
+  . mapD  theGang append
   $ distUPSegd segd
-  where
-    append ((segd,seg_off),el_off)
-      = Seq.unstream $ appendSegS (segdUPSegd xd) xs
-                               (segdUPSegd yd) ys
-                               (elementsUSegd segd) seg_off el_off
+  where append ((segd,seg_off),el_off)
+         = Seq.unstream
+         $ appendSegS (segdUPSegd xd) xs
+                      (segdUPSegd yd) ys
+                      (elementsUSegd segd)
+                      seg_off el_off
+
+
+appendSegS
+        :: Unbox a      
+        => USegd        -- ^ segment descriptor of first array
+        -> Vector a     -- ^ data of first array
+        -> USegd        -- ^ segment descriptor of second array
+        -> Vector a     -- ^ data of second array
+        -> Int          -- 
+        -> Int
+        -> Int
+        -> S.Stream a
 
-
-appendSegS :: Unbox a => USegd -> Vector a -> USegd -> Vector a -> Int -> Int -> Int
-                -> S.Stream a
 {-# INLINE_STREAM appendSegS #-}
 appendSegS !xd !xs !yd !ys !n seg_off el_off
   = Stream next state (Exact n)
@@ -79,39 +103,38 @@ appendSegS !xd !xs !yd !ys !n seg_off el_off
     state
       | n == 0 = Nothing
       | el_off < xlens ! seg_off
-          = let i = (indicesUSegd xd ! seg_off) + el_off
-                j = indicesUSegd yd ! seg_off
-                k = (lengthsUSegd xd ! seg_off) - el_off
-            in
-            Just (False, seg_off, i, j, k, n)
-      | otherwise
-          = let -- NOTE: *not* indicesUSegd xd ! (seg_off+1) since seg_off+1
-                -- might be out of bounds
-                i = (indicesUSegd xd ! seg_off) + (lengthsUSegd xd ! seg_off)
-                el_off' = el_off - lengthsUSegd xd ! seg_off
-                j = (indicesUSegd yd ! seg_off) + el_off'
-                k = (lengthsUSegd yd ! seg_off) - el_off'
-            in
-            Just (True, seg_off, i, j, k, n)
+      = let i = (indicesUSegd xd ! seg_off) + el_off
+            j = indicesUSegd yd ! seg_off
+            k = (lengthsUSegd xd ! seg_off) - el_off
+        in  Just (False, seg_off, i, j, k, n)
 
+      | otherwise
+      = let -- NOTE: *not* indicesUSegd xd ! (seg_off+1) since seg_off+1
+            -- might be out of bounds
+            i       = (indicesUSegd xd ! seg_off) + (lengthsUSegd xd ! seg_off)
+            el_off' = el_off - lengthsUSegd xd ! seg_off
+            j       = (indicesUSegd yd ! seg_off) + el_off'
+            k       = (lengthsUSegd yd ! seg_off) - el_off'
+        in  Just (True, seg_off, i, j, k, n)
 
     {-# INLINE next #-}
     next Nothing = return Done
 
     next (Just (False, seg, i, j, k, n))
-      | n == 0 = return Done
-      | k == 0 = return $ Skip (Just (True, seg, i, j, ylens ! seg, n))
+      | n == 0    = return Done
+      | k == 0    = return $ Skip (Just (True, seg, i, j, ylens ! seg, n))
       | otherwise = return $ Yield (xs!i) (Just (False, seg, i+1, j, k-1, n-1))
 
     next (Just (True, seg, i, j, k, n))
-      | n == 0 = return Done
+      | n == 0    = return Done
       | k == 0
-        = let !seg' = seg+1
-          in
-          return $ Skip (Just (False, seg', i, j, xlens ! seg', n))
+      = let !seg' = seg+1
+        in  return $ Skip (Just (False, seg', i, j, xlens ! seg', n))
+
       | otherwise = return $ Yield (ys!j) (Just (True, seg, i, j+1, k-1, n-1))
 
 
+-- fold -----------------------------------------------------------------------
 fixupFold :: Unbox a => (a -> a -> a) -> MVector s a
           -> Dist (Int,Vector a) -> ST s ()
 {-# NOINLINE fixupFold #-}
@@ -185,6 +208,7 @@ foldRUP f z !segSize xs =
     dlen = splitLenD theGang noOfSegs
 
 
+-- indices --------------------------------------------------------------------
 indicesSUP :: UPSegd -> Vector Int
 {-# INLINE_UP indicesSUP #-}
 indicesSUP = joinD theGang balanced
index 1f4cb49..66b9c02 100644 (file)
@@ -9,13 +9,8 @@
 -- Stability   : internal
 -- Portability : portable
 --
--- Description ---------------------------------------------------------------
---
 -- Interface to operations on segmented unlifted arrays.
 --
--- Todo ----------------------------------------------------------------------
---
-
 module Data.Array.Parallel.Unlifted.Sequential.Segmented (
 
   replicateSU, replicateRSU, appendSU, indicesSU, indicesSU',
index dc2d4a7..cdf2c01 100644 (file)
@@ -26,6 +26,3 @@ import Data.Array.Parallel.Unlifted.Sequential.Segmented.USegd (
 instance Show USegd where
   showsPrec k = showsApp k "toUSegd" . lengthsUSegd
 
--- instance Read USegd where
---   readPrec = fmap toUSegd (readApp "toUSegd")
-
index 5a03c12..07215b4 100644 (file)
@@ -2,18 +2,14 @@
 -- |
 -- Module      : Data.Array.Parallel.Unlifted.Sequential.Segmented.USegd
 -- Copyright   : (c) [2001..2002] Manuel M T Chakravarty & Gabriele Keller
---              (c) 2006         Manuel M T Chakravarty & Roman Leshchinskiy
+--             , (c) 2006 Manuel M T Chakravarty & Roman Leshchinskiy
 -- License     : see libraries/ndp/LICENSE
 -- 
 -- Maintainer  : Roman Leshchinskiy <rl@cse.unsw.edu.au>
 -- Stability   : internal
 -- Portability : portable
 --
--- Description ---------------------------------------------------------------
---
--- Segment descriptors.
---
--- Todo ----------------------------------------------------------------------
+-- Segment Descriptors
 --
 
 {-# LANGUAGE CPP #-}
 #include "fusion-phases.h"
 
 module Data.Array.Parallel.Unlifted.Sequential.Segmented.USegd (
-
   -- * Types
   USegd,
 
-  -- * Operations on segment descriptors
-  lengthUSegd, lengthsUSegd, indicesUSegd, elementsUSegd, mkUSegd,
+  -- * Constructors
+  mkUSegd,
   emptyUSegd, singletonUSegd, lengthsToUSegd,
+
+  -- * Projections
+  lengthUSegd, lengthsUSegd, indicesUSegd, elementsUSegd, 
+
+  -- * Operations
   sliceUSegd, extractUSegd
 ) where
 
 import Data.Array.Parallel.Unlifted.Sequential.Vector as V
 
--- | Segment descriptors represent the structure of nested arrays. For each
--- segment, it stores the length and the starting index in the flat data
--- array.
---
-data USegd = USegd { usegd_lengths  :: !(Vector Int)
-                   , usegd_indices  :: !(Vector Int)
-                   , usegd_elements :: !Int
-                   }
+-- | Segment descriptors represent the structure of nested arrays.
+--  For each segment, it stores the length and the starting index in the flat data array.
+--
+--   Example:
+--
+--   @
+--    flat array data:  [1, 2, 3, 4, 5, 6, 7, 8]
+--      (segmentation)   ----  -------  -  ----
+--.
+--      segd  lengths: [2, 3, 1, 2]
+--            indices: [0, 2, 5, 6]
+--           elements: 8 
+--   @
+data USegd 
+        = USegd 
+        { usegd_lengths  :: !(Vector Int)  -- ^ length of each segment
+        , usegd_indices  :: !(Vector Int)  -- ^ starting index of each segment in the flat array
+        , usegd_elements :: !Int           -- ^ total number of elements in the flat array
+        }
+
+
+-- Constructors ---------------------------------------------------------------
+-- | O(1). Construct a new segment descriptor.
+mkUSegd 
+        :: Vector Int   -- ^ length of each segment
+        -> Vector Int   -- ^ starting index of each segment
+        -> Int          -- ^ total number of elements in the flat array
+        -> USegd
+
+{-# INLINE mkUSegd #-}
+mkUSegd = USegd
+
+
+-- | O(1). Yield an empty segment descriptor, with no elements or segments.
+emptyUSegd :: USegd
+{-# INLINE emptyUSegd #-}
+emptyUSegd = USegd V.empty V.empty 0
+
+
+-- | O(1). Yield a singleton segment descriptor.
+--         The single segment covers the given number of elements.
+singletonUSegd :: Int -> USegd
+{-# INLINE singletonUSegd #-}
+singletonUSegd n = USegd (V.singleton n) (V.singleton 0) n
 
--- |Operations on segment descriptors
--- ----------------------------------
 
--- |Yield the overall number of segments
+-- | O(n). Convert a length array into a segment descriptor.
+-- 
+--   The array contains the length of each segment, and we compute the 
+--   indices from that. Runtime is O(n) in the number of segments.
 --
+lengthsToUSegd :: Vector Int -> USegd
+{-# INLINE lengthsToUSegd #-}
+lengthsToUSegd lens
+        = USegd lens (V.scanl (+) 0 lens) (V.sum lens)
+
+
+-- Projections ----------------------------------------------------------------
+-- | O(1). Yield the overall number of segments.
 lengthUSegd :: USegd -> Int
 {-# INLINE lengthUSegd #-}
 lengthUSegd = V.length . usegd_lengths
 
--- |Yield the segment lengths of a segment descriptor
---
+
+-- | O(1). Yield the lengths of the individual segments.
 lengthsUSegd :: USegd -> Vector Int
 {-# INLINE lengthsUSegd #-}
 lengthsUSegd = usegd_lengths
 
--- |Yield the segment indices of a segment descriptor
---
+
+-- | O(1). Yield the segment indices of a segment descriptor.
 indicesUSegd :: USegd -> Vector Int
 {-# INLINE indicesUSegd #-}
 indicesUSegd = usegd_indices
 
--- |Yield the number of data elements
---
+
+-- | O(1). Yield the number of data elements.
 elementsUSegd :: USegd -> Int
 {-# INLINE elementsUSegd #-}
 elementsUSegd = usegd_elements
 
-mkUSegd :: Vector Int -> Vector Int -> Int -> USegd
-{-# INLINE mkUSegd #-}
-mkUSegd = USegd
-
--- |Yield an empty segment descriptor
---
-emptyUSegd :: USegd
-{-# INLINE emptyUSegd #-}
-emptyUSegd = USegd V.empty V.empty 0
 
--- |Yield a singleton segment descriptor
+-- | O(n). Extract a slice of a segment descriptor, avoiding copying where possible.
 --
-singletonUSegd :: Int -> USegd
-{-# INLINE singletonUSegd #-}
-singletonUSegd n = USegd (V.singleton n) (V.singleton 0) n
+--   We can share the segment lengths with the original segment descriptor, 
+--   but still need to recompute the starting indices of each. Hence
+--   runtime is O(n) in the number of segments sliced out.
+-- 
+--   NOTE: In the new segment descriptor, the starting index of the first
+--         segment will be 0.
+sliceUSegd 
+        :: USegd        -- ^ source segment descriptor
+        -> Int          -- ^ index of first segment
+        -> Int          -- ^ number of segments to slice out
+        -> USegd
+        
+{-# INLINE sliceUSegd #-}
+sliceUSegd segd i n
+        = lengthsToUSegd $ V.slice (lengthsUSegd segd) i n
 
--- |Convert a length array into a segment descriptor.
---
-lengthsToUSegd :: Vector Int -> USegd
-{-# INLINE lengthsToUSegd #-}
-lengthsToUSegd lens = USegd lens (V.scanl (+) 0 lens) (V.sum lens)
 
--- |Extract a slice of a segment descriptor, avoiding copying where possible.
+-- | O(n). Extract a slice of a segment descriptor, copying everything.
 --
--- NOTE: In the new segment descriptor, the starting index of the first
---       segment will be 0.
+--   In contrast to `sliceUSegd`, this function copies the array of 
+--   segment lengths as well as recomputing the starting indices of each.
 --
-sliceUSegd :: USegd -> Int -> Int -> USegd
-{-# INLINE sliceUSegd #-}
-sliceUSegd segd i n = lengthsToUSegd $ V.slice (lengthsUSegd segd) i n
+--   NOTE: In the new segment descriptor, the starting index of the first
+--         segment will be 0.
+extractUSegd 
+        :: USegd        -- ^ source segment desciptor
+        -> Int          -- ^ index of the first segment
+        -> Int          -- ^ number of segments to extract out
+        -> USegd
 
--- |Extract a slice of a segment descriptor, copying everything.
---
--- NOTE: In the new segment descriptor, the starting index of the first
---       segment will be 0.
---
-extractUSegd :: USegd -> Int -> Int -> USegd
 {-# INLINE extractUSegd #-}
-extractUSegd segd i n = lengthsToUSegd $ V.extract (lengthsUSegd segd) i n
+extractUSegd segd i n 
+        = lengthsToUSegd $ V.extract (lengthsUSegd segd) i n