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