relation between foldr and append in Scheme

Question

try to figure out how to use "append" in Scheme the concept of append that I can find like this:

----- part 1: understanding the concept of append in Scheme-----

1) append takes two or more lists and constructs a new list with all of their elements.

2) append requires that its arguments are lists, and makes a list whose elements are the elements of those lists. it concatenates the lists it is given. (It effectively conses the elements of the other lists onto the last list to create the result list.)

3) It only concatenates the top-level structure ==> [Q1] what does it mean "only concatenates the top-level"?

4) however--it doesn't "flatten" nested structures. ==> [Q2] what is "flatten" ? (I saw many places this "flatten" but I didn't figure out yet) ==> [Q3] why append does not "flatten" nested structures.

---------- Part 2: how to using append in Scheme --------------------------------

then I looked around to try to use "append" and I saw other discussion

based on the other discussion, I try this implementation

 [code 1]
 (define (tst-foldr-append lst)
  (foldr 
   (lambda (element acc) (append acc (list element)))      
    lst
    '())                          
  )

it works, but I am struggling to understand that this part ...(append acc (list element)...

what exactly "append" is doing in code 1, to me, it just flipping. then why it can't be used other logics e.g. i) simply just flip or iii).... cons (acc element).....

[Q4] why it have to be "append" in code 1??? Is that because of something to do with foldr ??

again, sorry for the long question, but I think it is all related.

Answer 1

Q1/2/3: What is this "flattening" thing?

Scheme/Lisp/Racket make it very very easy to use lists. Lists are easy to construct and easy to operate on. As a result, they are often nested. So, for instance

`(a b 34)

denotes a list of three elements: two symbols and a number. However,

`(a (b c) 34)

denotes a list of three elements: a symbol, a list, and a number.

The word "flatten" is used to refer to the operation that turns

`(3 ((b) c) (d (e f)))

into

`(3 b c d e f)

That is, the lists-within-lists are "flattened".

The 'append' function does not flatten lists; it just combines them. So, for instance,

(append `(3 (b c) d) `(a (9)))

would produce

`(3 (b c) d a (9))

Another way of saying it is this: if you apply 'append' to a list of length 3 and a list of length 2, the result will be of length 5.

Q4/5: Foldl really has nothing to do with append. I think I would ask a separate question about foldl if I were you.

Final advice: go check out htdp.org .

Answer 2

Q1: It means that sublists are not recursively appended, only the top-most elements are concatenated, for example:

(append '((1) (2)) '((3) (4)))
=> '((1) (2) (3) (4))

Q2: Related to the previous question, flattening a list gets rid of the sublists:

(flatten '((1) (2) (3) (4)))
=> '(1 2 3 4)

Q3: By design, because append only concatenates two lists, for flattening nested structures use flatten.

Q4: Please read the documentation before asking this kind of questions. append is simply a different procedure, not necessarily related to foldr, but they can be used together; it concatenates a list with an element (if the "element" is a list the result will be a proper list). cons just sticks together two things, no matter their type whereas append always returns a list (proper or improper) as output. For example, for appending one element at the end you can do this:

(append '(1 2) '(3))
=> '(1 2 3)

But these expressions will give different results (tested in Racket):

(append '(1 2) 3)
=> '(1 2 . 3)
(cons '(1 2) '(3))
=> '((1 2) 3)
(cons '(1 2) 3)
=> '((1 2) . 3)

Q5: No, cons will work fine here. You wouldn't be asking any of this if you simply tested each procedure to see how they work. Please understand what you're using by reading the documentation and writing little examples, it's the only way you'll ever learn how to program.