True Bags Cannot Exist

A philosophical discussion about whether the data structure "bag" can truly exist. (Motivated by complaints that SQL is not "true relational".)

Any physical representation imposes an order on the "objects" involved. A bunch of atomic particles floating in space have an "order" relative to any given source of energy or force. Whether it's theoretically possible for two or more particles to have the same distance or push/pull from a given force or object at a given time, I'm not sure; I'm not a physicist. But the chance of any measurement of the forces being perfectly equal is zero in theory, or at least close enough to zero for our uses such that in practice it's zero. It's not something we can recreate even if it happened such that 99.9999999999999999999999999etc% of the time, it's not a bag. We can round measurements, but that's discarding information about order for our view, not in the absolute sense.

In our computing machinery, we have memory addresses which do not overlap. If we model anything using our usual hardware, the hardware imposes order. We may choose to ignore that order, but again that's just us discarding information about order for our view, not in the absolute sense.

Similarly, the notation "x = bag(7, 4, 33, -2)" provides a list in the absolute sense on paper. It's only a "bag" as a viewpoint when we or some function discards or hides order info.

--top

[It's completely irrelevant how the data structure is represented in memory. If its interface does not provide any way to determine the ordering of elements, the data structure isn't ordered. A bag might be represented using an array (which is ordered), or a hashmap of values-to-quantity-counts (which isn't ordered), or something else esoteric, but if it's a bag it never provides accessors to determine what order elements are stored in. A bag only doesn't exist if it provides access which violates the constraints of the datatype's definition, such as by allowing the order of elements to be accessed. -DavidMcLean?]

Every implementation "provides access" if you have the means to "bust into" it. It's relative to your bust-into-ability. Interfaces are not things, they are a viewpoint. A "bag" is a viewpoint, not an object. Objects are not interfaces, they can only provide interfaces.

[Yes, every implementation provides access if you have the means to "bust into" it. But you don't. You have, for example, a bag object, and it only exposes a bag interface; there's no way to break in and mess with the underlying array. There might not even be an underlying array, and there's no way to know because the interface won't tell you. -DavidMcLean?]

There is always a way to get in. It may not always be practical given ones goal or resources, but that's another issue. You are only pretending like there is no way in. Just because you don't want to bother to peel away the layers of the onion does not mean there is no core.

[No. There isn't always a way to get in. You're wrong. Genuinely-abstract AbstractDataTypes exist, and they're not even hard to implement. By way of example, here's a bag in HaskellLanguage:]

    module Bag ( Bag, fromList, count, insert ) where

    import qualified Data.Map as M

    newtype Bag a = Bag (M.Map a Integer)
    fromList :: Ord a => [a] -> Bag a
    fromList = Bag . M.fromListWith (+) . map (\x -> (x, 1))

    count :: Ord a => a -> Bag a -> Integer
    count x (Bag m) = M.findWithDefault 0 x m

    insert :: Ord a => a -> Bag a -> Bag a
    insert x (Bag m) = Bag $ M.insertWith (+) x 1 m

[The exports from this module, given by the first parenthesised list at the top, do not include any data constructors for the Bag type. This means Bags cannot be constructed "from scratch" using a Data.Map.Map directly, nor destructured through PatternMatching in other modules; the only way to get Bag instances or to get data out of Bag instances is to use the functions (fromList, count, and insert) which are exported. Therefore, there is absolutely no way for a user to access the underlying Data.Map.Map used to implement this bag. It can't happen. Ever. (This is standard practice with datatypes in Haskell. Data.Map itself does almost exactly the same thing as this Bag module; it is of course rather more complicated than my example, since a dictionary data structure is more complicated to implement than a bag.) -DavidMcLean?]