[Haskell-cafe] Have you seen this functor/contrafunctor combo?

[Sjoerd Visscher]

On Jun 7, 2012, at 5:21 PM, Conal Elliott wrote:

> Oh, yeah. Thanks, Sjoerd.
> 
> I wonder if there's some way not to require Monad. Some sort of ApplicativeFix instead. Hm.

Something like this:
> instance (Contravariant p, ApplicativeFix f) => Applicative (Q' p f) where
>   pure a = Q' (pure (pure a))
>   Q' fs <*> Q' as = Q' $ \r -> uncurry ($) <$> afix (\ ~(f, a) -> (,) <$> fs (contramap ($ a) r) <*> as (contramap (f $) r))

This works with this ApplicativeFix class:

> class Applicative f => ApplicativeFix f where
>   afix :: (a -> f a) -> f a

At first I thought there would be no instance for this that would not also be a monad. But actually the list instance for MonadFix looks more like an instance for ZipList:

> mfix (\x -> [1:1:zipWith (+) x (tail x), 1:zipWith (+) x x])

gives [[1,1,2,3,5,8…], [1,2,4,8,16,32,64…]], and mfix (\x -> [f x, g x, h x]) = [fix f, fix g, fix h]. For a list monad instance I would expect results with a mixture of f, g and h (but that would not be productive).

Btw, you've asked this before and you got an interesting response:
http://haskell.1045720.n5.nabble.com/recursive-programming-in-applicative-functors-td3171239.html

--
Sjoerd Visscher
https://github.com/sjoerdvisscher/blog