1. 8

  2. 7

    A Set is a Sequence, which means you can call dropFirst on it.

    His problem is that he’s been forced to use shit abstractions, not that abstractions are too abstract.

    In particular, the Apple docs for Sequence make it extremely clear that this protocol is a completely incoherent jumble of only vaguely related properties that don’t follow any sensible or useful laws.

    The OP is right; you shouldn’t be able to drop the “first” element from a type with no ordering semantics. That just means your standard library is bad, not that abstractions are bad.

    Set should expose several protocols/interfaces/typeclasses/whatever, but it’s only worth the trouble if they make sense. In particular, there are sensible and intuitive definitions for Foldable (do a fold over the set in an arbitrary order) and Monoid (union). Depending on your language it might also make sense to make the set have an abstract “map” operation, but probably not. (Unordered containers pose some unique constraints on mapping, since it can change the “shape” of the container.)

    1. 1

      I don’t understand how map wouldn’t work on sets, could you elaborate please?

      1. 2

        Iteration order for an unordered set can be arbitrary, often dependent on hash function output values. You want map(x => x, …) to not change anything. Suppose you have a hash set implementation where each set created has a different tweak for the hash function (to make hash collision DoS infeasible). Now when .map(x => x) creates the new result hash set, the new one will compute different hashes for the same keys, so the iteration order will change. But that’s observable different behavior, even though we wanted map to preserve shape.

        This isn’t insurmountable, but the statement “not all valid implementation strategies for unordered containers readily admit a perfectly well behaved map() method” is true.

        1. 2

          Another more compelling example of this problem is that iteration order for hashsets can depend on the entire history of the hashset object, especially the ordering of key insertions and deletions causing rehashing to happen at specific times. When you call map(x => x), it is probably going to create a new object with a fresh straightforward history (just insertions, in the same order as the source set’s iteration order) so the output set might immediately have a different iteration order, and further (identical, mirrored) operations on the input and output sets might cause their iteration orders to diverge.

          1. 1

            But since iteration order is not technically a property of a set, how can it change? I don’t recall ever seeing anything saying that iteration order should be preserved between two equal sets?

            1. 2

              Well, the sticking point is that map(id) ought to, if it’s perfectly well behaved, return an object that you can’t distinguish from the old one by calling any of its methods.

              You could say “set iteration order is not dependable anywhere, any time”, claiming that iteration order is out of scope, and that’s okay, you can write programs that work using that. It’s still not a perfectly well behaved map().

      2. 3

        The example with the bird-feeder that sets up the article is a case of hierarchical VS prototypical categorization. Humans tend to use the latter for most things but the former is popular with scientists and other highly systemic thinkers.