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]
[[],[3],[2],[2,3],[1],[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"
["abcd","bacd","bcad","bcda"]

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!

 

 

 

 

 

 

 

Advertisements

Speak your mind!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s