How to manually flatten a list in Racket (Scheme)

Question

How could one go about flattening a list without using the flatten function built in to racket?

I understand that the default implementation of flatten is

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

but im not entirely sure how to go about not using the flatten function as I do not know how it is working behind the scenes. I couldn't find a good explanation of this besides implementations of this code. Could someone please explain

This is my very bad attempt and im pretty much clueless because this is not even close and will not run....

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

Solution

The first implementation shown is self-contained but incorrect, and it's not calling Racket's built-in flatten - it's simply calling itself recursively, rename it to see what I mean. Here's a fixed version:

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

Or a bit simpler:

(define (my-flatten lst)
  (cond ((null? lst) '())
        ((pair? lst)
         (append (my-flatten (car lst)) (my-flatten (cdr lst))))
        (else (list lst))))

Comments

[James Combs]

Im sorry, I must have misinterpreted the code that I was reading. I've been programming for a few hours, sometimes things get twisted up after awhile. I am getting a quote in my output though, what does this mean? > (my-flatten '(1 2 '(3 4) 5)) '(1 2 quote 3 4 5) -- Sorry for my bad understanding of Racket, I am pretty new to this

[Óscar López]

@JamesCombs remove the innermost quote, that's causing the problem

[Sylwester]

I think list? might be O(1) in #!racket but using pair? will support dotted lists as well (at least the last version) .

[James Combs]

@ÓscarLópez thanks for all of your help, if I could poke your brain just once more to fully understand the nature of this... Inside of the append function, when executing the recursion, does it execute both recursive statements at the same time, building 2 different stack frames? To me, this would be the only explanation that this works, otherwise the first recursive statement would just keep calling for the first element of the list and never reach the base case. Is this correct?

[Óscar López]

@JamesCombs The recursive calls are executed sequentially, but append is executed only when both have returned from their respective calls. Clearly the base case is reached, why shouldn't it?. If this answer was helpful for you, please don't forget to accept it, just click on the check mark to its left ;)