Lisp nested list iteration

Question

I just started to learn Common Lisp and this is my first functional programming language. I am trying to learn about iterating through lists. I wrote these two functions:

(defun reverseList (liste)
    (defvar reversedList(list))
    (loop for i downfrom (-(length liste)1) to 0 do
     (setf reversedList (append reversedList (list(nth i liste)))))
    reversedList ;return
)


(defun countAppearance(liste element)
    (defvar count 0)
    (loop for i from 0 to (-(length liste) 1)do
        (if (= (nth i liste) element)
            (setf count (+ count 1))))
    count
)

Both work fine for a regular list(ex: (1 3 5 7 3 9) but I want them to work for nested lists too.

Examples:

countAppearance - Input: (1 (3 5) (3 7 8) 2) 3 -> Expected output:2

reverseList - Input: (1 (2 3)) -> Expected output: ((3 2) 1)

Note that iteration is the poster antithesis of functional programming. Common Lisp is a multi-paradigm language: out of the box it supports functional, imperative and object-oriented programming, and is easily extensible into other paradigms like declarative logic programming and what have you. — Kaz
– Kaz, Commented Nov 19, 2021 at 9:10

Martin Půda · Accepted Answer · 2021-11-18 16:06:24Z

Before I will show you solutions for nested lists, some notes about your code:

There is already function reverse for non-nested lists, so you don't have to reinvent the wheel.

=> (reverse (list 1 2 3 4 5))
(5 4 3 2 1)

If you need some local variables, use let or let*.
Lisp uses kebab-case, not camelCase, so rename reverseList as reverse-list and so on.
For (setf ... (+ ... 1)), use incf.
For iterating over list, use dolist.
Function count-occurrences can be written using recursion:

(defun count-occurrences (lst elem)
  (cond ((null lst) 0)
        ((= (car lst) elem) (+ 1 (count-occurrences (cdr lst) elem)))
        (t (count-occurrences (cdr lst) elem))))

CL-USER 3 > (count-occurrences (list 1 2 3 1 2 3) 2)
2

Or it can be written with let, dolist and incf:

(defun count-occurrences2 (lst elem)
  (let ((count 0))
    (dolist (e lst)
      (when (= e elem) (incf count)))
    count))

CL-USER 4 > (count-occurrences2 (list 1 2 3 1 2 3) 2)
2

Solutions for nested lists use recursion:

(defun deep-reverse (o)
  (if (listp o) 
      (reverse (mapcar #'deep-reverse o))
    o))

CL-USER 11 > (deep-reverse '(1 (2 3)))
((3 2) 1)

(defun deep-count (lst elem)
  (cond ((null lst) 0)
        ((listp (car lst)) (+ (deep-count (car lst) elem)
                              (deep-count (cdr lst) elem)))
        ((= (car lst) elem) (+ 1 (deep-count (cdr lst) elem)))
        (t (deep-count (cdr lst) elem))))

CL-USER 12 > (deep-count '(1 (3 5) (3 7 8) 2) 3)
2

Francis King · Accepted Answer · 2021-11-18 21:51:56Z

Welcome to functional programming.

Firstly, there are some problems with the code that you have provided for us. There are some spaces missing from the code. Spaces are important because they separate one thing from another. The code (xy) is not the same as (x y).

Secondly, there is an important difference between local and global variables. So, in both cases, you want a local variable for reversedList and count. This is the tricky point. Common Lisp doesn't have global or local variables, it has dynamic and lexical variables, which aren't quite the same. For these purposes, we can use lexical variables, introduced with let. The keyword let is used for local variables in many functional languages. Also, defvar may not do what you expect, since it is way of writing a value once, which cannot be overwritten - I suspect that defparameter is what you meant.

Thirdly, looking at the reverse function, loop has its own way of gathering results into a list called collect. This would be a cleaner solution.

(defun my-reverse (lst)
   (loop for x from (1- (length lst)) downto 0 collect (nth x lst)))

It can also be done in a tail recursive way.

(defun my-reverse-tail (lst &optional (result '()))
   (if lst
      (my-reverse-tail (rest lst) (cons (first lst) result))
      result))

To get it to work with nested lists, before you collect or cons each value, you need to check if it is a list, using listp. If it is not a list, just add it onto the result. If it is a list, add on instead a call to your reverse function on the item.

Loop also has functionality to count items.

Collectives™ on Stack Overflow

Lisp nested list iteration

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related