[Haskell-cafe] Properties for Foldable
Is there a collection of laws associated with the Foldable class? Or for Traversable? - Conal ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Properties for Foldable
On Fri, Jul 29, 2011 at 1:15 PM, Conal Elliott co...@conal.net wrote: Is there a collection of laws associated with the Foldable class? Or for Traversable? - Conal Judging by the documentation in the source, I think all the laws are in terms of 'toList'... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Properties for Foldable
On Fri, 29 Jul 2011, Conal Elliott wrote: Is there a collection of laws associated with the Foldable class? Or for Traversable? - Conal Recently I asked the same question: http://www.haskell.org/pipermail/libraries/2011-June/016429.html and got the answer: http://www.cs.ox.ac.uk/jeremy.gibbons/publications/iterator.pdf ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Properties for Foldable
Hi, On Jul 29, 2011, at 10:15 PM, Conal Elliott wrote: Is there a collection of laws associated with the Foldable class? Or for Traversable? - Conal if you are not aware of The essence of the Iterator pattern by Jeremy Gibbons and Bruno Oliveira (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.136.850rep=rep1type=pdf) it might be interesting. Especially chapter 5 discusses some laws of traversable instances. Cheers, Jan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Properties for Foldable
http://www.cs.ox.ac.uk/jeremy.gibbons/publications/iterator.pdf Interesting. However I don't understand why the instance in Section 5.5 is not already forbidden by the purity law traverse pure = pure and a 'no duplication' constraint would be necessary. For example: traverse Id [1,2,3] = Id [1,1,2,2,3,3] /= Id [1,2,3] What am I missing? Can we derive Foldable laws from the Traversable laws? Sebastian ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Properties for Foldable
On Jul 30, 2011, at 12:40 AM, Sebastian Fischer wrote: Interesting. However I don't understand why the instance in Section 5.5 is not already forbidden by the purity law traverse pure = pure and a 'no duplication' constraint would be necessary. For example: traverse Id [1,2,3] = Id [1,1,2,2,3,3] /= Id [1,2,3] What am I missing? I suspect you missed the use of const in the definition of the instance if I am referring to the correct instance. The following instance duplicates elements where duplication of elements is meant in the sense that the instance duplicates the applicative action on an element and not the element itself (at least in the sense of duplication of elements you used above). instance Traversable [] where traverse f [] = pure [] traversef (x:xs) = pure (const (:)) * f x * f x * traverse f xs If f is pure the duplication has no effect but it might have an effect if it is not. Can we derive Foldable laws from the Traversable laws? As foldMap is supposed to be equivalent to foldMapDefault and we have foldMapDefault f = getConst . traverse (Const . f) I think we can derive similar laws. To me, in this case the no duplication constraint seems very desirable for all instances of Traversable as foldMapDefault is probably not supposed to use the function f more often than there are elements in the data structure. Cheers, Jan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Properties for Foldable
What am I missing? I suspect you missed the use of const Doh! I completely overlooked that it's about duplication of *effects*. Thanks, Sebastian ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
