CODEWITHSUNDEEP
listscheme
gebby
gebby

Reputation: 165

Flattening an association list in Scheme

(define (associate lst)
    (if (or (null? lst) (= (length lst) 1))
        '()
        (cons (cons (car lst) (cadr lst)) (associate (cddr lst)))))

(define (disassociate lst)
    ;(display (caar lst))
    (if (null? lst)
        '()
        (cons (cons (caar lst) (cdar lst)) (disassociate (cdr lst)))))

(display (disassociate '((a . 1) (b . 2) (c . 3))))
(newline)
(display (associate '(a 1 b 2 c)))
(newline)

OUTPUT:

;; with list
((a 1) ((b 2) ((c 3) ())))
((a . 1) (b . 2))

;; with cons
((a . 1) (b . 2) (c . 3))
((a . 1) (b . 2))

I'm trying to flatten an association list in Scheme but the brackets keep turning up even when I change the list to cons. Am I doing something wrong?

Upvotes: 3

Views: 186

Answers (2)

GoZoner
GoZoner

Reputation: 70135

Your disassociate line needs to read:

(cons (caar lst) (cons (cdar lst) (disassociate (cdr lst)))))

quasi-quotation! Sometimes these are more clearly implemented using quasi-quotation because quasi-quotation lets you see the resulting list structure.

(define (associate lst)
  (if (or (null? lst) (null? (cdr lst)))
       '()
       `(,(cons (car lst) (cadr lst)) ,@(associate (cddr lst)))))

(define (disassociate lst)
  (if (null? lst)
      '()
      `(,(caar lst) ,(cdar lst) ,@(disassociate (cdr lst)))))

> (associate (disassociate '((a . 1) (b . 2))))
((a . 1) (b . 2))

Note that you could also write the associate quasi-quotation as:

       `((,(car lst) . ,(cadr lst)) ,@(associate (cddr list)))))

but that starts getting harder to read for me even though it makes the association pair explicit.

Upvotes: 3

Óscar López
Óscar López

Reputation: 235984

There's an error in the way you're creating the list in disassociate. Try this:

(define (disassociate lst)
  (if (null? lst)
      '()
      (cons (caar lst)
            (cons (cdar lst) 
                  (disassociate (cdr lst))))))

Or alternatively, using list*:

(define (disassociate lst)
  (if (null? lst)
      '()
      (list* (caar lst)
             (cdar lst) 
             (disassociate (cdr lst)))))

The above assumes that the association list is using cons to stick together the values, notice how the output list is created by consing the first element, then the second and then calling the recursion. On the other hand, if the association list was created using list to stick together the values, then this is the way to disassociate it:

(define (disassociate lst)
  (if (null? lst)
      '()
      (cons (caar lst)
            (cons (cadar lst) ; here's the change
                  (disassociate (cdr lst))))))

Or alternatively:

(define (disassociate lst)
  (if (null? lst)
      '()
      (list* (caar lst)
             (cadar lst) ; here's the change
             (disassociate (cdr lst)))))

A more idiomatic solution would be to use higher-order procedures to process the input list. Here's how, using foldr for the two association list variants described in the question:

; associations created with cons
(define (disassociate lst)
  (foldr (lambda (pr ac) (list* (car pr) (cdr pr) ac))
         '()
         lst))

; associations created with list
(define (disassociate lst)
  (foldr (lambda (pr ac) (list* (car pr) (cadr pr) ac))
         '()
         lst))

Upvotes: 3

Related Questions