cv-combinators- Functional Combinators for Computer Vision

Portabilitytested on GHC only
MaintainerNoam Lewis <>



Framework for expressing IO actions that require initialization and finalizers. This module provides a *functional* interface for defining and chaining a series of processors.

Motivating example: bindings to C libraries that use functions such as: f(foo *src, foo *dst), where the pointer dst must be pre-allocated. In this case we normally do:

 foo *dst = allocateFoo();
 while (something) {
    f(src, dst);

You can use the runUntil function below to emulate that loop.

Processor is an instance of Category, Functor, Applicative and Arrow.

In addition to the general type Processor m a b, this module also defines the semantic model for Processor IO a b, which has synonym IOProcessor a b.



data Processor m a b whereSource

The type of Processors

  • a, b = the input and output types of the processor (think a -> b)
  • x = type of internal state (existentially quantified)

The arguments to the constructor are:

  1. Processing function: Takes input and internal state, and returns new internal state.
  2. Allocator for internal state (this is run only once): Takes (usually the first) input, and returns initial internal state.
  3. Convertor from state x to output b: Takes internal state and returns the output.
  4. Releaser for internal state (finalizer, run once): Run after processor is done being used, to release the internal state.


Processor :: Monad m => (a -> x -> m x) -> (a -> m x) -> (x -> m b) -> (x -> m ()) -> Processor m a b 


Monad m => Arrow (Processor m)

A few tricks by Saizan from #haskell to perhaps use here: first f = (,) $ (arr fst >>> f) * arr snd arr f = f $ id f *** g = (arr fst >>> f) &&& (arr snd >>> g)

Monad m => Category (Processor m) 
Monad m => Functor (Processor m a) 
Monad m => Applicative (Processor m a) 

type IOProcessor a b = Processor IO a bSource

The semantic model for IOProcessor is a function:

 [[ 'IOProcessor' a b ]] = a -> b

And the following laws:

  1. The processing function (a -> x -> m x) must act as if purely, so that indeed for a given input the output is always the same. One particular thing to be careful with is that the output does not depend on time (for example, you shouldn't use IOProcessor to implement an input device). The IOSource type is defined exactly for time-dependent processors. For pointer typed inputs and outputs, see next law.
  2. For processors that work on pointers, [[ Ptr t ]] = t. This is guaranteed by the following implementation constraints for IOProcessor a b:
  3. If a is a pointer type (a = Ptr p), then the processor must NOT write (modify) the referenced data.
  4. If b is a pointer, the memory it points to (and its allocation status) is only allowed to change by the processor that created it (in the processing and releasing functions). In a way this generalizes the first constraint.

Note, that unlike Yampa, this model does not allow transformations of the type (Time -> a) -> (Time -> b). The reason is that I want to prevent arbitrary time access (whether causal or not). This limitation means that everything is essentially point-wise in time. To allow memory-full operations under this model, scanlT is defined. See for more about arbitrary time access.

type IOSource a b = Processor IO a bSource

IOSource a b is the type of time-dependent processors, such that:

 [[ 'IOSource' a b ]] = (a, Time) -> b

Thus, it is ok to implement a processing action that outputs arbitrary time-dependent values during runtime regardless of input. (Although the more useful case is to calculate something from the input a that is also time-dependent. The a input is often not required and in those cases a = () is used.

Notice that this means that IOSource doesn't qualify as an IOProcessor. However, currently the implementation does NOT enforce this, i.e. IOSource is not a newtype; I don't know how to implement it correctly. Also, one question is whether primitives like chain will have to disallow placing IOSource as the second element in a chain. Maybe they should, maybe they shouldn't.

type IOSink a = IOProcessor a ()Source

TODO: What's the semantic model for IOSink a?

processor :: Monad m => (a -> x -> m x) -> (a -> m x) -> (x -> m b) -> (x -> m ()) -> Processor m a bSource

TODO: do we need this? we're exporting the data constructor anyway for now, so maybe we don't.

chain :: Processor m a b' -> Processor m b' b -> Processor m a bSource

Chains two processors serially, so one feeds the next.

parallel :: Processor m a b -> Processor m c d -> Processor m (a, c) (b, d)Source

A processor that represents two sub-processors in parallel (although the current implementation runs them sequentially, but that may change in the future)

forkJoin :: Processor m a b -> Processor m a b' -> Processor m a (b, b')Source

Constructs a processor that: given two processors, gives source as input to both processors and runs them independently, and after both have have finished, outputs their combined outputs.

Semantic meaning, using Arrow's (&&&) operator: [[ forkJoin ]] = &&& Or, considering the Applicative instance of functions (which are the semantic meanings of a processor): [[ forkJoin ]] = liftA2 (,) Alternative implementation to consider: f &&& g = (,) & f * g

empty :: Monad m => Processor m a aSource

The identity processor: output = input. Semantically, [[ empty ]] = id

split :: Functor f => f a -> f (a, a)Source

Splits (duplicates) the output of a functor, or on this case a processor.

(--<) :: (Functor (cat a), Category cat) => cat a a1 -> cat (a1, a1) c -> cat a cSource

'f --< g' means: split f and feed it into g. Useful for feeding parallelized (***'d) processors. For example, a -- (b *** c) = a >> (b &&& c)

run :: Monad m => Processor m a b -> a -> m bSource

Runs the processor once: allocates, processes, converts to output, and deallocates.

runUntil :: Monad m => Processor m a b -> a -> (b -> m Bool) -> m bSource

Keeps running the processing function in a loop until a predicate on the output is true. Useful for processors whose main function is after the allocation and before deallocation.

runWith :: Monad m => (m b -> m b') -> Processor m a b -> a -> m b'Source

Runs the processor once, but passes the processing + conversion action to the given function.

type Clock m = m DoubleSource

scanlT :: Clock IO -> (b -> b -> DTime -> c -> c) -> c -> IOSource a b -> IOSource a cSource

scanlT provides the primitive for performing memory-full operations on time-dependent processors, as described in


differentiate :: Real b => Clock IO -> IOSource a b -> IOSource a DoubleSource

Differentiate using scanlT. TODO: test, and also generalize for any monad (trivial change of types).

max_ :: Ord b => Clock IO -> b -> IOSource a b -> IOSource a bSource

min_ :: Ord b => Clock IO -> b -> IOSource a b -> IOSource a bSource