如何在Racket中手动压平列表(Scheme)

Question

如何在不使用内置的扁平功能进行球拍的情况下展平列表？

我知道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)))

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