On 7 September 2010 14:24, wren ng thornton <w...@freegeek.org> wrote: > On 9/7/10 12:04 AM, Ivan Lazar Miljenovic wrote: >>> >>> Perhaps this just means that union/insert should be part of some other >>> class. >> >> That is part of the plan (I'm tentatively calling the class with the >> "insert" method "Buildable" or "Extendable"); this means that if a >> type is an instance of Monoid (for mempty), Buildable/whatever (for >> insert) and Foldable (for foldr), then we can possibly define a >> build-fusion rule > > You don't need mempty for fusion. All you need is a basis case, and > singleton can give that.
I'm talking about the build-foldr fusion rule from A Shortcut to Deforestation, which (in my admittedly brief search) seems to be the easiest to adapt to a wide range of containers (assuming there is some linearity involved). Yes, for specific types without mempty, we can possibly define specific fusion rules; but I'd like to be able to say "if we're doing a foldr over a build from any sequential type to another sequential type, then we can just fuse the intermediary type". >> (note: I dont' think this will work on Sets, etc. >> unless we have some way of guarantee-ing that the folding function is >> strictly monotonic). > > You should only have to require that mapping functions are injective, and > that folding functions are associative and commutative. Alternatively, that > the folding function is associative, commutative, and idempotent. There's no > need for the target domain to be ordered nor for the folding function to be > monotonic in that order... Well, even given those constraints: it's a bit hard to say "Associative (a -> b), Communtative (a -> b), Idempotent (a -> b) => ... " for a specific function... > >>> Of course, I'd expect singleton to obey the pointed law as well, so >>> that other class would (most likely) be a subclass of pointed functors. >>> In >>> any case, it does mean there's something of a mismatch between singleton >>> vs >>> return/pure/point/unit. >> >> Not quite sure what you mean by a "mis-match" > > Just that they're not the same thing. For example, ZipList supports pure but > it has no meaningful instance of singleton since every ZipList is infinite. Huh; didn't know that ZipList did that. OK, so there's a definite mis-match between what we'd want a "singleton" function to do and what pure appears to do. How can we specify such a hierarchy given that for the majority of containers they will be the same? -- Ivan Lazar Miljenovic ivan.miljeno...@gmail.com IvanMiljenovic.wordpress.com _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe