pure-borrow
Safe HaskellNone
LanguageGHC2021

Data.Vector.Mutable.Linear.Borrow

Synopsis

Documentation

data Vector a Source #

Linearly owned mutable vector. Contrary to those in linear-base, our Vector owns every element linearly. This is because Pure Borrow can now treat nested mutability safely, so we must allow mutable values to be stored inside Vector. This manifests in the type of set - it returns the old value, which MUST NOT drop in favour of the new value.

Instances

Instances details
LinearOnly (Vector a :: Type) Source # 
Instance details

Defined in Data.Vector.Mutable.Linear.Borrow

Methods

linearOnly :: LinearOnlyWitness (Vector a) Source #

Dupable a => Clone (Vector a) Source # 
Instance details

Defined in Data.Vector.Mutable.Linear.Borrow

Methods

clone :: forall (α :: Lifetime). Share α (Vector a) %1 -> BO α (Vector a) Source #

Unsatisfiable ('ShowType (Vector a) ':<>: 'Text " cannot be copied!") => Copyable (Vector a) Source # 
Instance details

Defined in Data.Vector.Mutable.Linear.Borrow

Methods

copy :: forall (bk :: BorrowKind) (α :: Lifetime). Borrow bk α (Vector a) %1 -> Vector a Source #

empty :: Linearly %1 -> Vector a Source #

constant :: Int -> a -> Linearly %1 -> Vector a Source #

fromList :: [a] %1 -> Linearly %1 -> Vector a Source #

fromVector :: Vector a -> Linearly %1 -> Vector a Source #

Convert a Vector (from vector package) to a Vector.

unsafeFromVector :: Vector a %1 -> Linearly %1 -> Vector a Source #

Unsafely thaws Vector (from vector package) to a Vector, reusing the same memory. This is highly unsafe

fromMutable :: MVector s a %1 -> Linearly %1 -> Vector a Source #

O(n). Clone a MVector from vector package to a Vector.

unsafeFromMutable :: MVector s a %1 -> Linearly %1 -> Vector a Source #

toVector :: Copyable a => Vector a %1 -> Ur (Vector a) Source #

O(1). Freezes Vector a to Vector a from vector package, without copying.

toList :: Copyable a => Vector a %1 -> Ur [a] Source #

size :: forall (bk :: BorrowKind) (α :: Lifetime) a. Borrow bk α (Vector a) %1 -> (Ur Int, Borrow bk α (Vector a)) Source #

get :: forall (α :: Lifetime) (β :: Lifetime) (bk :: BorrowKind) a. (HasCallStack, α >= β) => Int -> Borrow bk α (Vector a) %1 -> BO β (Borrow bk α a) Source #

unsafeGet :: forall (α :: Lifetime) (β :: Lifetime) (bk :: BorrowKind) a. α >= β => Int -> Borrow bk α (Vector a) %1 -> BO β (Borrow bk α a) Source #

get without bounds check.

set :: forall (α :: Lifetime) (β :: Lifetime) a. (HasCallStack, α >= β) => Int -> a %1 -> Mut α (Vector a) %1 -> BO β (a, Mut α (Vector a)) Source #

set i a v sets the i-th element of v to a, and returns the old value alongside. Note that a is bound linearly.

unsafeSet :: forall (α :: Lifetime) (β :: Lifetime) a. α >= β => Int -> a %1 -> Mut α (Vector a) %1 -> BO β (a, Mut α (Vector a)) Source #

set without bound check.

update :: forall (α :: Lifetime) (β :: Lifetime) a b. α >= β => Int -> (a %1 -> BO β (b, a)) %1 -> Mut α (Vector a) %1 -> BO β (b, Mut α (Vector a)) Source #

unsafeUpdate :: forall (α :: Lifetime) (β :: Lifetime) a b. α >= β => Int -> (a %1 -> BO β (b, a)) %1 -> Mut α (Vector a) %1 -> BO β (b, Mut α (Vector a)) Source #

modify :: forall (α :: Lifetime) (β :: Lifetime) a. α >= β => Int -> (a %1 -> a) %1 -> Mut α (Vector a) %1 -> BO β (Mut α (Vector a)) Source #

head :: forall (α :: Lifetime) (β :: Lifetime) (bk :: BorrowKind) a. (HasCallStack, α >= β) => Borrow bk α (Vector a) %1 -> BO β (Borrow bk α a) Source #

unsafeHead :: forall (α :: Lifetime) (β :: Lifetime) (bk :: BorrowKind) a. α >= β => Borrow bk α (Vector a) %1 -> BO β (Borrow bk α a) Source #

last :: forall (α :: Lifetime) (β :: Lifetime) (bk :: BorrowKind) a. (HasCallStack, α >= β) => Borrow bk α (Vector a) %1 -> BO β (Borrow bk α a) Source #

unsafeLast :: forall (α :: Lifetime) (β :: Lifetime) (bk :: BorrowKind) a. α >= β => Borrow bk α (Vector a) %1 -> BO β (Borrow bk α a) Source #

indicesMut :: forall (α :: Lifetime) (β :: Lifetime) a. (HasCallStack, α >= β) => Mut α (Vector a) %1 -> [Int] %1 -> BO β [Mut α a] Source #

unsafeIndicesMut :: forall (α :: Lifetime) (β :: Lifetime) a. α >= β => Mut α (Vector a) %1 -> [Int] %1 -> BO β [Mut α a] Source #

Get multiple elements at the given indices without bounds and duplication check. For more safety, use indicesMut.

splitAt :: forall (bk :: BorrowKind) (α :: Lifetime) a. Int %1 -> Borrow bk α (Vector a) %1 -> (Borrow bk α (Vector a), Borrow bk α (Vector a)) Source #

swap :: forall (α :: Lifetime) (β :: Lifetime) a. (HasCallStack, α >= β) => Mut α (Vector a) %1 -> Int -> Int -> BO β (Mut α (Vector a)) Source #

unsafeSwap :: forall (α :: Lifetime) (β :: Lifetime) a. α >= β => Mut α (Vector a) %1 -> Int -> Int -> BO β (Mut α (Vector a)) Source #

copyAt :: forall a (α :: Lifetime) (β :: Lifetime). (Copyable a, α >= β) => Int -> Share α (Vector a) -> BO β (Ur a) Source #

copyAtMut :: forall a (α :: Lifetime) (β :: Lifetime). (Copyable a, α >= β) => Int -> Mut α (Vector a) %1 -> BO β (Ur a, Mut α (Vector a)) Source #

inplace :: forall (α :: Lifetime) (β :: Lifetime) a. α >= β => (forall s. MVector s a -> ST s ()) %1 -> Mut α (Vector a) %1 -> BO β (Mut α (Vector a)) Source #

Applies an in-place mutation on MVector from vector package.

An example algorithm implementations

qsort Source #

Arguments

:: forall a (α :: Lifetime) (β :: Lifetime). (Ord a, Copyable a, α >= β) 
=> Word

Cost for using parallelism. Halved after each recursive call, and stops parallelizing when it reaches 1.

-> Mut α (Vector a) 
-> BO β () 

A simple parallel implementation of quicksort. It uses a sequential divide-and-conquer when size <8, and parallel divide-and-conquer with parBO otherwise.

This is meant to be a demonstrative implementation and not practical - you need a genuine parallel scheduler to scale this up.

Internal functions

divide :: forall a (α :: Lifetime) (β :: Lifetime). (Ord a, Copyable a, α >= β) => a -> Mut α (Vector a) %1 -> Int -> Int -> BO β (Mut α (Vector a), Mut α (Vector a)) Source #