Re: [Chicken-users] list vs dotted-list

[Jim Pryor]

On Sun, Nov 14, 2010 at 01:02:36PM -0500, John Cowan wrote:
> > Conceptually, a list is type-homogeneous,
> 
> I don't agree here: see below.
> 
> > If you map some function that accepts either ints or bools as arguments
> > over your list, then the list can be regarded as homogeneously having
> > a union type, int-or-bool.  In statically-typed functional languages,
> > you'd have to express that explicitly, by boxing the elements inside
> > an Either-type.
> 
> That's the fundamental difference between mainstream FPLs and something
> like Typed Racket: an "Either string integer" type is not a supertype of
> "string" or "integer", whereas the Typed Racket equivalent "(U string
> integer)" is.  So there is no need to unbox in Typed Racket: once you know
> what type you have using the STRING? or INTEGER? predicates, you can just
> use the ordinary operations on strings or integers as the case may be.

The type you describe as explicitly available in Typed Racket, and which
is implicit in other Schemes, does differ from the Either type in
Haskell (or the hand-coded analogue in ML) in just the way you say: it's
a supertype, which the type systems of the latter don't make readily
available. So the elements of int-or-bool which are ints can just be
treated as unboxed ints. That's a more sophisticated type possibility,
yes. But still a kind of union type, no?

> Lisp/Scheme can, however, handle more complicated things that even
> Typed Racket can't (AFAIK) express, such as "an alternating list of
> symbols and arbitrary objects", also known as a property list.  This is
> a special case of the truism that statically typed systems can and do
> reject programs (or make them impossible to express) that are entirely
> type-safe, because of the complexity of the types they use.

Yes, good point. I acknowledge that lists-as-type-homogeneous is an
over-simplification for what's really available in Scheme.

I do think it's conceptually helpful to think of lists first in the way
I described, though, and then think of more sophisticated possibilities really
available for Scheme lists afterwards.

-- 
Jim Pryor
address@hidden