Hacker News Reader

Comment by auggierose | Hacker News Reader

Interesting that they put Strings under fixed size data, and then start the arbitrarily large data section with Lists ...

View on HN

Images are also considered "fixed size data" in the textbook. I think this is for pedagogical reasons, the sort of simplifying-lie-that-is-cleared-up-later that is common in science education. In the first section, students are encouraged to think of strings and images as atomic data to be processed all at once using built-in functions, but in the "arbitrarily large data" section, the authors give you tools for converting images and strings to lists (of characters and pixel values).

(Note: since Racket supports exact bignums, in a sense numbers are not atomic either! Only Booleans ;-)

Strings are usually represented as arrays (Haskell represents them as linked lists; it's the only exception I can think of offhand), which are a fixed length. To append to an array, you need to allocate a larger one and copy everything over. You can avoid that copying for a lot of appends by allocating more space than you need and using a fill pointer, and the realloc might be hidden away in a method, but it is still fundamentally a fixed-length data structure.

Linked lists are not a fixed lenth. To add an element to a linked list, you allocate a new cons, point its car to the new element, and point its cdr to the old list. There is no "and then allocate a new, larger fixed-length list, copy everything over, and delete the old one" step.

That's all language-agnostic, but in Scheme specifically, the interface it provides for strings does not simulate arbitrary length, either. The only way to add onto strings is using string-append, which returns a newly allocated string.

In a functional language (like Scheme) strings are immutable, so they are fixed size.

> In a functional language (like Scheme) strings are immutable, so they are fixed size.

Strings are mutable in standard Scheme (unlike, say, Java):

    #;1> (let ((string (string-copy "foo")))
           (string-set! string 0 #\b)
           string)
    "boo"

They're still a fixed length (as they are in virtually every language) because the only way to add onto them is to allocate a new string and copy everything over (this might be hidden behind a method, and you can avoid actually doing this every time by initially allocating more space than you need and using a fill pointer, but they're still fundamentally a fixed length). For example, the 4th edition of the Scheme Programming Language[0] gives this example definition of string-append:

    (define string-append
      (lambda args
        (let f ([ls args] [n 0])
          (if (null? ls)
              (make-string n)
              (let* ([s1 (car ls)]
                     [m (string-length s1)]
                     [s2 (f (cdr ls) (+ n m))])
                (do ([i 0 (+ i 1)] [j n (+ j 1)])
                    ((= i m) s2)
                  (string-set! s2 j (string-ref s1 i))))))))

Even in a language that helpfully assigned the result of this function to the first argument under the covers, this is more or less what you fundamentally have to do, as long as strings are represented by arrays (in Haskell, strings are linked lists, so this doesn't apply).

0: http://www.scheme.com/tspl4/objects.html#./objects:h8

In a functional language lists are immutable, too.

Why is this surprising? Linked lists are easily extendable, whereas strings are fixed size...

Reply on news.ycombinator.com