Recursion in Lisp and making my own length function

Question

I am trying to make my own length/2 function(which allows you to find the length of a list) in lisp and am having an issue.

If I were to program this in java I would create a global index variable

that = 0

Then in the method I would do

if(list.equal(null))
{
    return index;
}
else
{
    index++;
    return functioname(tail of list) ;
}.

Obviously this is not actual java syntax but I am just trying to relay the logic I want to apply in lisp.

My main issue is that ifs in lisp only allow you to do

if test expression
    then do something
else
    do something else

while I am trying to do

if test expression
    then do something
else
    do 2x something

Is there a way I can accomplish this in lisp or is there a better way to go about this problem?

Ah sorry about that. I have made the necessary edit to the question — JmanxC, May 22 '16 at 02:43

Rahn · Accepted Answer · 2016-05-22T03:17:29.310

0

Do it recursively:

len(list):
    if list is null
        return 0
    else
        remove first_item from list
        return 1 + len(list)


(define (length items)
  (if (null? items)
      0
      (+ 1
         (length (cdr items)))))


(length (list 1 2 3))

3

Or use set!:

(define count 0)

(define (length items)
  (when (not (null? items))
    (set! count (+ count 1))
    (length (cdr items))))

(length (list 1 2 3 4 5))

count

5

edited May 22 '16 at 03:17

answered May 22 '16 at 02:49

Rahn

4,787
4
31
57

Ah yes that makes sense, but there is no way to use a global index variable to do the same thing?(ie instead of adding 1, increment the index) – JmanxC May 22 '16 at 02:54
@JmanxC I guess you want to do: change `count` variable (+1) while going through a list. But lisp variable is immutable by default. – Rahn May 22 '16 at 03:00
Yes exactly or (incr index) before the recursive call. Sorry I am not sure what you mean by immutable, what does (incr index) do if the variable cannot be altered? – JmanxC May 22 '16 at 03:09
@JmanxC about immutability: http://stackoverflow.com/questions/844536/advantages-of-stateless-programming – Rahn May 22 '16 at 03:24
Perfect the second example does exactly what I wanted. I will also have to read a bit more on immutability with regards to functional programming. From what I am getting, in functional programming variable immutability means that any change of state in a program(in this example a recursive call) does not change the state of a variable? Is this a correct understanding? If not I'll probably have to read more. – JmanxC May 22 '16 at 03:34
@JmanxC In fact many modern Lisp implementation does enable `mutability` though functional programming typically avoids using mutable state. – Rahn May 22 '16 at 03:45
Ah ok. One last problem haha I tried to apply the following and I get a result of nil. Not sure why. – JmanxC May 22 '16 at 04:02
(defun length2(myList) (when (not (equal nil myList) ) (defparameter index (+ index 1) ) (length2 (cdr myList) ) ) ) – JmanxC May 22 '16 at 04:02
Sorry for everything being on one line,not sure how to edit comments – JmanxC May 22 '16 at 04:03
I also tried setf instead of defparameter, with same results. Your "set!" is not a defined function in common lisp. – JmanxC May 22 '16 at 04:04
I am not sure what you are asking :P. I posted the code in my comment above but I wasn't sure how to space out different lines of text in comments. I applied the code in common lisp and it returned nil instead of the length of the list. – JmanxC May 22 '16 at 04:12
modify your code from `(defun length2 (myList) implementation)` to `(defun (length2 myList) implementation)` – Rahn May 22 '16 at 04:14
Gives the follow error : Error: (LENGTH2 MYLIST) is neither of type SYMBOL nor a list of the form (SETF SYMBOL). – JmanxC May 22 '16 at 04:18
@JmanxC I was wrong about the syntax. Did your initialize `index`? – Rahn May 22 '16 at 04:24
Yes I defined it before creating the function – JmanxC May 22 '16 at 04:32
ie: (setf index 0) – JmanxC May 22 '16 at 04:33

Paul Richter · Answer 2 · 2016-05-22T14:52:39.213

Scheme has the special operator begin (the Common Lisp equivalent is progn) that lets you group expressions which are executed in sequence, and returns the last one.

(if (null? items)
    0
    (begin (set! index (+ 1 index))
           (my-length (cdr items))
           index))

If the if expression returns nil under the false condition, then you can also use when (as in Rahn's answer) which is a bit more compact.

That said, having a global variable, or any variable at all, whose value gets changed (which is the purpose of a variable) is not the Lisp/recursive way of doing things. (Global variables are not a good thing in any language.) Rahn's first example is the only way any experienced Lisp programmer would do it.

In my example above, the (set! index (+ 1 index)) and index)) lines, and the global variable index are completely unnecessary if you add the 1 to the (my-length (cdr items)). If the list is empty, the length is zero; otherwise, the length is 1 + the length of the tail of the list.

Thanks for the help. I will just go about it not using global variables then and do it the first way. — JmanxC, May 22 '16 at 18:29

Recursion in Lisp and making my own length function

2 Answers2