On Tue, Aug 30, 2011 at 4:53 PM, Sebastian Fischer <[email protected]>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
_______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
