Data.Traversable.Parts

Sort any traversable. Idea from here, but parameterized over the heap type.

Parts can be thought of as a safe version of unsafePartsOf from lens.

Documentation

data Parts f g a b r where

A queue with a certain number of elements, and a function which extracts exactly that many elements from a larger queue. You can transform the queue (i.e., reversing, etc.) before running the function, effectively transforming the contents of a traversable safely. If the underlying queue is a priority queue, then inserting elements will sort them as you go.

Constructors

Parts :: (forall n. g (m + n) b -> (g n b, r)) -> !(f m a) -> Parts f g a b r

Instances

Functor (Parts f g a b)

Methods

fmap :: (a -> b) -> Parts f g a b a -> Parts f g a b b

(<$) :: a -> Parts f g a b b -> Parts f g a b a

(IndexedQueue f x, MeldableIndexedQueue f x) => Applicative (Parts f g x y)

Methods

pure :: a -> Parts f g x y a

(<*>) :: Parts f g x y (a -> b) -> Parts f g x y a -> Parts f g x y b

(*>) :: Parts f g x y a -> Parts f g x y b -> Parts f g x y b

(<*) :: Parts f g x y a -> Parts f g x y b -> Parts f g x y a

liftParts :: (IndexedQueue g a, IndexedQueue f x) => x -> Parts f g x a a

Lift a value into the running queue.

queueTraversable :: (MeldableIndexedQueue f a, Traversable t) => p f -> t a -> t a

Enqueue every element of a traversable into a queue, and then dequeue them back into the same traversable. This is useful if, for instance, the queue is a priority queue: then this function will perform a sort. If the queue is first-in last-out, this function will perform a reversal.

runParts :: forall a b f. Parts f f b b a -> a

Run the built-up function on the stored queue.

queueTraversal :: (IndexedQueue f b, IndexedQueue f a) => ((a -> Parts f f a b b) -> t -> Parts f f a a t) -> t -> t

Queues a traversal.

runPartsWith :: forall a b c f g. (forall n. f n a -> g n b) -> Parts f g a b c -> c

Perform a length-preserving transformation on the stored queue, and run the built-up function on the transformed version.

transformTraversal :: (IndexedQueue g b, IndexedQueue f a) => (forall n. f n a -> g n b) -> ((a -> Parts f g a b b) -> t -> Parts f g a b t) -> t -> t

Perform an arbitrary length-preserving transformation on a lens-style traversal.

transformTraversable :: (MeldableIndexedQueue f a, IndexedQueue g b, Traversable t) => (forall n. f n a -> g n b) -> t a -> t b

Apply a function which transforms a queue without changing its size to an arbitrary traversable.