Invisible wrote:
> Lists have another nice property. Haskell is a "lazy" language. If you 
> call a function, the function call isn't really executed until you try 
> to "examine" the result.

That's another thing Python 3.x does now. Lots of new "iteration" features 
(where "iteration" means "for loop" basically), with iterator objects that 
calculate the next element on the fly instead of (for example) taking all 
the keys from a big dictionary and putting them in a list to iterate over. 
One more reason to drop Tcl in favor of Python. :-)

> By contrast, to alter one element of an array, you must copy THE ENTIRE 
> ARRAY. If the array is large, this is obviously absurdly inefficient in 
> both time and space.

You know, there are lots of situations where something *like* an array can 
be made more efficient, and tunable. For example, you can have an array with 
an exception list, where you first look up the index in the exception list, 
and if it isn't there, you look it up in the main body, and copy the main 
body to a new one when the exception list gets too long. IIRC, it's O(1) 
with a much larger constant and a bit of wasted space. Obviously if you're 
going to do something where you change every element of the array, you might 
want a different structure also.

> (I wonder if the C++ STL can do that?)

I think that's why you can have a template plus versions of the code 
specific to particular types. In Ada, you just say "Packed array" instead of 
"array" and it's automatic for whatever size (like, 12-bit FAT records, for 
example).

> First came the Bytestring library. Now Haskell 98 defines a type called 
> "String", but this is really just an alias for a linked list of (32-bit 
> Unicode) characters. That means that the entire list-processing library 
> can be brought to bear on all your string-processing problems. But it's 
> also not especially efficient.

Sounds like what Erlang does. Strings are linked lists of integers 
(converted by the output formatting code). You also have "array of bytes" 
type strings, mostly used for protocol stuff (packing bytes into a protocol) 
but which can be used as strings. Erlang, unfortunately, doesn't really 
support unicode, so the linked-list-of-integers really only works with the 
rest of the system when all the integers are <256.  D'oh!

> The result? Immutable, referentially-transparent arrays with almost the 
> same performance as mutable arrays. (All these clever transformations 
> happen at compile-time, not runtime.)

Yah, Erlang special-cases certain updates that are common idioms (since 
records/structs are basically immutable arrays in Erlang) and folds them up 
in a similar way. Not at the source level, tho. Not as a library, but as a 
compiler wart. :-)

-- 
   Darren New, San Diego CA, USA (PST)
   My fortune cookie said, "You will soon be
   unable to read this, even at arm's length."

Post a reply to this message