Blog » Pernicious Myth No. 1: The Container Fiction

Posted on 1234625723|%A: %d %B, %Y|agohover

Newcomers to Haskell quickly learn that lots of containers are involved. Lists and tuples are containers; a monad is like a container; constructed data contain the arguments used in construction, and so forth.

It's a useful fiction, but it is a fiction. A value of type "[a]" does *not* contain values of type 'a', or anything else, for that matter. The Container Fiction is pernicious insofar as it retards progress toward a deeper understanding of how the notation works and why category theory provides such a powerful semantic framework.

All values are ontologically primitive.

This is obvious if you look at "simple" values like integers. Is 3 primitive? Some mathematicians would disagree. The number three, they might argue, is constructed using {} and a successor function. Or they might argue that it's a sequence of lambda expressions of some kind. There are probably lots of other ways to describe the meaning of '3' using various mathematical constructions.

These are all just different ways of *describing* a mathematical object; but as one of my college professors (expert in comparative religion) was fond of saying, map is not territory. Description of an object does not an object make. If these various and sundry descriptions all describe the same thing, then that thing must be independent of the descriptions.

Constructive mathematics does not construct its objects, it describes them. It would be the height of hubris to suggest otherwise; after all, numbers do not depend on the exertions of mathematicians for their continued existence.

The vitality of the Container Fiction demonstrates the power of the Iconic Fallacy. Values do not contain, but syntactic expressions do. We think that an ordered pair (a,b) contains a and b. It doesn't, but the graphical form, using parentheses, strongly implies that containment is involved. This is the Iconic Fallacy: false inference about the nature of the thing signified drawn from the form of the signifier. An expression like [1,2,3] "looks like" a list of integers; it does not therefore follow that it *is* (or denotes) a list of integers. It would be more accurate to say it is a construction that *uses* a list of integers to denote a value. The expression "[1,2,3]" represents application of a morphism (the [] functor) to an argument; if its denoted value contains 1, 2, and 3, then does the denoted value of $\sqrt 4$ contain $4$?

Part of the problem is that "List" (i.e. []) is misnamed, implying that '[a]' *is* a list. It's named after the target end of the arrow; a proper name would be something like "TypToList", thus emphasizing that it is a morphism.

This may seem like so much philosophical splitting of hairs, but it's not. On the contrary, it correlates with one of the fundamental insights of category theory, namely, elements don't matter. I believe it's very important for learners of Haskell (or any FPL with lazy evaluation) not only to learn to think in terms of mathematics, but also to learn to think about how mathematical notation works. I speak from experience; when I first picked up Haskell I used a book that insisted that something like "x = Foo 1 (2,3) 'a'" means that x contains 1, and (2,3), and 'a'. That didn't match up with the ideas I had formed about algebraic data types, so I eventually ended up dropping the whole thing in exasperation.

More specifically: it's important (essential?) to realize that we can only talk about values indirectly. On the one hand that means we have to use a language with syntax, obviously. But it's deeper than that. We can only talk about mathematical objects by "triangulating" using other, related mathematical objects. As a concrete example consider an ordered pair (1,2). Disregarding syntax, lambda expressions, etc., the value (1,2) is a primitive object that is the image of 1, 2 under the mapping ( ). The only way we can talk about it is to use these three things. Not the "contents" of (1,2) - it has no contents - but the things we used to construct (describe) it , which are completely distinct from the thing itself.

The most important reason to learn to think like this is that it is the primary idiom of category theory. For example, in CT terms, something like (1,2) is treated as an opaque object together with two projection arrows fst and snd. No contents involved, just an object and two mappings. The internal structure of the object is irrelevant. Saunders MacLane says somewhere that CT is about "learning to live without elements"; applied to Haskell, that means learning to live without containers.

Like this entry?

## Leave a comment

I see where you are coming from now.

Not the

onlyway, but this is the normal form of ways to talk about it, so to say.What is its argument, then?

I see where you are coming from now. I don't really agree yet, but I do need to study category theory more.

ReplyOptionsThe list

[1,2,3]consists of[](or better, the:data constructor) applied to1and[2,3]. Going further:ReplyOptionsI know this, but since gar says [] (not :) is the morphism and there is just one argument, I thought he had to mean something else.

ReplyOptionsI think the CT way of looking at e.g. "[1,2,3]" is as a mapping from a set to the free monoid generated by the integers, or something like that. It's a little hairy, actually. Pierce has a very concise treatment of how List works. A simpler example would be something like taking an int a to the pair (a,1).

ReplyOptionsI'd venture that the height of hubris is reached when a Platonist tells a Constructivist what he (the Constructivist) thinks.

ReplyOptionsI could not agree more. That's why I restrict my comments to what is (or may be) said.

Whether numbers are Platonic Ideals or something else, I'm satisfied it's a pretty good bet that they're indifferent to our labors.

ReplyOptionsI thought intuitionist at least thought precisely that mathematics is merely mental acts of humans?

No, that's solipsism. ;)_ I gather Intuitionist philosophy does think mathematics is non-linguistic, non-platonic, etc. But that's philosophy, and not even the most ardent intuitionist/constructivist would argue that writing stuff down is anything other than an act of description, not creation. At least I sure hope not.

I think the intuitionist believes the act of creation happens in the mind of the reader. Not really related, but you might enjoy Errett Bishop's "The Crisis in Contemporary Mathematics".

ReplyOptionsThe special syntax for [] and () make this harder to see, if we simply de-sugar to:

Cons 1 $ Cons 2 $ Cons 3 $ Cons 4 Nil

We observe that [] is obviously a morphism from primitive values of type a to a primitive value of type List a. For a list, because it contains the promise of pattern-matching to "get the values back out," it is tempting to think they are simply contained by the list. When we look at other "containers," especially Monoids, this becomes misleading.

ReplyOptionsHi Adam,

Yes, accounting for pattern matching is the tricky part. I'm still mulling this over, but for the moment I look at it like this: the syntax of the construction expression is encoded in a lambda expression in the metalangauge. So even though the expression denotes a primitive value, we have a representation in the metalanguage that "remembers" the constructor syntax. So pattern matching matches against the metalanguage expression, not against the value itself. Something like that, anyway.

-g

ReplyOptionsConceptualizing about How Stuff Works, I envision my program stack as the table of contents entries of the book, and the actual data involved as the print upon the pages.

So the feeling of dismay when some goober puts an odd pagebreak in the document, and throws off the numbering of the table of contents really starts to take on meaning.

Is this dichotomy what you're pointing out?

I may get there after a few more reads, but I'm cutting to the chase with this reply.

ReplyOptionsHowdy,

I'm not sure I understand your metaphor about TOC of a book, but it sounds like you may have something else in mind. What I'm trying to get at is the language we use to think abstractly. In imperative languages that do not support higher-level functions etc. one can get away with purely concrete thinking; the container metaphor works just fine here. (Take functor to mean type/data constructor.) Haskell and its brethren allow one to operate at a much higher level of abstraction, though, so the container metaphor can get in the way, by prejudicing our thinking. Some functors (or rather application of some functors) look like containers, but others don't, so if you get used to thinking "functor expression = container", you may run into trouble. For example, suppose a functor that takes a value of type a to a function value that

usesa, something like foo a :: s -> (a, s). One can certainly think of the values of type "foo a" as containing an a value; but I think for most people it would be a stretch to think of a function as containing anything. But suppose we do; then what about "map"? Map lifts an element function to a function that works on lists of elements - at least that's the most common way to explain it. But that's misleading; foo is not a list or collection of any kind. Lifting a function that works on a to a function that works on the function foo a is quite different from lifting to a list function. Well, it's the same (a lifted function), only different. So it's better to work at a higher level of abstraction: functors just map values/types to values/types, and that's all.Hope it helps,

gregg

ReplyOptionsThat helps.

It takes several readings to climb up the intellectual ladder.

Sort of feel like I'm getting there.

Thanks.

Chris

not those familiar with Scheme… :) They'd think right away in terms of function call frames holding their lexical bindings.

Maybe a container metaphor is not such a bad idea to hold as long as we realize it's just a metaphor (

"denotes containment"— what a great way of putting it!). If some value can be retrieved reliably, repeateably, from an "object", it's only natural to think of that value being contained by it.How the held value is retrived from a curried function

fooa = foo a(that is what it is, right) or from list, is two different things; so the mechanics of how a function is lifted over to them are different too - since it all eventually boils down to how and by what means the access is performed. So,liftL f (a:as) = f a : liftL f as— access on list is patter-matching

liftS f fooa s = (f a, s') where (a,s') = fooa s— access on fooa is by ($ s)

But the meaning is the same. Both versions are just reductions of

(liftM f = m »= (return.f)).So here the container metaphor looks helpful in understanding.

Actually, I stand corrected: from a set-theoretic perspective, a function is exactly a container - a set of ordered pairs, nothing more, nothing less, and lots of people probably think of it that way. I was reminded of this when I went back to look at Z (I think you'd find it very interesting; see the links on my resources page.) So what does that do to my argument, other than demolish it?

Actually I'm not sure it does demolish it. My original motivation was thinking about the ontology of mathematical objects. ZF set theory is just another

representationof mathematical objects. The lambda operator captures what I'm getting at better: given a formula like $x+2$, the corresponding lambda expression $\lambda x.x+2$ denotes the functionassociated withthe formula (Church's words, my emphasis). In other words it just gives us a way to refer to the function (mathematical object) without naming it, but it doesn't say anything about what itis, except that it corresponds to the formula. In Z notation, one could use set comprehension notation to refer to the same object, something like $\{ (x,y) | y = x+2 \}$ (read "the set of all pairs $(x,y)$ satisfying the predicate $y = x+2$".) Ok, a set is about as containerish is it gets, but the point is we cannot privilege that representation by saying a functionisa set of ordered pairs.In any case your post(s) are a good reminder that most programmers are going to be coming from a practical, bottom-up perspective - thinking in terms of machine and language-specific concepts - whereas I'm trying to start with the theoretical, purely mathematical stuff and work my way down to the bits. But the kind of programmers who work with LISP dialects and FP languages are probably going to think in terms of a mix of theoretical and implementational (machine, specific language) ideas, so I think the trick (if one were to try to write e.g. a guide to Haskell from the top-down perspective) is to be very clear about the theory/practice distinction and show how they match up.

Thanks,

gregg

ReplyOptionsOf course you are correct.

However i believe adopting such a radical approach would lead to elitism.

May be, if you come from an algebraic culture, then the container fiction hurts your first contact with Haskell.

But let's face it: if you come from an algebraic culture then certainly Haskell is easier to grasp than if you are say, a Cobol programmer.

In my opinion, up to a certain extent, the tolerant way to speak about Haskell is to avoid difficulties for beginners and syntax-oriented people. Beginners tend to think about programming using objects, containers are familiar to them, containers are objects within objects, that's exactly what they expect to be.

Tell them there is no object, tell them everything is defined behavioristically, tell them morphism is the real thing and you have lost them, perhaps forever. Containers may be a fiction yet there are a fiction with a purpose.

I understand how CT can be deeply enlightening yet i simply don't want functionnal programming becoming an ivory tower only inhabited with people ending every word with -morphism.

ReplyOptions…as long as you say that a container is a thing that denotes containment. Whether or not you describe a phenomenon using nouns, verbs, or relations does not matter: All are mere maps, not the territory itself.

I'm constantly puzzled by professional mathematicians becoming territorial about nomenclature, usually justified by the need to "avoid misunderstanding". "List" is a very good name, it denotes that the constructor

listsits argument. Things of course get harder with nullary functions: They do not have a chance to form a morphism, they only can be subject of one. Is this latter — let's call it "subjective" — view of values what you're driving at?ReplyOptionsFWIW I'm about as far from being a professional mathematician as you can get. I'm just trying to figure out Haskell, and I've been lead astray be lots of tutorials.

"List" is a good name, defined as you defined it: it means the constructor lists its arguments, not that the denoted value is some kind of list.

One would not want to belabor this point too much in a manual or guide, but I think it is worth making in order to bring out the character of functors as structure-preserving things that allow us to manipulate the values of one (unknown) domain using the objects and morphisms of another (known) domain.

ReplyOptions…the internal language of a Cartesian Closed Category shows us that with care it's fine to reason about AxB in terms of elements of A and B even when our category doesn't have elements.

ReplyOptionsCan you first explain what you think a container is? Then we might or might not be able to agree with you.

To me types like [a], Maybe a, etc are containers (but not all monads are containers). But for me a container is something where I can put something in and later get it back out again. I'm sure you have some other more precise definition in mind.

ReplyOptionsHi augustss - see my post on Intergalactic Telefunctors, I think it might answer your question.

ReplyOptionsThe difference between a fiction and a construction is whether you understand and agree with the formalization. For containers, there are worse places to start than Ghani, Abbott and Altenkirch:

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.3.285

ReplyOptionsHi, liked it very much!

If you'll allow my trying to rephrase you in more simple terms (so it is easier for me to understand), it's all about a distinction between an abstract mathematical concept and its concrete implementation inside the machine i.e. run-time system. A distinction between the inside pure world of Haskell compiler, and the outside real world of its run-time system implementation.

We are too imperatively inclined and are used to think in terms of concrete representations. To take your example of a pair, it _can_ actually be represented - inside run-time system world - by a C struct with two fields. Or if we use Scheme, by a tagged cons chain. Or by nothing at all - if it is all "compiled out" into its basic components as e.g. C's global variables.

And this is the main point. What it all means, is that the compiler is allowed to "compile it all out" into the thin air. What it means, is that from the mathematical perspective - from inside the pure Haskell world now - every object is an opaque entity which can only be known to us through its prescribed transactions (re: ADT via functional interfaces). IOW an object is defined by what we can do with it, ask of it, ask from it. By transactions we can get involved with it.

And that has got nothing to do with its concrete representations chosen by the implementation. And so a list - from the pure standpoint - is not a list, but an object which can be asked LENGTH? (!!)? and participate in (:). The list image inside the run-time implementation can be anything that will give us same answers to same questions. Or it can be nothing at all, as long as we get the same answers to same questions we pose using its "name" that holds its "value". As long as there's Repeatability and Predictability exhibited by our program/run-time system/implementation.

ReplyOptionsIOW Haskell decouples abstract definitions from their implementation.

In concrete languages, when we use "struct" we know what's going on internally. In Haskell, we don't.

The compiler is free to choose whatever concrete representation it pleases for a given abstract construct, as long as its behaviour is as prescribed.

ReplyOptionsHi Will,

Thanks, this is a very useful way of putting it. I started out trying to think in purely mathematical terms and not paying any mind to implementation stuff like how things are represented, but obviously at some point one would have to leap the chasm between math and actual languages and compilers. The kind of language you use here is an excellent way to integrate these two worlds.

Thanks,

gregg

ReplyOptions## Post preview:

Close preview