2

如果不使用内置于球拍中的 flatten 功能，如何将列表展平？

我知道 flatten 的默认实现是

(define (flatten lst)
  (cond 
    ((null? list)
      empty)
    ((list? (car lst))
      (append (flatten (car lst)) (flatten (cdr lst))))
    (else
      (cons (car lst) (flatten (cdr lst))))))

但我不完全确定如何不使用 flatten 功能，因为我不知道它在幕后是如何工作的。除了这段代码的实现之外，我找不到一个很好的解释。有人可以解释一下吗

这是我非常糟糕的尝试，我几乎一无所知，因为这甚至还没有接近并且不会运行....

(define acc null)
(define (my-flatten lst)
  (cond
    [(null? lst) null]
    [(list? (car lst)) (help-flatten (car lst)) (append (cdr lst) acc)]
    [else (append (car lst) acc) (my-flatten (cdr lst))]))

(define (help-flatten subLst)
  (if (null? subLst)
      (set! acc null)
      (append (car subLst) acc))
  (help-flatten (cdr subLst)))
4

1 回答 1

6

显示的第一个实现是自包含但不正确的，它没有调用 Racket 的内置flatten- 它只是递归地调用自己，重命名它以了解我的意思。这是一个固定版本：

(define (my-flatten lst)
  (cond ((null? lst) empty) ; you wrote `list` instead of `lst`
        ((pair? (car lst))  ; it's more efficient if we use `pair?`
         (append (my-flatten (car lst)) (my-flatten (cdr lst))))
        (else (cons (car lst) (my-flatten (cdr lst))))))

或者更简单一点：

(define (my-flatten lst)
  (cond ((null? lst) '())
        ((pair? lst)
         (append (my-flatten (car lst)) (my-flatten (cdr lst))))
        (else (list lst))))
于 2015-02-26T22:15:59.140 回答