[Haskell-cafe] Properties for Foldable

[Jan Christiansen]

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