User Tools


This shows you the differences between two versions of the page.

Link to this comparison view

cl:functions:list-length [2019/06/15 02:00]
cl:functions:list-length [2019/06/16 07:00] (current)
Line 1: Line 1:
 +====== Function LIST-LENGTH ======
 +  * **list-length** //list// → //length//
 +====Arguments and Values====
 +  * //list// - a //​[[CL:​Glossary:​proper list]]// or a //​[[CL:​Glossary:​circular list]]//.
 +  * //length// - a non-negative //​[[CL:​Glossary:​integer]]//,​ or **[[CL:​Constant Variable:​nil]]**.
 +Returns the //​[[CL:​Glossary:​length]]//​ of //list// if //list// is a //​[[CL:​Glossary:​proper list]]//. Returns **[[CL:​Constant Variable:​nil]]** if //list// is a //​[[CL:​Glossary:​circular list]]//.
 +(list-length '(a b c d)) <​r>​4</​r>​
 +(list-length '(a (b c) d)) <​r>​3</​r>​
 +(list-length '()) <​r>​0</​r>​
 +(list-length nil) <​r>​0</​r>​
 +([[CL:​Macros:​defun]] circular-list (&rest elements)
 +  ([[CL:​Special Operators:​let]] ((cycle ([[CL:​Functions:​copy-list]] elements))) ​
 +    ([[CL:​Functions:​nconc]] cycle cycle))) <​r>​CIRCULAR-LIST</​r>​
 +(list-length (circular-list 'a 'b)) <​r>​[[CL:​Constant Variable:​nil|NIL]]</​r>​
 +(list-length (circular-list 'a)) <​r>​[[CL:​Constant Variable:​nil|NIL]]</​r>​
 +(list-length (circular-list)) <​r>​0</​r>​
 +====Side Effects====
 +====Affected By====
 +====Exceptional Situations====
 +Should signal an error of type type-error if //list// is not a //​[[CL:​Glossary:​proper list]]// or a //​[[CL:​Glossary:​circular list]]//.
 +====See Also====
 +**[[CL:​Functions:​length|Function LENGTH]]**
 +====Example Implementation====
 +**list-length** could be implemented as follows:
 +([[CL:​Macros:​defun]] list-length (//​x//​)  ​
 +  ([[CL:​Macros:​do]] ((//n// 0 ([[CL:​Functions:​plus|+]] //n// 2))           ;​Counter.
 +       ​(//​fast//​ //x// ([[CL:​Functions:​cddr]] //​fast//​)) ​   ;Fast pointer: leaps by 2.
 +       ​(//​slow//​ //x// ([[CL:​Functions:​cdr]] //​slow//​))) ​   ;Slow pointer: leaps by 1.
 +      ()
 +    ;; If fast pointer hits the end, return the count.
 +    ([[CL:​Macros:​when]] ([[CL:​Functions:​endp]] //fast//) ([[CL:​Macros:​return]] //n//))
 +    ([[CL:​Macros:​when]] ([[CL:​Functions:​endp]] ([[CL:​Functions:​cdr]] //fast//)) ([[CL:​Macros:​return]] ([[CL:​Functions:​one-plus|1+]] //n//)))
 +    ;; If fast pointer eventually equals slow pointer,
 +    ;;  then we must be stuck in a circular list.
 +    ;; (A deeper property is the converse: if we are
 +    ;;  stuck in a circular list, then eventually the
 +    ;;  fast pointer will equal the slow pointer.
 +    ;;  That fact justifies this implementation.)
 +    ([[CL:​Macros:​when]] ([[CL:​Macros:​and]] ([[CL:​Functions:​eq]] //fast// //slow//) ([[CL:​Functions:​greater|>​]] //n// 0)) ([[CL:​Macros:​return]] nil))))