[Haskell-cafe] Pointed, but not Applicative

[Ryan Ingram]

On Tue, Aug 30, 2011 at 4:53 PM, Sebastian Fischer <fischer at nii.ac.jp>wrote:

> I think the idea of functional lists is that the monoids of 'lists'
> and 'functions on lists' are isomorphic with isomorphisms toFList and
> toList:
>
>    toFList [] = id
>    toFList (xs++ys) = toFList xs . toFList ys
>
>    toList id = []
>    toList (f . g) = toList f ++ toList g
>

Oh absolutely, but my point (if you will pardon the pun), was that just
given the type

newtype FList a = FL ([a] -> [a])
runFList (FL f) = f

and the law

runFList fl as = runFList fl [] ++ as

we can prove that

fmap f fl = FL $ \bs -> map f (runFList fl []) ++ bs

is a valid functor instance:

fmap id
(eta expand) = \fl -> fmap id fl
(apply fmap) = \fl -> FL $ \bs -> map id (runFList fl []) ++ bs
(map law) = \fl -> FL $ \bs -> id (runFList fl []) ++ bs
(apply id) = \fl -> FL $ \bs -> runFList fl [] ++ bs
(FList law) = \fl -> FL $ \bs -> runFList fl bs
(eta reduce) = \fl -> FL $ runFList fl
(constructor of destructor) = \fl -> fl
(unapply id) = \fl -> id fl
(eta reduce) = id

We don't need to know that FList is supposed to represent an isomorphism
to/from lists, although you can derive one, as you've shown.  I just wanted
to show that it's a valid functor, but only if you assume an extra law on
the type.  The functor instance depends critically on converting back to a
list which requires that law.

There's no functor instance for this type that doesn't convert back to a
list, which is unfortunate, because you lose the performance benefits of
constant-time append!

  -- ryan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20110901/3a9750d9/attachment.htm>