4 Replies - 3237 Views - Last Post: 07 December 2011 - 07:01 PM

#1 sunde887  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 14-March 11

Lisp: Flatten a tree using map

Posted 07 December 2011 - 05:39 PM

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.

Is This A Good Question/Topic? 0
  • +

Replies To: Lisp: Flatten a tree using map

#2 sepp2k  Icon User is online

  • D.I.C Lover
  • member icon

Reputation: 2019
  • View blog
  • Posts: 3,049
  • Joined: 21-June 11

Re: Lisp: Flatten a tree using map

Posted 07 December 2011 - 05:44 PM

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.
Was This Post Helpful? 2
  • +
  • -

#3 sunde887  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 14-March 11

Re: Lisp: Flatten a tree using map

Posted 07 December 2011 - 06:30 PM

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.
Was This Post Helpful? 0
  • +
  • -

#4 sepp2k  Icon User is online

  • D.I.C Lover
  • member icon

Reputation: 2019
  • View blog
  • Posts: 3,049
  • Joined: 21-June 11

Re: Lisp: Flatten a tree using map

Posted 07 December 2011 - 06:37 PM

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.
Was This Post Helpful? 1
  • +
  • -

#5 sunde887  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 14-March 11

Re: Lisp: Flatten a tree using map

Posted 07 December 2011 - 07:01 PM

Once again you helped me solve it. Thanks a bunch!
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1