A few things I just learned about Lisp

I was trying to implement the Fisher-Yates algorithm earlier this evening. This algorithm lets you randomly shuffle the contents of a list. I wanted to provide a list of songs and return a shuffled list. I decided to use Lisp for this since I don't know much Lisp and I want to build my skills.

After quite a bit of coding, I managed to write a four line function. But, I wasn't satisfied. I wondered: is my implementation correct? How could I improve my code? I went to the #lisp libera.chat IRC for assistance and, within minutes, had a discussion about my code.

I learned a few things:

1. (rotatef) lets you change the value of an item at a specified position in a list.
2. Use "(loop for i below (length arr) ...)" to iterate over all items in a sequence rather than a separate (range) function that creates another copy of a list I already have.
3. Use vectors rather than lists when you are doing in-place substitution (as I was because the Fisher-Yates algorithm involves changing the contents of elements in place). Vectors are a lot faster than lists. Retreiving items from vectors is O(1) whereas doing the same thing for lists is O(n).
4. You use (elt) to retrieve an item from a vector (whereas I was using nth earlier, which you use to get the nth item in a list).
5. You can use "with" to declare a variable that will only be accessible in the context of a function (this reminded me of Python's "with" context management statement, but that isn't really used in loops like it is here).

I ended up with this code:

(defun fisher-yates (arr) 
    (loop with len = (length arr)
        for i below len
        do (rotatef (elt arr i) (elt arr (random len)))
        finally (return arr)))

(print "Let's help you shuffle the ultimate playlist. Here's an order of music you can play today:")

(loop for i across (fisher-yates (vector "Bat Out of Hell" "Hard Times" "Paradise" "Skyfall"))
    do (print i))

My code:

1. Defines a function called fisher-yates that iterates over every item in a list and shuffles each item. At the end, my function returns the array with which I have been working.
2. I print some introductory text.
3. I execute the fisher-yates and print each item in the result to the console. I use a "vector" explicitly instead of a list. My code will not work with a list because I use elt.

Here is some sample output from my code:

"Bat Out of Hell" 
"Skyfall" 
"Hard Times" 
"Paradise"

Now I don't have to decide what to listen to next. I can use this Lisp function!

I also learned about the (time) function. (time) returns the amount of time it took to run a function. Here's how long it takes to run my fisher-yates function:

Evaluation took:
  0.000 seconds of real time
  0.000001 seconds of total run time (0.000001 user, 0.000000 system)
  100.00% CPU
  0 bytes consed

Barely any time at all. I am only changing items in a vector though.

In the #lisp IRC, someone made my function with 1000 items (using make-list and make-array) to prove that, at scale, my code would run a lot slower if I were using lists versus vectors. To retrieve these numbers, the person who helped me used the (time) function.

I am only at the beginning of getting my head around how to write programs in Lisp. I like little challenges like this: enough to introduce me to new concepts without pushing me too far. I wonder what I will learn next!

Tagged in lisp, algorithms, fisher-yates.