Extract Foldable trait from Traversable

[Badmoonz]

Some kind of data structures can have constraint on type paramters, like Ord[A] for ordered structures like Set / TreeSet, but they are not Funktors (Covariant) => not Traversable too origin idea

But Foldable by itself provides as lot of useful functionality (majority of current Traversable methods) even foreach_[G[+_]: IdentityBoth: Covariant, A](fa: F[A])(f: A => G[Any]): G[Unit]

suggested trait:

trait Foldable[A] {
   def foldLeft[S, A](fa: F[A])(s: S)(f: (S, A) => S): S   

  /// all other methods implemented using foldLeft
}

[sideeffffect]

What laws apply for Foldable?

[Badmoonz]

probably there are no fundamental laws we just can check that overriden methods are equivalent to default implementations but we cannot provide lawful check that foldLeft iterrates over the structure in the right way

[Badmoonz]

withing Traversable we also can check that Foldable.foldLeft and implementation via foreach are equivalent

example of good traversable and bad foldable :

Traversable[Option] {
  def foreach[G[_], A, B](fa : Option[A])(f : A => G[B]) { fa match {
      case Some(a) => (f(a) *> f(a)).map(Some(_))
      case None => None.pure[G]
   }
 } 
}

if fold is implement via foreach double apply of f(a) make double interations , so all folding operations doubles

[sideeffffect]

That would make me thing that Foldable is not as much an actual Type class, but more like a "shape" (we talked about Shapes here)

[sideeffffect]

Although there are some laws in the Haskell definition

foldr f z t = appEndo (foldMap (Endo . f) t ) z

foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z

fold = foldMap id

length = getSum . foldMap (Sum . const  1)

Although here it says that

Foldable is slightly unusual among Haskell classes which are both principled and general-purpose in that it has no laws of its own. The closest thing is the following property, which strictly speaking is not a law (as it is guaranteed to hold whatever the instance is): given a monoid homomorphism g,

foldMap (g . f) = g . foldMap f

[Badmoonz]

i will insvestigate the "shape" thread

and about the laws from hackage , it's just checks that overriden methods are equivalent to default implementations via foldLeft

[adamgfraser]

Yes, when we were putting the library together we did not include Foldable because it did not have meaningful laws but agree it would be good to think about how to abstract over data types like this.

[Badmoonz]

Yes, when we were putting the library together we did not include Foldable because it did not have meaningful laws but agree it would be good to think about how to abstract over data types like this.

I think that Foldable can have the same laws as Hash: folding Equal objects give Equal results

both laws check that we compute some value over structure in deterministic way

[jdegoes]

I think I'd rather handle this with a "subcategory" Traverse, which could include arbitrary constraints on the types.

[Badmoonz]

I think I'd rather handle this with a "subcategory" Traverse, which could include arbitrary constraints on the types.

Set's are still not covariant even in subcategory; map's can change structure by squashing produced equal values.