3 ms·

In Scala a Set is "mappable" because it has a `map` method that goes over its elements and transforms them using the provided function. But it is not a functor,

by dmit 7y ago

In Scala a Set is "mappable" because it has a `map` method that goes over its elements and transforms them using the provided function. But it is not a functor, because its `map` does not obey the functor laws. If you take a Set of integers and pass an `isEven` function to `map` you will get a Set with a different structure (as long as there were originally at least two odd or two even numbers of course). `Mappable` provides short-term comfort due to familiarity, but to do so it sacrifices precision that is essential in the long term.

guerrilla 7y ago
> it sacrifices precision that is essential in the long term. Definitions are precise, not names. Names aren't what makes math work, it's the precise definitions, inference rules and theorems, regardless of the language in which they are written. 'printf' does not work the same in all programming language yet everyone knows what that name means.
TJSomething 7y ago
The very concept of functors was created to describe sets that did exactly that. The functor laws only require that there is an operator that can wrap a value from one category into the functor's target category, that mapping with the identity function is the same as the identity function, and that the results of composition of mapping with two functions is the same as the results of mapping with the composition of the two functions. Set fulfills these laws perfectly. There is no law for maintaining cardinality, because the functor laws don't care if cardinality is a concept that even makes sense for the target category in question.
joshlemer 7y ago
I am also really annoyed by how Set and Map's map methods work in Scala (and have argued about it here: https://contributors.scala-lang.org/t/set-map-deduping-and-possibly-unsafe-behavior/3436 https://contributors.scala-lang.org/t/set-map-deduping-and-p...), I actually don't think that for all the shortcomings of the Set map method, it actually violates any of the Functor laws: 1) For all sets s, s.map(identity) == s ==> true 2) For all sets s, functions f and g, s.map(x => f(g(x)) == s.map(g).map(f) ==> true On the other hand, Map's map method is much more horrible, and does violate the 2nd functor law where f == g == _.swap : Map(1 -> 2, 2 -> 2).map(_.swap).map(_.swap) ==> Map(2 -> 2) Map(1 -> 2, 2 -> 2).map(_.swap.swap) ==> Map(1 -> 2, 2 -> 2) Further, it behaves differently depending on if it is known to be a Map at compile-time, or if it is only known to be an Iterable[(K, V)], due to overloading: Map(1 -> 2, 2 -> 2).map(_.swap) ==> Map(2 -> 2) (Map(1 -> 2, 2 -> 2): Iterable[(Int, Int)]).map(_.swap) ==> List(2 -> 1, 2 -> 2)
- dmit 7y ago
  Ah, you're correct of course, as is TJSomething. While Cats and Scalaz don't provide a Functor instance for Set (and neither does Haskell for Data.Set), it's not for the reason I mentioned.

by dmit 7y ago

guerrilla 7y ago

> it sacrifices precision that is essential in the long term. Definitions are precise, not names. Names aren't what makes math work, it's the precise definitions, inference rules and theorems, regardless of the language in which they are written. 'printf' does not work the same in all programming language yet everyone knows what that name means.

TJSomething 7y ago

The very concept of functors was created to describe sets that did exactly that. The functor laws only require that there is an operator that can wrap a value from one category into the functor's target category, that mapping with the identity function is the same as the identity function, and that the results of composition of mapping with two functions is the same as the results of mapping with the composition of the two functions. Set fulfills these laws perfectly. There is no law for maintaining cardinality, because the functor laws don't care if cardinality is a concept that even makes sense for the target category in question.

joshlemer 7y ago

I am also really annoyed by how Set and Map's map methods work in Scala (and have argued about it here: https://contributors.scala-lang.org/t/set-map-deduping-and-possibly-unsafe-behavior/3436 https://contributors.scala-lang.org/t/set-map-deduping-and-p...), I actually don't think that for all the shortcomings of the Set map method, it actually violates any of the Functor laws: 1) For all sets s, s.map(identity) == s ==> true 2) For all sets s, functions f and g, s.map(x => f(g(x)) == s.map(g).map(f) ==> true On the other hand, Map's map method is much more horrible, and does violate the 2nd functor law where f == g == _.swap : Map(1 -> 2, 2 -> 2).map(_.swap).map(_.swap) ==> Map(2 -> 2) Map(1 -> 2, 2 -> 2).map(_.swap.swap) ==> Map(1 -> 2, 2 -> 2) Further, it behaves differently depending on if it is known to be a Map at compile-time, or if it is only known to be an Iterable[(K, V)], due to overloading: Map(1 -> 2, 2 -> 2).map(_.swap) ==> Map(2 -> 2) (Map(1 -> 2, 2 -> 2): Iterable[(Int, Int)]).map(_.swap) ==> List(2 -> 1, 2 -> 2)

dmit 7y ago
Ah, you're correct of course, as is TJSomething. While Cats and Scalaz don't provide a Functor instance for Set (and neither does Haskell for Data.Set), it's not for the reason I mentioned.