CODEWITHSUNDEEP
listlispcommon-lispclisp
Barrett
Barrett

Reputation: 23

LISP length of the longest sublist

I want to generate the length of the longest sublist. For example, for the list (1 (2 (3 (4 5)) (6 7) 8) 9) , the result would be 4, because of the sublist (2 (3 (4 5)) (6 7) 8), which has 4 as the length.

I have tried to do this:

(defun len(l)
    (cond
         ((null l) 0)
         ((atom l) 1)
         (t (+ (len(cdr l)) 1))
    )
)
(defun lun(l)
    (cond
        ((atom l) 1)
        (t(apply #'max (mapcar #' len l)))
    )   
)

For the example above, it returns 4, but the problem is that it analyses just the first level of the sublist. If i try to resolve it for the list (1 (2 (3 (4 5 a a a a)) (6 7) 8) 9) it also returns 4, even though it should be 6 because of the list (4 5 a a a a), it still only takes the list (2 (3 (4 5 a a a a)) (6 7) 8).

Thank you in advance.

Upvotes: 1

Views: 774

Answers (1)

coredump
coredump

Reputation: 38799

Your inputs are list of lists of lists (etc.), also known as trees. You want to compute the longest length of one of the lists that makes a tree. Roughly speaking, you need to iterate over subtrees, compute their respective longest length, and combine those length into a new, maximal length.

A first sketch of the function is as follows, based on the LOOP macro (you still need a bit of work to convert it to a fully recursive solution):

(defun longest-length (tree)
  (loop for subtree in tree maximize (longest-length subtree)))

Just as explained above, you divide your problems into subproblems, solve them recursively by finding for each subtree their longest length, and combine them by returning the maximum of each local maximum.

But the above is missing a couple of things. First, you need to take into account that the tree's length itself should be computed:

(defun longest-length (tree)
  (max (length tree)
       (loop for subtree in tree maximize (longest-length subtree))))

Also, the code fails when it reaches items that are not cons-cells. You now have to add code for the base case where trees are not cons-cells. In particular, nil is treated as an empty lists and not as a symbol:

(defun longest-length (tree)
  (typecase tree
    (cons (max (length tree)
               (loop
                 for subtree in tree
                 maximize (longest-length subtree))))
    (null 0)
    (t 1)))

Here is a test:

CL-USER> (longest-length '(1 (2 (3 (4 5 a a a a)) (6 7) 8) 9))
6

Consider also using reduce, which unlike apply introduces no restrictions on the number of elements in the list (call-argument-limit):

(reduce #'max (mapcar ... tree) :initial-value (length tree))

Upvotes: 4

Related Questions