They're not structures the way a C programmer thinks of a struct or a pascal programmer thinks of a record.
That doesn't matter; I'd like to assume that we want to teach students who don't already have a preconceived notion of a Pascal record or C struct.
For CP4E, absolutely. I was just reporting on my experience with existing programmers not unlike Greg's (also with many fewer PhD's)[*].
I have a feeling that introducing optional static typing would help here, because it clarifies the concept.
Very interesting point -- however, I think that we need a better answer in general. The question in my experience stems from a desire to minimize memory load. The students grok lists in about 30 seconds. Then I explain tuples, and they wonder why they were "added" given that lists "exist" (in their brain at that time =). --david [*]: I did teach a course at Bank of America where 15 of the 16 people in the room were Vice Presidents. Of course, they were just programmers, but the pay for a competent programmer is high in the hierarchy of bank salaries. =)