On Sun, Aug 28, 2011 at 7:41 AM, Tony Morris wrote:

Pointed f => Pointed (StateT s f)

but not

Applicative f => Applicative (StateT s f)

But we do have (Functor m, Monad m) => Applicative (StateT s m) so I'm not sure if this is a valid example. Cheers, -- Felipe.

Tony Morris wrote:

Pointed f => Pointed (StateT s f)

but not

Applicative f => Applicative (StateT s f)

I see. So StateT cannot be what you could call an applicative transformer. (Unlike for example ReaderT.) Thanks.

On Mon, 2011-08-29 at 12:00 +0900, Sebastian Fischer wrote:

On Sun, Aug 28, 2011 at 12:41 AM, Sönke Hahn wrote:

...

I was wondering which type could be an instance of Pointed, but not of Applicative. But I can't think of one. Any ideas?

Functional lists:

type FList a = [a] -> [a]

they have a Monoid instance for empty and append, a "point" function for singletons but Applicative or Monad cannot be defined without converting back and forth to ordinary lists.

Sebastian

newtype FList a = FList ([a] -> [a]) instance Functor FList where f `fmap` FList g = ...? The only possible implementation I can think of: f `fmap` FList g = _|_ f `fmap` FList g = map id f `fmap` FList g = map _|_ (+ variation of _|_*) Neither of them holding fmap id = id. Regards

On Sun, Aug 28, 2011 at 8:24 PM, Maciej Marcin Piechotka < uzytkownik2@gmail.com> wrote:

f `fmap` FList g = _|_ f `fmap` FList g = map id f `fmap` FList g = map _|_ (+ variation of _|_*)

f `fmap` FList g = \bs -> map f (g []) ++ bs

I suspect this definition is what Sebastian meant by "converting back and forth to ordinary lists". 2011/8/29 Ryan Ingram

On Sun, Aug 28, 2011 at 8:24 PM, Maciej Marcin Piechotka < uzytkownik2@gmail.com> wrote:

...

f `fmap` FList g = _|_ f `fmap` FList g = map id f `fmap` FList g = map _|_ (+ variation of _|_*)

f `fmap` FList g = \bs -> map f (g []) ++ bs

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

On Wed, Aug 31, 2011 at 6:13 AM, Ryan Ingram wrote:

technically it violates 'fmap id' == 'id' [...]

If you add this FList law, though, you're OK:

runFList fl as = runFList fl [] ++ as

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 These can be defined as: toFList = (++) toList = ($[]) Eliding newtypes, runFList is just the identity function so we need to check f l = toList f ++ l to verify your law. This is the same as f = toFList (toList f) which (once we know that toList and toFList are isomorphisms) does indeed hold because: toFList . toList = id toList . toFList = id Sebastian

On Tue, Aug 30, 2011 at 4:53 PM, Sebastian Fischer 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

On Wed, 31 Aug 2011, roconnor@theorem.ca wrote:

On Sat, 27 Aug 2011, Sönke Hahn wrote:

...

Hi!

I was reading through the Typeclassopedia ([1]) and I was wondering which type could be an instance of Pointed, but not of Applicative. But I can't think of one. Any ideas?

(Identity :+: Store s) is a comonad that is also instance of Pointed, but I do not believe it is an instance Applicative.

newtype SemiStore s a = (Identity :+: Store s) a

instance Pointed (SemiStore s) where pure a = Inl (Identity a)

Coalgebras of the (Identity :+: Store s) comonad form the type of partial lenses so this isn't just an academic functor.

Sorry I left out the newtype wrappers: newtype SemiStore s a = SemiStore ((Identity :+: Store s) a) instance Pointed (SemiStore s) where pure = SemiStore . Inl . Identity -- Russell O'Connor http://r6.ca/ ``All talk about `theft,''' the general counsel of the American Graphophone Company wrote, ``is the merest claptrap, for there exists no property in ideas musical, literary or artistic, except as defined by statute.''