Data.Collate

An Applicative Functor for extracting parts of a stream of values.

Basic usage involves building up a computation from calls to the sample function, then running the computation against a Foldable of inputs. Operationally, this makes one pass over the input in order, extracting each of the values specified by calls to sample, then constructs the result according to the Applicative structure.

Because this is written against ST, we can run Collates purely, or convert them to IO as if by stToIO, and run them with actual I/O interspersed. This means a Collate can be driven by a streaming abstraction such as conduit or pipes.

Finally, although Collate itself doesn't admit any reasonable Monad implementation, it can be used with free to describe multi-pass algorithms over (repeatable) streams. To implement join, we'd potentially need to look over the whole stream of inputs to be able to construct the inner Collate and determine which inputs it needs to inspect. So, we'd need to make multiple passes. If we extended the type to support multiple passes and gave it a Monad instance that implemented (>>=) by making two passes, then the Applicative instance would also be required to make two passes for (<*>), because of the law that (<*>) = ap for any Monad.

Types

newtype Collate c a

Collate c a is a strategy for extracting an a from a sequence of cs in a single streaming pass over the input, even when lookups are specified in arbitrary order.

Operationally, we build up a collection of mutable references, construct a Collator that describes how to fill all of them, construct an action that will read the mutable references and return the ultimate result, iterate over the input sequence to fill the mutable references, and finally run the action to get the result.

Constructors

Collate

Fields

• unCollate :: forall s. ST s (ST s a, Collator (ST s) c)

Instances

Functor (Collate c)

Defined in Data.Collate

Methods

fmap :: (a -> b) -> Collate c a -> Collate c b

(<$) :: a -> Collate c b -> Collate c a

Applicative (Collate c)

Defined in Data.Collate

Methods

pure :: a -> Collate c a

(<*>) :: Collate c (a -> b) -> Collate c a -> Collate c b

liftA2 :: (a -> b -> c0) -> Collate c a -> Collate c b -> Collate c c0

(*>) :: Collate c a -> Collate c b -> Collate c b

(<*) :: Collate c a -> Collate c b -> Collate c a

newtype Collator m c

An collection of "callbacks" for extracting things from a stream of values.

This is generated by Collate, and holds many partially-applied writeSTRefs, so that once they've all been called, some larger value can be extracted.

Constructors

Collator

Fields

• getCollator :: IntMap (c -> ST (PrimState m) ())

Instances

Semigroup (Collator m c)

Collators can be combined by merging the contained maps.

Defined in Data.Collate

Methods

(<>) :: Collator m c -> Collator m c -> Collator m c

sconcat :: NonEmpty (Collator m c) -> Collator m c

stimes :: Integral b => b -> Collator m c -> Collator m c

Monoid (Collator m c)

An empty Collator is just an empty map.

Defined in Data.Collate

Methods

mempty :: Collator m c

mappend :: Collator m c -> Collator m c -> Collator m c

mconcat :: [Collator m c] -> Collator m c

Constructon

sample :: Int -> (c -> a) -> Collate c a

Construct a primitive Collate that strictly extracts the result of a function from the input at the given index.

bulkSample :: Traversable t => t Int -> (c -> a) -> Collate c (t a)

Construct a primitive Collate that strictly extracts the result of a function from many different indices.

Elimination

collate :: Foldable f => Collate c a -> f c -> a

Run a Collate on any Foldable.

collateOf :: (forall s0. Traversing' (->) (Const (Sequenced () (StateT Int (ST s0)))) s c) -> Collate c a -> s -> a

Run a Collate on any Fold.

The type signature looks complicated because we expand Fold to avoid incurring a dependency on lens, but it's effectively just:

collateOf :: Fold s c -> Collate c a -> s -> a

Lower-level elimination APIs

withCollator :: PrimMonad m => Collate c a -> (Collator m c -> m ()) -> m a

Run a Collate by providing an action in any PrimMonad to drive the Collator it generates.

feedCollatorOf :: forall m s c. PrimMonad m => Traversing' (->) (Const (Sequenced () (StateT Int (ST (PrimState m))))) s c -> Int -> Collator m c -> s -> m Int

Drive a Collator with any Fold over the input type it expects.

The Int parameter is the index of the first item in the Fold (so that you can supply the input in multiple chunks).

feedCollatorOf
  :: PrimMonad m
  => Fold s c -> Int -> Collator m c -> s -> m Int

feedCollator :: forall m f c. (PrimMonad m, Foldable f) => Int -> Collator m c -> f c -> m Int

Drive a Collator with any Foldable containing its input type.

See feedCollatorOf.