13ffe9b45ce34af843f67ffc43e47afe77f06ee0
[darcs-mirrors/vector.git] / Data / Vector / Generic / Base.hs
1 {-# LANGUAGE Rank2Types, MultiParamTypeClasses, FlexibleContexts,
2 TypeFamilies, ScopedTypeVariables, BangPatterns #-}
3 {-# OPTIONS_HADDOCK hide #-}
4
5 -- |
6 -- Module : Data.Vector.Generic.Base
7 -- Copyright : (c) Roman Leshchinskiy 2008-2010
8 -- License : BSD-style
9 --
10 -- Maintainer : Roman Leshchinskiy <rl@cse.unsw.edu.au>
11 -- Stability : experimental
12 -- Portability : non-portable
13 --
14 -- Class of pure vectors
15 --
16
17 module Data.Vector.Generic.Base (
18 Vector(..), Mutable
19 ) where
20
21 import Data.Vector.Generic.Mutable ( MVector )
22 import qualified Data.Vector.Generic.Mutable as M
23
24 import Control.Monad.Primitive
25
26 -- | @Mutable v s a@ is the mutable version of the pure vector type @v a@ with
27 -- the state token @s@
28 --
29 type family Mutable (v :: * -> *) :: * -> * -> *
30
31 -- | Class of immutable vectors. Every immutable vector is associated with its
32 -- mutable version through the 'Mutable' type family. Methods of this class
33 -- should not be used directly. Instead, "Data.Vector.Generic" and other
34 -- Data.Vector modules provide safe and fusible wrappers.
35 --
36 -- Minimum complete implementation:
37 --
38 -- * 'unsafeFreeze'
39 --
40 -- * 'basicLength'
41 --
42 -- * 'basicUnsafeSlice'
43 --
44 -- * 'basicUnsafeIndexM'
45 --
46 class MVector (Mutable v) a => Vector v a where
47 -- | /Assume complexity: O(1)/
48 --
49 -- Unsafely convert a mutable vector to its immutable version
50 -- without copying. The mutable vector may not be used after
51 -- this operation.
52 unsafeFreeze :: PrimMonad m => Mutable v (PrimState m) a -> m (v a)
53
54 -- | /Assumed complexity: O(1)/
55 --
56 -- Yield the length of the vector.
57 basicLength :: v a -> Int
58
59 -- | /Assumed complexity: O(1)/
60 --
61 -- Yield a slice of the vector without copying it. No range checks are
62 -- performed.
63 basicUnsafeSlice :: Int -- ^ starting index
64 -> Int -- ^ length
65 -> v a -> v a
66
67 -- | /Assumed complexity: O(1)/
68 --
69 -- Yield the element at the given position in a monad. No range checks are
70 -- performed.
71 --
72 -- The monad allows us to be strict in the vector if we want. Suppose we had
73 --
74 -- > unsafeIndex :: v a -> Int -> a
75 --
76 -- instead. Now, if we wanted to copy a vector, we'd do something like
77 --
78 -- > copy mv v ... = ... unsafeWrite mv i (unsafeIndex v i) ...
79 --
80 -- For lazy vectors, the indexing would not be evaluated which means that we
81 -- would retain a reference to the original vector in each element we write.
82 -- This is not what we want!
83 --
84 -- With 'basicUnsafeIndexM', we can do
85 --
86 -- > copy mv v ... = ... case basicUnsafeIndexM v i of
87 -- > Box x -> unsafeWrite mv i x ...
88 --
89 -- which does not have this problem because indexing (but not the returned
90 -- element!) is evaluated immediately.
91 --
92 basicUnsafeIndexM :: Monad m => v a -> Int -> m a
93
94 -- | /Assumed complexity: O(n)/
95 --
96 -- Copy an immutable vector into a mutable one. The two vectors must have
97 -- the same length but this is not checked.
98 --
99 -- Instances of 'Vector' should redefine this method if they wish to support
100 -- an efficient block copy operation.
101 --
102 -- Default definition: copying basic on 'basicUnsafeIndexM' and
103 -- 'basicUnsafeWrite'.
104 basicUnsafeCopy :: PrimMonad m => Mutable v (PrimState m) a -> v a -> m ()
105
106 {-# INLINE basicUnsafeCopy #-}
107 basicUnsafeCopy !dst !src = do_copy 0
108 where
109 !n = basicLength src
110
111 do_copy i | i < n = do
112 x <- basicUnsafeIndexM src i
113 M.basicUnsafeWrite dst i x
114 do_copy (i+1)
115 | otherwise = return ()
116
117 -- | Evaluate @a@ as far as storing it in a vector would and yield @b@.
118 -- The @v a@ argument only fixes the type and is not touched. The method is
119 -- only used for optimisation purposes. Thus, it is safe for instances of
120 -- 'Vector' to evaluate @a@ less than it would be when stored in a vector
121 -- although this might result in suboptimal code.
122 --
123 -- > elemseq v x y = (singleton x `asTypeOf` v) `seq` y
124 --
125 -- Default defintion: @a@ is not evaluated at all
126 --
127 elemseq :: v a -> a -> b -> b
128
129 {-# INLINE elemseq #-}
130 elemseq _ = \_ x -> x
131
132