Warp wrote:
> Orchid XP v7 <voi### [at] devnull> wrote:
>> Notice that a string is a *single-linked* list. (I.e., there are "next" 
>> pointers but no "prev" pointers.)
> 
>   You can't random-access a string in haskell? You can just go through it
> once and that's it? That would be quite limiting...

Not unless you transform it into something else first.

(This "ByteString" thing I keep harping on about gives you something 
like O(n/k) random access time, for some implementation-dependent k.)

Typically, if you read a text string, you're probably going to feed it 
into some kind of parser, and then manipulate the resulting parse tree. 
And parsing only requires linear access.

Post a reply to this message

Warp wrote:
> Orchid XP v7 <voi### [at] devnull> wrote:
>> This is why the "ByteString" library was developed.
> 
>   It just shows that the original article which spawned this thread is
> naive. *In theory* you can have all kinds of fancy high-level uber-abstract
> constructs which abstract away all the dirty internal details. *In practice*,
> however, you still need those dirty details if you want any efficiency.
> The fancy theories may be good in a big bunch of programs, but like so many
> abstractions before, it's not the final silver bullet of programming.

The point being, ByteString is implemented as an array, yet still *looks 
like* a normal linked-list. So you get all the nice fancy theory *and* 
the efficient runtime behaviour, all at once. So I'm not sure it is 
"flawed"...

Post a reply to this message

Warp wrote:
> Orchid XP v7 <voi### [at] devnull> wrote:
>> The nice thing about Haskell is that is *allows* you to come up with a 
>> better implementation and slip it in there later.
> 
>   Is that really so? Can you refactor an existing solution (eg. in a library)
> so that it will be more efficient (eg. memorywise) without breaking any
> existing programs?

It depends on the library, and how carefully it was thought out in the 
first place. (I imagine this applies in most languages.)

For example, there is a current project to introduce 
trippy-new-killer-feature "stream fusion". This involves rewriting 
almost *all* the standard Haskell list processing functions (of which 
there are a fairly mind-blowing number) so that they work completely 
differently internally.

Obviously, these are the most-used functions in all of Haskell [three 
guesses why they're being optimised?], and any change to the interface 
would break practically every Haskell program ever written. And breaking 
almost every Haskell program ever written would be a Very Bad Thing(tm). 
Fortunately, they haven't needed to...

Can the same be said for *every* library? Well, that is a harder 
question to answer. My guess would be "many of them", but I don't have 
any really scientific proof of that.

Post a reply to this message

Warp wrote:
> Orchid XP v7 <voi### [at] devnull> wrote:
>> (My strong suspecion is that it *is* 12 
>> *bytes* - since, after all, a single Unicode code point is 24 bits already.)
> 
>   That depends on whether it's a "raw" unicode value (ie. in practice an
> integer) or eg. an UTF8-encoded unicode character (which would make each
> character of variable size).

My understanding is that single characters are stored as 32-bit 
integers. (Because that's simple, and they fit nicely into CPU 
registers.) I could be mistaken though...

>> The situation is actually worse than it looks. All this lazy evaluation 
>> magic is implemented by storing program state around the place, so an 
>> "unevaluated" string probably takes up more space still...
> 
>   I have always wondered about that. Lazy evaluation can indeed be of
> great help optimizing many things. For example, if you read a file into
> a string and then just read a small part of it, the lazy evaluation will
> automatically skip reading the rest of the file.
> 
>   However, in situations where lazy evaluation does not actually help
> much (or at all), which isn't a very uncommon case, it feels like a
> useless waste of memory.

And time - don't forget time. (Takes time to build a closure, takes time 
to execute it. All of which can be avoided if you know you don't need it.)

For this reason, we have the following facts:

1. There is a special compiler pass for detecting places where laziness 
is *not* necessary, and automatically removing it. (E.g., an inner loop 
where you can *see* that the value is obviously used in the next loop.) 
When you compile a library, the compiler even leaves a note to itself 
telling it how strict each function is with its arguments.

2. There are mechanisms for the programmer to explicitly turn off 
laziness where not required. (Unlike the compiler's automatic detection 
stuff, this operation actually changes the behaviour of the program - 
which is why you, the programmer, must say this is OK.)

Post a reply to this message

Le Forgeron wrote:
> Le 01.11.2007 20:00, Orchid XP v7 nous fit lire :
>> No - it's Unicode. 24 bits per character. ;-)
> 
> Unicode is just a bunch of tables of glyphs (lot of tables, lot of
> glyphs).
> It is past 24 bits since a few...  (even past 32 bits!!!)
> The real thing is how you encode all these.
> UTF-8 is one way (the popular one these days),
> UTF-16 another...  and raw storage the worst idea ever!
> 
> UTF-8 is about 8 bits for ascii range, usually go up to 24 bits (3 x
> 8) for classical japanese, 16 for most french variants...

I was under the impression that these encodings apply to *strings*, not 
individual characters by themselves...

>> But yes, the standard Haskell string type is geared to flexibility, not
>> performance. See my ByteString comments...
> 
> Fixed size unicode... if only they stop adding more tables!

Oh, ByteString (as the name somewhat implies) only supports the first 
256 Unicode code-points. ;-)

Somebody should really fix that eventually...

Post a reply to this message

Warp wrote:

>   UTF-8 encoding "wastes" some bits (in order to use less bits for the
> most used western characters) and requires at most 4 bytes per character
> (even though the characters requiring more than 3 bytes are very rarely
> used).

And thus, like any decent variable-length encoding scheme, it tries to 
assign short codes to common symbols. (Although UTF-8 probably fails 
horribly for, say, Japanese text. I don't actually know...)

>> UTF-16 another...  and raw storage the worst idea ever!
> 
>   Why would raw storage be the worst idea? There are several advantages.
>   The disadvantage is, of course, an increased memory requirement.

You win some, you loose some. Programming is all about these kinds of 
compromises. :-)

Post a reply to this message

Orchid XP v7 <voi### [at] devnull> wrote:
> The point being, ByteString is implemented as an array, yet still *looks 
> like* a normal linked-list. So you get all the nice fancy theory *and* 
> the efficient runtime behaviour, all at once. So I'm not sure it is 
> "flawed"...

  Then why do you need any other type of string?

-- 
                                                          - Warp

Post a reply to this message

>> Yeah, it does take a lot, and it uses unicode for characters too,
>> I think I heard it takes about 12 bytes per character that way.
>> It's perty bad on big files.
>
>  But hey, that's the fad in modern programming: Memory usage and speed
> are irrelevant. Processors are getting faster and memory amounts are
> doubling every couple of years, so who cares if something like a string
> takes 12 times as much memory as it could?

Wasn't that part of  Leo Brodie's point, it's more important that a
solution be adequate, and correct than simple?

Post a reply to this message

Warp wrote:
>   Is that really so? Can you refactor an existing solution (eg. in a library)
> so that it will be more efficient (eg. memorywise) without breaking any
> existing programs?

I don't know about Haskell, but IBM had a language called NIL that was 
very high-level. Everything was processes and SQL-style tables and 
unbounded integers and dynamic code instantiation and such.  They wrote 
the routing software for SNA in it.

When a customer wanted to have two SNA routers sharing the load and 
picking up in the event of a fall-over, the guys on the NIL team 
realized they didn't need to rewrite any NIL code. They simply(*) added 
a flag to the compiler to tell it to generate parallel code with soft 
fail-over. Nothing but the compiler got changed.


(*) For some meaning of "simply" obviously. ;-)

-- 
   Darren New / San Diego, CA, USA (PST)
     Remember the good old days, when we
     used to complain about cryptography
     being export-restricted?

Post a reply to this message

Warp wrote:
> Orchid XP v7 <voi### [at] devnull> wrote:
>> The point being, ByteString is implemented as an array, yet still *looks 
>> like* a normal linked-list. So you get all the nice fancy theory *and* 
>> the efficient runtime behaviour, all at once. So I'm not sure it is 
>> "flawed"...
> 
>   Then why do you need any other type of string?

You probably don't.

It's just that the language standard ("Haskell 98") defines "String" as 
an alias for "[Char]" ("single linked list of characters"). ByteString 
is a 3rd-party library that somebody independently wrote much more 
recently. Adding a new library is quite easy; actually *replacing* 
something existing is much more work.

My hope is that eventually the work that has been done on ByteString 
will be extended to make *all* list processing trippy-fast. There's just 
not much evidence of it happening right now. You know what volunteer 
projects are like...

Post a reply to this message