[sunde887]

I am looking to flatten a tree into a list using map rather than a more direct approach. The direct approach I was able to develop as:

(define (flatten tree)
    (cond ((null? tree) nil)
          ((not (pair? tree))
           (list tree))
          (else
           (append (flatten (car tree))
                   (flatten (cdr tree))))))

Not I would like to do something like

(define (flatten tree)
    (map <??> tree))

Where both of these will produce '(1 2 3 4 5) when passed in '(1 (2 (3 4) 5))

I am unsure of what kind of function to pass into map, to me it seems like the process decomposes fairly naturally into two cases. Either the car input is a pair or an element, if it is an element, it should pass it onto map, if it is a pair I am not sure where to proceed.

It seems that if it is an element you want to recurse into tree further, but recursing onto car, and cdr produces a function akin to the first posted.

Any help would be appreciated, I've been trying to find the answer for quite a while without luck.

[sepp2k]

The list returned by map will always be the same number of elements as the list given to map. If you consider the fact the list returned by flatten will often have a different number of elements than the one to given to it, it becomes clear that flatten could not possibly be implemented using map.

[sunde887]

With that in mind, I'd like to elaborate my question. The goal is to count the number of leaves in a tree using a procedure called accumulate.

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

I am to fill the template given which is of the following form:

(define (count-leaves t)
    (accumulate <??> <??> (map <??> <??>)))

My thought was to simply flatten the tree and count the length, but now it is clear that a map cannot flatten a tree properly.

I am merely asking for some insight into the problem, I am at a loss at solving it using map, although using a separate procedure in place of map is simple enough.

[sepp2k]

You can give map a lambda which maps the element to 1 if it is a leaf or to the number of leaves in the subtree if it is a subtree (by calling count-leaves recursively). Then you can use accumulate to sum up those numbers.

[sunde887]

Once again you helped me solve it. Thanks a bunch!