Cats: Foldable.toList potentially inconsistent for Map

[julien-truffaut]

test("toList") {
    import cats.Foldable
    val x = Map(1 -> "abc", 2 -> "cde")
    val y = Map(2 -> "cde", 1 -> "abc")

    x === y should be (true)

    val F = Foldable[Map[Int, ?]]

    F.toList(x) should be (List("abc", "cde"))
    F.toList(y) should be (List("abc", "cde")) // fail, it returns List("cde", "abc")
  }

The problem comes from Map.toList which is used by cats. As far as I know scalaz side step this issue because it requires an Order on Map keys.

You can also see this problem when you use traverse:

test("traverse - toList") {
    import cats.{Foldable, Traverse, Id}
    val x = Map(1 -> "abc", 2 -> "cde")

    val F = Foldable[Map[Int, ?]]
    val T = Traverse[Map[Int, ?]]

    F.toList(T.traverse[Id, String, String](x)(_.reverse)) should be (List("cba", "edc"))  // fail, it returns List("cde", "abc")
  }

[johnynek]

This same issue would show up for Foldable[Set] too, no?

[julien-truffaut]

@johnynek I suppose

[tpolecat]

I don't know how we can possibly get congruence here since you can trivially distinguish values that are ostensibly equal. Universal properties FTL yet again. Do we punt and say yeah that's the risk you take with non-parametric data types, or remove the instances for Map and Set and only provide them for Tree*? Or something else behind door number 3?

I'd like to push past this as it seems to be the only thing holding up the Monocle port.

[adelbertc]

I have a selfish preference for the Order constraint since I have found the Traverse[Map[K, ?]] instance useful several times, and really anything you use as keys in a Map should have an Order.. right?

Though I guess we can put it in alleycats.

[tpolecat]

Are you suggesting we constrain the instance to K: Order and pre-sort the traversal? That's an expensive operation to sweep under the rug … I think I'd prefer to add instances for TreeMap and punt this one to alleycats, although subtyping is going to make the instances ambiguous I think.

:-\

[adelbertc]

Oh I totally forgot about TreeMap. I like that.

[julien-truffaut]

I wonder if it is possible to have a traverse implementation for Map that maintains order, I believe the map implementation does it.

Regarding Monocle, I need to review the traversal law. Maybe it is just too strict.

[julien-truffaut]

I have been thinking a bit more about this and I find it worrying that traverse with a => Id(a) can cause a change in the order. I would think that traverse(a => Id(a)) == id. For example:

test("traverse order") {
    import cats.{Id, Traverse}
    import cats.data.Const
    import newts.FirstOption

    val T = Traverse[Map[Int, ?]]

    val x = Map(1 -> "abc", 2 -> "cde")
    def liftId[A](a: A): Id[A] = a
    def store[A](a: A): Const[FirstOption[A], A] = Const(FirstOption(Some(a)))

    val first = T.traverse[Const[FirstOption[String], ?], String, String](x)(store).getConst.getFirstOption
    val traverseFirst = T.traverse[Const[FirstOption[String], ?], String, String](
      T.traverse(x)(liftId)
    )(store).getConst.getFirstOption

    first should be (traverseFirst) // Some("abc") was not equal to Some("cde")
  }

[tpolecat]

It seems unresolvable to me if we have instances for Map. Equality is bogus because it doesn't consider the information that's needed to compute traversal order.

[tpolecat]

I talked to a friend who helped clarify it for me. The problem is that the relation Eq defines isn't the same thing as equality that we use for substitution, so it's irritating but perfectly legal to have a === b but f(a) =!= f(b). So I think this is not a bug.

[adelbertc]

Makes sense, can't assume f is injective.

[julien-truffaut]

Thanks, @tpolecat I need to read more about this. I always consider Eq as the same equality for substitution.

I believe the problem remain regarding the fusion rule for traverse (from the paper):
traverse (f ⊙ g) = traverse f ⊙ traverse g

However by changing the order in Map, our traverse doesn't respect the fusion law. For example take g: A => Id[A] and f: A => Const[FirstOption[A], A],

[johnynek]

I think we need to formulate the objections here into a PR which adds some laws to Foldable that Map[K, ?] is violating.

I am not sure we want that Eq[A] => (fa =!= fb) | (Foldable.toList(fa) === Foldable.toList(fa)), but maybe we do. If we do, we should argue for that and get it added. It may indeed lead to problems for Map[K, ?] and Set[?].

I think we definitely want: traverse (f ⊙ g) = traverse f ⊙ traverse g and if we aren't testing that explicitly now, we should be. If we are violating that for Map I think we're in real trouble.

[julien-truffaut]

@johnynek We are violating this law for Map. You're right, we should add a test for this law for all Traverse instance

[LukaJCB]

So I've thought about this for some time now including some related issues #1966 and #1927.
There are a few ways I'm seeing to deal with this issue.
For making Foldable#toList consistent:

1. Require an Order[K] for the Foldable instance (This still leaves the problem with Set)
2. Require an Order[K] for the Eq instance.
3. Delete the Foldable instances for unordered collections (and add them in SortedSet and SortedMap)

Both of the first two incur the penalty of having to sort the keys whenever the operation in question is performed. Out of those two, I think folding is more common, so I'd rather reorder on Eq.

Then we have the issue of Traverse associativity. Here we can also envision a couple of solutions:

1. Don't require Traverse to be associative (this is probably the worst solution, IMO)
2. Delete the Traverse instance for Map(but keep it for SortedMap)
3. Require an Order[K] for the Traverse instance and pre-sort upon each traversal (probably not feasible performantly)
4. Add a superclass for Traverse that doesn't require the associative property
5. Add a superclass for Traverse that makes use of the commutative property, so order does not matter at all. (Essentially a traverseUnordered :: CommutativeApplicative f => t a -> (a -> f b) -> f t b, this is also useful for Set as can be seen in #1927)

Out of those I only really like 2 and 5, WDYT?

[LukaJCB]

To clarify number 5 up there would be something like this:

@typeclass trait TraverseUnordered[F[_]] {
  def traverseUnordered[G[_]: CommutativeApplicative, A, B](sa: F[A])(f: A => G[B]): G[F[B]]
}

We could define that for Map and Traverse for SortedMap

[kailuowang]

I vote for deprecating the current Traverse instances for Map and Set. IMO, adding an Order[K] or CommutativeApplicative impose too much performance and/or API limitation for these instances to be generally useful enough to be included in core.
For SortedMap @LukaJCB is adding instances, for SortedSet maybe we can't?

[johnynek]

To me, the highest priority is adding the law to check. We could be violating this elsewhere that we have not noticed.

I think requiring Order[K] to patch Map[K, ?] should be a non-starter. We should just tell users to use SortedMap at that point and not resort on all the operations.

I agree that the Map instance is useful, but i think where it is useful we could fairly easily use SortedMap instead. Usually law violations come back to bite at some point.

As far as how quickly to remove vs. just deprecate I don't know. I'm usually +1 on a slow cycle there so people don't get totally burned trying to do upgrades (I already fear cats 1.0 is going to be painful for large codebases).

On a side note, I wonder if we should bring alley-cats into this repo so it is easier to version together and move lawless, but often useful instances there.

[tpolecat]

There's probably a way to design our way out of this but I don't think it's worth holding up 1.0 (it's been like this forever in scalaz). So for now I would be fine either deprecating these instances or moving them to alleycats immediately (traversing maps isn't super common so I imagine the impact of a package change won't be huge). Also 👍 for bringing alleycats into the repo.

[kailuowang]

agree, alleycats needs more attention, right now it's been left in a dark corner. I submitted an issue to move it into typelevel org and even I totally forgot about it.

[LukaJCB]

We can add Foldable to SortedSet just like Set currently has, but it's still not a valid Functor and therefore not a valid Traverse.

[julien-truffaut]

@tpolecat I wouldn't say traversable for Map is so rare. You can't build a Traversal for Map without it.

[kailuowang]

I propose the following plan

1. move alleycats into cats ( I was against it, but right now it seems the only way to resurrect the project which is very useful) . it will be under a different root package name alleycats.
2. move Traverse instance of Map and Set into the new alleycats module.
3. point users to either use the unlawful one in alleycats or use the traverseUnordered being added by #1927

[johnynek]

I agree 2 and 5 here: https://github.com/typelevel/cats/issues/1831#issuecomment-337221498 sound like the best way forward.

Unordered(Foldable/Traverse) seems tractable and useful for general unordered containers.

[kailuowang]

I also agree that we should add the laws to expose this inconsistency.

[kailuowang]

fixed by #1972