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