Copyright	(C) 2015 Edward Kmett
License	BSD-style (see the file LICENSE)
Maintainer	Edward Kmett <[email protected]>
Stability	experimental
Portability	non-portable
Safe Haskell	Trustworthy
Language	Haskell98

Control.Monad.Hyper.Rep

Description

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.

Synopsis

data Hyper a b where
- Hyper :: forall (g :: Type -> Type) a b. 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

data Hyper a b where Source #

Represented Hyperfunctions

arr is a faithful functor, so

arr f ≡ arr g implies f ≡ g

Constructors

Hyper :: forall (g :: Type -> Type) a b. Representable g => g (g a -> b) -> Rep g -> Hyper a b

Instances

Instances details

Arrow Hyper Source #
Instance details Defined in Control.Monad.Hyper.Rep Methods arr :: (b -> c) -> Hyper b c # first :: Hyper b c -> Hyper (b, d) (c, d) # second :: Hyper b c -> Hyper (d, b) (d, c) # (***) :: Hyper b c -> Hyper b' c' -> Hyper (b, b') (c, c') # (&&&) :: Hyper b c -> Hyper b c' -> Hyper b (c, c') #
ArrowLoop Hyper Source #
Instance details Defined in Control.Monad.Hyper.Rep Methods loop :: Hyper (b, d) (c, d) -> Hyper b c #
Costrong Hyper Source #
Instance details Defined in Control.Monad.Hyper.Rep Methods unfirst :: Hyper (a, d) (b, d) -> Hyper a b # unsecond :: Hyper (d, a) (d, b) -> Hyper a b #
Strong Hyper Source #
Instance details Defined in Control.Monad.Hyper.Rep Methods first' :: Hyper a b -> Hyper (a, c) (b, c) # second' :: Hyper a b -> Hyper (c, a) (c, b) #
Profunctor Hyper Source #
Instance details Defined in Control.Monad.Hyper.Rep Methods dimap :: (a -> b) -> (c -> d) -> Hyper b c -> Hyper a d # lmap :: (a -> b) -> Hyper b c -> Hyper a c # rmap :: (b -> c) -> Hyper a b -> Hyper a c # (#.) :: forall a b c q. Coercible c b => q b c -> Hyper a b -> Hyper a c # (.#) :: forall a b c q. Coercible b a => Hyper b c -> q a b -> Hyper a c #
Category Hyper Source #
Instance details Defined in Control.Monad.Hyper.Rep Methods id :: Hyper a a # (.) :: Hyper b c -> Hyper a b -> Hyper a c #
Applicative (Hyper a) Source #
Instance details Defined in Control.Monad.Hyper.Rep Methods pure :: a0 -> Hyper a a0 # (<>) :: Hyper a (a0 -> b) -> Hyper a a0 -> Hyper a b # liftA2 :: (a0 -> b -> c) -> Hyper a a0 -> Hyper a b -> Hyper a c # (>) :: Hyper a a0 -> Hyper a b -> Hyper a b # (<*) :: Hyper a a0 -> Hyper a b -> Hyper a a0 #
Functor (Hyper a) Source #
Instance details Defined in Control.Monad.Hyper.Rep Methods fmap :: (a0 -> b) -> Hyper a a0 -> Hyper a b # (<$) :: a0 -> Hyper a b -> Hyper a a0 #
Monad (Hyper a) Source #
Instance details Defined in Control.Monad.Hyper.Rep Methods (>>=) :: Hyper a a0 -> (a0 -> Hyper a b) -> Hyper a b # (>>) :: Hyper a a0 -> Hyper a b -> Hyper a b # return :: a0 -> Hyper a a0 #
MonadZip (Hyper a) Source #
Instance details Defined in Control.Monad.Hyper.Rep Methods mzip :: Hyper a a0 -> Hyper a b -> Hyper a (a0, b) # mzipWith :: (a0 -> b -> c) -> Hyper a a0 -> Hyper a b -> Hyper a c # munzip :: Hyper a (a0, b) -> (Hyper a a0, Hyper a b) #

ana :: (x -> (x -> a) -> b) -> x -> Hyper a b Source #

cata :: (((y -> a) -> b) -> y) -> Hyper a b -> y Source #

cata phi (push f h) ≡ phi $ \g -> f $ g (cata phi h)

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

Memoizing catamorphism

push :: (a -> b) -> Hyper a b -> Hyper a b Source #

arr f ≡ push f (arr f)
invoke (push f q) k ≡ f (invoke k q)
push f p . push g q ≡ push (f . g) (p . q)

unroll :: Hyper a b -> (Hyper a b -> a) -> b Source #

Unroll a hyperfunction

roll :: ((Hyper a b -> a) -> b) -> Hyper a b Source #

Re-roll a hyperfunction using Lambek's lemma.

invoke :: Hyper a b -> Hyper b a -> b Source #

uninvoke :: (Hyper b a -> b) -> Hyper a b Source #

run :: Hyper a a -> a Source #

run f ≡ invoke f id
run (arr f) ≡ fix f
run (push f q) ≡ f (run q)
run (push f p . q) ≡ f (run (q . p)) = f (invoke q p)

project :: Hyper a b -> a -> b Source #

project . arr ≡ id
project h a ≡ invoke h (pure a)
project (push f q) ≡ f

fold :: [a] -> (a -> b -> c) -> c -> Hyper b c Source #

Under "nice" conditions

fold . build ≡ id

build :: (forall b c. (a -> b -> c) -> c -> Hyper b c) -> [a] Source #