Cleff.Internal.Rec

This module defines an immutable extensible record type, similar to vinyl and data-diverse. However this implementation focuses on fast reads, hence has very different performance characteristics from other libraries:

• Lookup: Amortized \( O(1) \).
• Update: \( O(n) \).
• Shrink: \( O(1) \).
• Append: \( O(n) \).

This is an internal module and its API may change even between minor versions. Therefore you should be extra careful if you're to depend on this module.

Documentation

data Rec (f :: k -> Type) (es :: [k])

Extensible record type supporting efficient \( O(1) \) reads. The underlying implementation is SmallArray slices, therefore suits small numbers of entries (i.e. less than 128).

Constructors

Rec

Fields

• !Int

  The offset.

• !Int

  The length.

• !(SmallArray Any)

  The array content.

type family xs ++ ys where ... infixr 5

Type level list concatenation.

Equations

'[] ++ ys = ys

(x ': xs) ++ ys = x ': (xs ++ ys)

Construction

empty :: Rec f '[]

Create an empty record. \( O(1) \).

cons :: f e -> Rec f es -> Rec f (e ': es)

Prepend one entry to the record. \( O(n) \).

concat :: Rec f es -> Rec f es' -> Rec f (es ++ es')

Concatenate two records. \( O(m+n) \).

Deconstruction

class KnownList (es :: [k])

KnownList es means the list es is concrete, i.e. is of the form '[a1, a2, ..., an] instead of a type variable.

Instances

KnownList ('[] :: [k])

Defined in Cleff.Internal.Rec

Methods

reifyLen :: Int

KnownList es => KnownList (e ': es :: [k])

Defined in Cleff.Internal.Rec

Methods

reifyLen :: Int

head :: Rec f (e ': es) -> f e

Get the head of the record. \( O(1) \).

take :: forall es es' f. KnownList es => Rec f (es ++ es') -> Rec f es

Take elements from the top of the record. \( O(m) \).

tail :: Rec f (e ': es) -> Rec f es

Slice off one entry from the top of the record. \( O(1) \).

drop :: forall es es' f. KnownList es => Rec f (es ++ es') -> Rec f es'

Slice off several entries from the top of the record. \( O(1) \).

Retrieval and updating

class Elem (e :: k) (es :: [k])

The element e is present in the list es.

Instances

(TypeError (ElemNotFound e) :: Constraint) => Elem (e :: k) ('[] :: [k])

Defined in Cleff.Internal.Rec

Methods

reifyIndex :: Int

Elem e es => Elem (e :: a) (e' ': es :: [a])

Defined in Cleff.Internal.Rec

Methods

reifyIndex :: Int

Elem (e :: a) (e ': es :: [a])

The element closer to the head takes priority.

Defined in Cleff.Internal.Rec

Methods

reifyIndex :: Int

class KnownList es => Subset (es :: [k]) (es' :: [k])

es is a subset of es', i.e. all elements of es are in es'.

Instances

Subset ('[] :: [k]) (es :: [k])

Defined in Cleff.Internal.Rec

Methods

reifyIndices :: [Int]

(Subset es es', Elem e es') => Subset (e ': es :: [k]) (es' :: [k])

Defined in Cleff.Internal.Rec

Methods

reifyIndices :: [Int]

index :: forall e es f. Elem e es => Rec f es -> f e

Get an element in the record. Amortized \( O(1) \).

pick :: forall es es' f. Subset es es' => Rec f es' -> Rec f es

Get a subset of the record. Amortized \( O(m) \).

update :: forall e es f. Elem e es => f e -> Rec f es -> Rec f es

Update an entry in the record. \( O(n) \).

Helpers

newArr :: Int -> ST s (SmallMutableArray s Any)

Create a new SmallMutableArray with no contents.