Composing Applicative and Alternative

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)

Leave a Reply