# Playtime with Lisp!

Since it has been a while that I have updated my blog, I thought of resurrecting it (in a manner of speaking) by playing around with some Common Lisp.

My first exposure to Functional Programming was, strangely enough, not through Haskell or even Scheme, but through Common Lisp. I know that many purists (on both sides) will claim that Common Lisp is a rather bad example of a Functional language, but I argue that Common Lisp is indeed one of the most performant Functional languages out there. Mutability alone does not dictate whether a language is Functional or not.

Working through the great book, “Programming in Haskell” (2nd Edition) by Professor Graham Hutton, I came across the following functions which were, as expected, rather niftily expressed in Haskell:

`subs` – the usual recursive way of generating all subsequences of a list.

```subs :: [a] -> [[a]]
subs [] = [[]]
subs (x:xs) = yss ++ map (x:) yss
where
yss = subs xs

*Misc> subs [1,2,3]
[[],,,[2,3],,[1,3],[1,2],[1,2,3]]
```

`interleave` – insert an element into every possible position of the target list.

```
interleave :: a -> [a] -> [[a]]
interleave x [] = [[x]]
interleave x (y:ys) = (x:y:ys) : map (y:) (interleave x ys)

*Misc> interleave 'a' "bcd"

```

and finally,

`perms` – generate all the permutations of a given list/sequence.

```
perms :: [a] -> [[a]]
perms [] = [[]]
perms (x:xs) = concat \$ map (interleave x) (perms xs)

*Misc> perms [1,2,3]
[[1,2,3],[2,1,3],[2,3,1],[1,3,2],[3,1,2],[3,2,1]]

```

Of course, this version uses plain recursion. The usual way I would generate permutations for practical purposes would be with something like Heap’s Algorithm as shown below (Rust implementation):

```
use std::fmt::Debug;

fn heap(a: &mut Vec, n: usize) {
if n == 0 {
println!("{:?}", a);
} else {
for i in 0..n - 1 {
heap(a, n - 1);

if n % 2 == 0 {
a.swap(i, n - 1);
} else {
a.swap(0, n - 1);
}
}

heap(a, n - 1);
}
}

fn main() {
let mut v = vec![1, 2, 3];
let vlen = v.len();

heap(&mut v, vlen);

let mut vv = vec!['a', 'b', 'c', 'd'];
let vvlen = vv.len();

heap(&mut vv, vvlen);
}

bash-3.2\$ rustc heap.rs && ./heap
[1, 2, 3]
[2, 1, 3]
[3, 1, 2]
[1, 3, 2]
[2, 3, 1]
[3, 2, 1]
['a', 'b', 'c', 'd']
['b', 'a', 'c', 'd']
['c', 'a', 'b', 'd']
['a', 'c', 'b', 'd']
['b', 'c', 'a', 'd']
['c', 'b', 'a', 'd']
['d', 'b', 'a', 'c']
['b', 'd', 'a', 'c']
['a', 'd', 'b', 'c']
['d', 'a', 'b', 'c']
['b', 'a', 'd', 'c']
['a', 'b', 'd', 'c']
['a', 'c', 'd', 'b']
['c', 'a', 'd', 'b']
['d', 'a', 'c', 'b']
['a', 'd', 'c', 'b']
['c', 'd', 'a', 'b']
['d', 'c', 'a', 'b']
['d', 'c', 'b', 'a']
['c', 'd', 'b', 'a']
['b', 'd', 'c', 'a']
['d', 'b', 'c', 'a']
['c', 'b', 'd', 'a']
['b', 'c', 'd', 'a']

```

However, the purpose of this exercise is to simply translate the Haskell examples into Common Lisp (as idiomatic as possible). So here are the equivalent Common Lisp versions:

`subs`

```
(defun subs (lst)
"generate the subsequences of the given list"
(cond ((null lst) '(()))
(t (let ((first (car lst))
(subs-lst (subs (cdr lst))))
(append subs-lst
(mapcar #'(lambda (rest) (cons first rest))
subs-lst))))))

CL-USER> (subs '(a b c))

(NIL (C) (B) (B C) (A) (A C) (A B) (A B C))

```

`interleave`

```
(defun interleave (elem lst)
"generate a list of lists by inserting elem into every possible slot"
(cond ((null lst) `((,elem)))
(t (let ((fst (car lst))
(rst (cdr lst)))
(cons (cons elem lst)
(mapcar #'(lambda (lst1) (cons fst lst1))
(interleave elem rst)))))))

CL-USER> (interleave #\c (coerce "ab" 'list))
((#\c #\a #\b) (#\a #\c #\b) (#\a #\b #\c))

```

The interesting things is that there appears to be no equivalent in Common Lisp for the Haskell `concat` function. Well, so let’s write out our own!

`concat` – flatten a list of lists.

```
(defun concat (lsts)
"flatten the given list of lists"
(cond ((null lsts) '())
((null (cdr lsts)) (car lsts))
(t (append (car lsts) (concat (cdr lsts))))))

```

Now we can finally complete `perms`

```
(defun perms (lst)
"generate the permutations of the given list"
(cond ((null lst) '(()))
(t (let ((fst (car lst))
(rst (cdr lst)))
(concat (mapcar #'(lambda (lst1)
(interleave fst lst1)) (perms rst)))))))

CL-USER> (perms '(1 2 3))
((1 2 3) (2 1 3) (2 3 1) (1 3 2) (3 1 2) (3 2 1))

```

Nice!