Copyright | (C) 2015 Edward Kmett |
---|---|

License | BSD-style (see the file LICENSE) |

Maintainer | Edward Kmett <ekmett@gmail.com> |

Stability | experimental |

Portability | non-portable |

Safe Haskell | Trustworthy |

Language | Haskell98 |

Hyperfunctions as an explicit nu form, but using a representable functor to describe the state space of the hyperfunction. This permits memoization but doesn't require it.

If we start with a 'function with state' `(x -> a) -> x -> b`

we can view
it as either `(x -> a, x) -> b`

wich is a `Store x`

Cokleisli morphism or
as `φ :: x -> (x -> a) -> b`

which given `H a b x = (x -> a) -> b`

is a
`(H a b)`

-coalgebra: `(x, φ)`

. Given that we can think of anamorphisms of
this 'function with state' as giving us a fixed point for `H a b`

and the
morphism to the final coalgebra @(Hyper a b, ana φ) is unique (by definition).

A representable functor `f`

is isomorphic to `(->) (`

. `Rep`

f)`((->) x)`

is an obvious selection for such a representable functor, so if we switch
out the functions from `x`

in the above, for a representable functor with
`x`

as its representation we get opportunities for memoization on the
internal 'state space' of our hyperfunctions.

- data Hyper a b where
- Hyper :: Representable g => g (g a -> b) -> Rep g -> Hyper a b

- ana :: (x -> (x -> a) -> b) -> x -> Hyper a b
- cata :: (((y -> a) -> b) -> y) -> Hyper a b -> y
- cata' :: Representable f => ((f a -> b) -> Rep f) -> Hyper a b -> Rep f
- push :: (a -> b) -> Hyper a b -> Hyper a b
- unroll :: Hyper a b -> (Hyper a b -> a) -> b
- roll :: ((Hyper a b -> a) -> b) -> Hyper a b
- invoke :: Hyper a b -> Hyper b a -> b
- uninvoke :: (Hyper b a -> b) -> Hyper a b
- run :: Hyper a a -> a
- project :: Hyper a b -> a -> b
- fold :: [a] -> (a -> b -> c) -> c -> Hyper b c
- build :: (forall b c. (a -> b -> c) -> c -> Hyper b c) -> [a]

# Documentation

Hyper :: Representable g => g (g a -> b) -> Rep g -> Hyper a b |

cata' :: Representable f => ((f a -> b) -> Rep f) -> Hyper a b -> Rep f Source

Memoizing catamorphism