Today I Learned Program and Coprogram

How to design co-programs | Patterns in Functional Programming

On the tail of the last random thought I realized data transformations are reinterpretations of constructors. That turns out to be a very established pattern in program design. Implicit in my thought was that constructors means constructors of the input. Like any established pattern, it has a dual. Enter coprogram, which are reinterpretations of constructors of the output.

The motivating example of zip is quite impressive. zip takes two lists and transform them into one list of pairs, pairing corresponding elements.

zip :: [a] -> [b] -> [(a,b)]

The conventional way of defining zip is case analysis on the input, as shown in the Haskell Prelude.

zip []     _bs    = []
zip _as    []     = []
zip (a:as) (b:bs) = (a,b) : zip as bs

What if we case analyze the output instead? Instead of asking "what is the output when input is empty", what if we ask "what is the input when output is empty"?

zip as bs = 
    if null as || null bs then []
    else (head x, head y) : zip (tail x) (tail y)

This concept adds a very welcome stepping stone between structural recursion and divide-and-conquer.

Comments

[Iven Marquardt]

I would call it codata, which is those in-memory structures which are consumed by a finite number of destructor applications (usually pattern matching in FP). Anyway, nice post.