List Functions

The head function is used to get the first element of a list, but what it returns is still wrapped in the list. If we want to actually get the element out of this list we need to extract it somehow.

Single element lists evaluate to just that element, so we can use the eval function to do this extraction. We can also define a couple of helper functions for aid extracting the first, second and third elements of a list. We’ll use these function more later.

; First, Second, or Third Item in List
(fun {fst l} { eval (head l) })
(fun {snd l} { eval (head (tail l)) })
(fun {trd l} { eval (head (tail (tail l))) })

We looked briefly at some recursive list functions a few chapters ago. Naturally there are many more we can define using this technique.

To find the length of a list we can recursive over it adding 1 to the length of the tail. To find the nth element of a list we can perform the tail operation and count down until we reach 0. To get the last element of a list we can just access the element at the length minus one.

; List Length
(fun {len l} {
  if (== l nil)
    {0}
    {+ 1 (len (tail l))}
})

; Nth item in List
(fun {nth n l} {
  if (== n 0)
    {fst l}
    {nth (- n 1) (tail l)}
})

; Last item in List
(fun {last l} {nth (- (len l) 1) l})

There are lots of other useful functions that follow this same pattern. We can define functions for taking and dropping the first so many elements of a list, or functions for checking if a value is an element of a list.

; Take N items
(fun {take n l} {
  if (== n 0)
    {nil}
    {join (head l) (take (- n 1) (tail l))}
})

; Drop N items
(fun {drop n l} {
  if (== n 0)
    {l}
    {drop (- n 1) (tail l)}
})

; Split at N
(fun {split n l} {list (take n l) (drop n l)})

; Element of List
(fun {elem x l} {
  if (== l nil)
    {false}
    {if (== x (fst l)) {true} {elem x (tail l)}}
})

These functions all follow similar patterns. It would be great if there was some way to extract this pattern so we don’t have to type it out every time. For example we may want a way we can perform some function on every element of a list. This is a function we can define called map. It takes as input some function, and some list. For each item in the list it applies f to that item and appends it back onto the front of the list. It then applies map to the tail of the list.

; Apply Function to List
(fun {map f l} {
  if (== l nil)
    {nil}
    {join (list (f (fst l))) (map f (tail l))}
})

With this we can do some neat things that look a bit like looping. In some ways this concept is more powerful than looping. Instead of thinking about performing some function to each element of the list in turn, we can think about acting on all the elements at once. We map the list rather than changing each element.

lispy> map - {5 6 7 8 2 22 44}
{-5 -6 -7 -8 -2 -22 -44}
lispy> map (\ {x} {+ x 10}) {5 2 11}
{15 12 21}
lispy> print {"hello" "world"}
{"hello" "world"}
()
lispy> map print {"hello" "world"}
"hello"
"world"
{() ()}
lispy>

An adaptation of this idea is a filter function which, takes in some functional condition, and only includes items of a list which match that condition.

; Apply Filter to List
(fun {filter f l} {
  if (== l nil)
    {nil}
    {join (if (f (fst l)) {head l} {nil}) (filter f (tail l))}
})

This is what it looks like in practice.

lispy> filter (\ {x} {> x 2}) {5 2 11 -7 8 1}
{5 11 8}

Some loops don’t exactly act on a list, but accumulate some total or condense the list into a single value. These are loops such as sums and products. These can be expressed quite similarly to the len function we’ve already defined.

These are called folds and they work like this. Supplied with a function f, a base value z and a list l they merge each element in the list with the total, starting with the base value.

; Fold Left
(fun {foldl f z l} {
  if (== l nil)
    {z}
    {foldl f (f z (fst l)) (tail l)}
})

Using folds we can define the sum and product functions in a very elegant way.

(fun {sum l} {foldl + 0 l})
(fun {product l} {foldl * 1 l})