Archive for July, 2007

Decisive Functors

Sunday, July 8th, 2007 by Conor

It’s another name-choosing exercise that I’m vacillating about, but here’s today’s terminology for the dual to Applicative functors. Remember we had the lax monoidal presentation

> class Functor f => Applicative f where
>    unit :: () -> f ()
>    mult :: (f s, f t) -> f (s, t)

Well, switch from products to coproducts and flip round those arrows and you’ve got

> class Functor f => Decisive f where
>   nogood :: f Zero -> Zero
>   orwell :: f (Either s t) -> Either (f s) (f t)

A Decisive f gives us some sort of certainty with respect to its parameter. If you think of f as some sort of epistemic modality, then it’s quite a useful one. Firstly, if we know/believe/imagine Zero, that must mean the world really is no good, and there really is an element of Zero. Even better, if we know/believe/imagine S or T, that must mean we actually know/believe/imagine S or know/believe/imagine T. ‘Or’ behaves well, and always gives us a decision.

I wonder what we expect to hold. Well, naturally,

> either (fmap g) (fmap h) . orwell = orwell . fmap (either g h)

but surely we’d also like

> orwell . fmap Left = Left
> orwell . fmap Right = Right

> either id orwell . orwell . fmap eassoc
>   = eassoc . either orwell id . orwell


> eassoc :: Either (Either a b) c -> Either a (Either b c)
> either :: (a -> c) -> (b -> c) -> Either a b -> c

but we’d also hope for

> either (magic . nogood) id . orwell = fmap (either magic id)
> either id (magic . nogood) . orwell = fmap (either id magic)

I wonder what else.

There’s an ‘idiomatic’ interface to these things.

> class Functor f => Decisive f where
>   refute :: f Zero -> a
>   branch :: (f s -> a) -> (f t -> a) -> f (Either s t) -> a

Now, guess what. Every comonad is decisive. As it were,

> instance Comonad c => Decisive c where
>   nogood = counit
>   orwell story = case counit story of
>     Left s   -> fmap (either id (const s)) story
>     Right t  -> fmap (either (const t) id) story

That is, orwell revises the story so that, throughout, it’s consistently on whichever side we happen to be on at the (counit) moment.

Nonempty Lists and Padding

Sunday, July 8th, 2007 by Conor

Lists are applicative with a zipping-truncating behaviour, but these guys (written backwards, today)

> data Paddy = First a | Paddy a :<: a

are applicative with a zipping-padding behaviour. Like this

> instance Applicative Paddy where
>   pure x = First x
>   First f     <*> First s     = First (f s)
>   First f     <*> (ss :<: s)  = (First f <*> ss) :<: f s
>   (fs :<: f)  <*> First s     = (fs <*> First s) :<: f s
>   (fs :<: f)  <*> (ss :<: s)  = (fs <*> ss) :<: f s

They're also happily monadic in the nondeterministic sense. Moreover, the join

> join :: Paddy (Paddy x) -> Paddy x
> join (First xs) = xs
> join (xss :<: First x) = join xss :<: x
> join (xss :<: (xs :<: x)) = join (xss :<: xs) :<: x

is structurally recursive (if you know what you're doing) and structurally corecursive, unlike the obvious candidate for join on CoList.

So these guys, as data or codata, get to be monadic hence applicative, but also (and differently) zip-max applicative. The padding behaviour is useful for making rectangular text boxes.

Note that Paddy is not Alternative because, like Ernst Stavro Blofeld, he doesn't tolerate failure.

However, Paddy is also comonadic.

> class Functor c => Comonad c where
>    counit :: c x -> x
>    cobind :: (c s -> t) -> c s -> c t

> instance CoMonad Paddy where
>   counit (First x) = x
>   counit (xs :<: x) = x
>   cobind f ss@(First _) = First (f ss)
>   cobind f ss@(ss' :<: _) = cobind f ss' :<: f ss

That's to say, thinking of these things temporally, each entry in the output to a cobind at a given time is given by the history of the input up to that time. Computations can't do more, but they can be more, by being in context. Again, note productivity means the codata version is also comonadic.

Reminder: lists, colists, etc are not instances of the free/completely iterative monad/comonad construction, as they have node information rather than leaf information, and are additive. Amusing, then, that they are so well behaved.

Composing Applicative and Alternative

Sunday, July 8th, 2007 by Conor

Nicolas asked whether the composition (either way around) of an Applicative functor

> class Applicative f where
>   pure   :: x -> f x
>   (<*>)  :: f (s -> t) -> f s -> f t

and an Alternative functor

> class Applicative g => Alternative g where
>   empty  :: g a
>   (<|>)  :: g a -> g a -> g a

was necessarily Alternative (of course, both f⋅g and g⋅f are Applicative). The answer is yes, both are Alternative. Firstly, g⋅f is Alternative, just by specialising g’s operations. Secondly, f⋅g is Alternative just by the usual idiomatic f-lifting of g’s operations. The applicative functor laws guarantee that the f-effects are combined associatively.

In the hunt for interesting non-monadic examples, we were drawn once again to

> codata CoList a = Nil | a :> (CoList a)

These things are not monadic like lists-with-‘nondeterminism’: the join
is not productive (what should  |join (repeat Nil)| do? These things are not monadic like streams-with-‘diagonal’ (raggedness breaks associativity of joining). But they are Applicative in the ‘minimum-diagonal’ sense

> instance Applicative CoList where
>   pure x = x :> pure x
>   (f :> fs) <*> (s :> ss) = f s :> (fs <*> ss)
>   _ <*> _ = Nil

They are also alternative

> instance Alternative CoList where
>   empty = Nil
>   Nil        <|> ys = ys
>   (x :> xs)  <|> ys = x :> (xs <|> ys)