[racket] Value Extraction from Lists vs. Structures

From: Matthias Felleisen (matthias at ccs.neu.edu)
Date: Tue Dec 7 09:11:21 EST 2010

Here is an expansion on Noel's answer. 

When the compiler sees a 

  (struct book (author title))

it creates code that allocates a vector of three words: 
 -- one that says "I am not a vector, but a book struct"
 -- one that holds the author value 
 -- one that holds the title value 
The functions 
 book-author translate into  a vector-ref that accesses the second slot above
 book-title  a vector-ref that accesses the third slot above

You can spell this out, except for the first slot, like this: 

 (define (book a t) (vector *tag-for-book* a t))
 (define (book-author b) ... (vector-ref b 1) ...)
 (define (book-title b) ... (vector-ref b 2) ...)

and as a bonus I throw in 

 (define (book? b) ... (vector-ref b 0) ... *tag-for-book* ...)

Since you know how vectors work in constant time, you now know how structs work in constant time. 


On Dec 6, 2010, at 11:42 PM, Luke Jordan wrote:

> I'm reading HtDP 29.3.
> 
> I get how value extraction from lists works in O(n) time, but how does extraction from structures work in O(1)?
> 
> Thanks (for being the "help me with HtDP" mailing list as well as the Racket mailing list...)
> 
> Luke
> _________________________________________________
>  For list-related administrative tasks:
>  http://lists.racket-lang.org/listinfo/users



Posted on the users mailing list.