scheme - 如何在 Racket 中手动展平列表(方案)

Question

如何在不使用 Racket 内置的展平函数的情况下展平列表？

据我了解，展平的默认实现是

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

但我不完全确定如何不使用展平函数，因为我不知道它在幕后是如何工作的。除了这段代码的实现之外，我找不到对此的良好解释。有人可以解释一下吗

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

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

Answer 1

显示的第一个实现是独立的，但不正确，它没有调用 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))))