Dynamically fill a list with key value pairs

Question

I need to fill a list with pairs, for example: ((x 10)(z 5)).

My current method:

;;send the current list, and an id value pair
(define (setID idList ID VAL)

  (cond 
        ;;if the list is null, add the pair
        ((null? idList) (cons '(ID VAL) '()))    

        ;; if the ID already exists, overwrite it
        ((equal? ID (car(car idList)))  (cons '((cdr idList)) VAL))

        ;; continue the search
        (else  (setID (cdr idList) ID VAL))
  )
)

I realize I also need to use cons to keep the list in tact, but the first problem is that when I do something like (setID z 5), the returned list is exactly: ((id val)). Obviously, it needs to be ((z 10)). Is there anyway to do such a thing?

Answer 1

There are three main problems with your code:

• In here: (cons '(ID VAL) '())) you're building a new pair with the value (ID VAL) - that is, the first element is the symbol ID and the second is the symbol VAL. That's not what you want, you want the value of ID and the value of VAL. Make sure you understand the way a quote works
• When you find an existing ID you have to cons the newly modified pair with the rest of the list
• And even if the current pair isn't the one we're looking for, we also have to cons it to the output. Remember: we're building the answer as we go traversing the list

This is what I mean:

;;send the current list, and an id value pair
(define (setID idList ID VAL)
  (cond 
    ;;if the list is null, add the pair
    ((null? idList) (cons (list ID VAL) '()))
    ;; if the ID already exists, overwrite it
    ((equal? ID (car (car idList))) (cons (list ID VAL) (cdr idList)))
    ;; continue the search
    (else (cons (car idList) (setID (cdr idList) ID VAL)))))

And don't forget that the list returned after executing this procedure is a new one, you have to store it somewhere or pass it along as a parameter if you want to keep adding elements to it - because the list originally received as parameter remains unmodified. Now the procedure works as expected:

(setID '() 'x 10)
=> '((x 10))

(setID '((x 10)) 'y 20)
=> '((x 10) (y 20))

(setID '((x 10) (y 20)) 'x 30)
=> '((x 30) (y 20))

Answer 2

Don't re-invent the wheel, association lists are pretty common in scheme

Easiet thing here is the guard with a head tag. so that ((x 10)(z 5)) becomes (*idList* (x 10)(z 5))

;;send the current list, and an id value pair
(define (setID! idList ID VAL)
;;if a function mutates data end it with a bang
  (let ((ID-VAL (assoc ID (cdr idList)))) 
        ;;assoc returns #f if no match, with the ID-VAL pair if there is a match
        (if ID-VAL
            (set-car! (cdr ID-VAL) VAL)  
                     ;; if the ID already exists, overwrite it     
            (set-cdr! idList (cons (list ID VAL) (cdr idList)))))
                     ;;if ID into in assoc-list, add the pair
    idList)      ;;return the idList

Testing

(setID! '(*idList*) 'x 10)
;Value 3: (*idlist* (x 10))

(setID! '(*idlist* (x 10)) 'y 20)
;Value 4: (*idlist* (y 20) (x 10))

(setID! '(*idlist* (y 20) (x 10)) 'x 30)
;Value 9: (*idlist* (y 20) (x 30))

Answer 3

Here's a Racket-y version of the answer from @WorBlux :

Your "setID" is essentially already defined in Racket under the name dict-set.

(dict-set dict key v) → (and/c dict? immutable?)
   dict : (and/c dict? immutable?)
   key  : any/c
   v    : any/c

Functionally extends dict by mapping key to v, overwriting any existing mapping for key, and returning an extended dictionary. The update can fail with a exn:fail:contract exception if dict does not support functional extension or if key is not an allowed key for the dictionary.

Examples:

> (dict-set #hash() 'a "apple")
'#hash((a . "apple"))

> (dict-set #hash((a . "apple") (b . "beer")) 'b "banana")
'#hash((b . "banana") (a . "apple"))

> (dict-set '() 'a "apple")
'((a . "apple"))

> (dict-set '((a . "apple") (b . "beer")) 'b "banana")
'((a . "apple") (b . "banana"))

See the last two examples above.

And of course you can use dict-ref and other functions to look up values by key, or map over them, and so on.

Note that dict-set is slightly different what you described because assoc (as used by dict) uses (key . val) not (key val). In other words it uses (cons key val) not (list key val). It's more efficient to store two items with (cons a b) than (cons a (cons b '())).