PROSAGA码农传奇-lisp-LISP长度最长的子列表

<div class =“post-text”itemprop =“text”>
  
    您的输入是列表（等）列表的列表，也称为树。
您想要计算构成树的列表之一的最长长度。粗略地说，您需要迭代子树，计算它们各自的最长长度，并将这些长度组合成一个新的最大长度。
  
  
    该函数的第一个草图如下，基于LOOP宏（您仍需要一些工作将其转换为完全递归的解决方案）：
  
   <pre>
 <code>
 (defun longest-length (tree)
 (loop for subtree in tree maximize (longest-length subtree)))

</code>
 </pre>
  
    正如上面所解释的那样，你将问题分成子问题，通过查找来递归地解决它们
对于每个子树，它们的最长长度，并通过返回它们来组合它们
每个局部最大值的最大值。
  
  
    但上面缺少一些东西。首先，您需要考虑树的长度本身应该计算：
  
   <pre>
 <code>
 (defun longest-length (tree)
 (max (length tree)
 (loop for subtree in tree maximize (longest-length subtree))))

</code>
 </pre>
  
    此外，代码在到达非cons-cells的项目时失败。
您现在必须为树不是缺陷单元的基本情况添加代码。特别是，nil被视为空列表而不是符号：
  
   <pre>
 <code>
 (defun longest-length (tree)
 (typecase tree
 (cons (max (length tree)
 (loop
 for subtree in tree
 maximize (longest-length subtree))))
 (null 0)
 (t 1)))

</code>
 </pre>
  
    这是一个测试：
  
   <pre>
 <code>
 CL-USER> (longest-length '(1 (2 (3 (4 5 a a a a)) (6 7) 8) 9))
6

</code>
 </pre>
  
    考虑也使用
     <code>
 reduce
 </code>
    ，不像
     <code>
 apply
 </code>
     对列表中的元素数量没有限制（
     <code>
 call-argument-limit
 </code>
    ）：
  
   <pre>
 <code>
 (reduce #'max (mapcar ... tree) :initial-value (length tree))

</code>
 </pre>
</DIV>