Re: [Haskell-cafe] Pointed, but not Applicative
On Tue, Aug 30, 2011 at 4:53 PM, Sebastian Fischer fisc...@nii.ac.jpwrote: 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 Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Pointed, but not Applicative
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. -- 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.''___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Pointed, but not Applicative
On Wed, 31 Aug 2011, rocon...@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.''___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Pointed, but not Applicative
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. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Pointed, but not Applicative
I suspect this definition is what Sebastian meant by converting back and forth to ordinary lists. 2011/8/29 Ryan Ingram ryani.s...@gmail.com On Sun, Aug 28, 2011 at 8:24 PM, Maciej Marcin Piechotka uzytkown...@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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Pointed, but not Applicative
On Tue, Aug 30, 2011 at 9:42 AM, Conal Elliott co...@conal.net wrote: I suspect this definition is what Sebastian meant by converting back and forth to ordinary lists. Yep, I know; and technically it violates 'fmap id' == 'id' for example, fmap id (FList $ \xs - xs ++ xs) = FList $ \xs - xs If you add this FList law, though, you're OK: runFList fl as = runFList fl [] ++ as But, yes, this definition of fmap converts back to an ordinary list representation. -- ryan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Pointed, but not Applicative
On Wed, Aug 31, 2011 at 6:13 AM, Ryan Ingram ryani.s...@gmail.com 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Pointed, but not Applicative
toFList [] = id toFList (xs++ys) = toFList xs . toFList ys toList id = [] toList (f . g) = toList f ++ toList g These laws do not *define* the isomorphisms because their behavior on singletons is not fixed. Combining them with laws using a 'point' function for functional lists point = (:) the isomorphisms are characterized uniquely: toFList [x] = point x toList (point x) = [x] This might be an argument in favor of a Pointed class without Functor constraint as it shows that other pointed structures have reasonable laws involving 'point' as well. Sebastian ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Pointed, but not Applicative
On Sun, Aug 28, 2011 at 8:24 PM, Maciej Marcin Piechotka uzytkown...@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
Re: [Haskell-cafe] Pointed, but not Applicative
On Mon, 2011-08-29 at 20:24 -0700, Ryan Ingram wrote: On Sun, Aug 28, 2011 at 8:24 PM, Maciej Marcin Piechotka uzytkown...@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 You mean f `fmap` FList g = FList $ \bs - map f (g []) ++ bs Seems to confirm to second law as well. Regards ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Pointed, but not Applicative
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? Sönke [1] http://www.haskell.org/haskellwiki/Typeclassopedia ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Pointed, but not Applicative
-BEGIN PGP SIGNED MESSAGE- Hash: SHA1 On 28/08/11 01:41, 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? Sönke [1] http://www.haskell.org/haskellwiki/Typeclassopedia ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe Pointed f = Pointed (StateT s f) but not Applicative f = Applicative (StateT s f) - -- Tony Morris http://tmorris.net/ -BEGIN PGP SIGNATURE- Version: GnuPG v1.4.10 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iQEcBAEBAgAGBQJOWhtaAAoJEPxHMY3rBz0Pa3oIAMrqoyv4DW39VjIXwzV3/4Ir W5s0+fdoPj7h1j6eyCB81VcDHNtGQmWhZ3+g2AhHo1jLAzmH8G5ACdD1c1FeF2dn a0iO7uvH5sM0xovpsqUwZC8BkomdeAnRuYF5Ohzar5M/Ip2BD0k7QpIWJt3RdLZm uCpwDnsQ2foHJCJYlGmmGkpzDAnkwePOfER93KrKXmzHqQxhS0oACQy6LKfXODTM +d2VVzzb4tWuzijXE4NflpdtW/4jSs3gVFmkZ7BmXSg8XxZO3naO/y4gtrU4YVjw 7TKo4IOIygQVMsFbdV2WZHprMHU/VaM6MTByiNECyB0q/yhJhsXtGsd9eeR2jng= =X4nM -END PGP SIGNATURE- ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Pointed, but not Applicative
On Sun, Aug 28, 2011 at 7:41 AM, Tony Morris tonymor...@gmail.com 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. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Pointed, but not Applicative
On Sun, 2011-08-28 at 11:48 -0300, Felipe Almeida Lessa wrote: On Sun, Aug 28, 2011 at 7:41 AM, Tony Morris tonymor...@gmail.com 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, newtype StateT s m a = StateT (s - m (a, s)) instance Functor m = Functor (StateT s m) where f `fmap` StateT g = StateT $ fmap (first f) . g instance Pointed m = Pointed (StateT s m) where point x = StateT $ point . (,) x Regards signature.asc Description: This is a digitally signed message part ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Pointed, but not Applicative
On Sun, Aug 28, 2011 at 12:41 AM, Sönke Hahn sh...@cs.tu-berlin.de 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Pointed, but not Applicative
On Mon, 2011-08-29 at 12:00 +0900, Sebastian Fischer wrote: On Sun, Aug 28, 2011 at 12:41 AM, Sönke Hahn sh...@cs.tu-berlin.de 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 signature.asc Description: This is a digitally signed message part ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Pointed, but not Applicative
On Mon, Aug 29, 2011 at 12:24 PM, Maciej Marcin Piechotka uzytkown...@gmail.com wrote: instance Functor FList where f `fmap` FList g = ...? Yes, Functor is also one of the classes that can only be implemented by converting to ordinary lists (I think). So FList could only be made an instance of Pointed without (certain) superclass constraints. Sebastian ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
