list - 在 Scheme 中展平关联列表

Question

(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)

输出:

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

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

我试图在 Scheme 中展平关联列表，但是括号即使我将 list 更改为 cons，也会继续出现。我做错了什么吗？

Answer 1

您在 disassociate 中创建列表的方式有误。试试这个:

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

或者，使用 list* :

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

上面假设关联列表使用 cons 将值粘在一起，请注意输出列表是如何通过 cons 第一个元素，然后是第二个元素创建的然后调用递归。另一方面，如果关联列表是使用 list 创建的以将值粘在一起，那么这是解除关联的方法:

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

或者:

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

更惯用的解决方案是使用高阶过程来处理输入列表。方法如下，使用 foldr对于问题中描述的两个关联列表变体:

; 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))