On 7 September 2010 14:24, wren ng thornton
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.Miljenovic@gmail.com IvanMiljenovic.wordpress.com