## An Early LISP Program

### March 1, 2011

Today we have another exercise in our continuing theme of historical computing, celebrating the publication of the Lisp I Programmer’s Manual on this date fifty-one years ago. Over at his blog Abstract Heresies, LISP/Scheme expert and general curmudgeon Joe Marshall recalls this program from that manual, written by Phyllis Fox:

```DEFINE (((COLLAPSE,(LAMBDA,(L),(COND,    ((ATOM,L), (CONS,L,NIL))    ((NULL,(CDR,L)),       (COND,((ATOM,(CAR,L)),L),(T,(COLLAPSE,(CAR,L)))))    (T,(APPEND,(COLLAPSE,(CAR,L)),(COLLAPSE,(CDR,L))))))))) () COLLAPSE ((((A,B),((C))),((D,(E,F)),(G),((H))))) () COLLAPSE ((A,(B,(C,(D,(E))),F,(G,(H,J))))) () COLLAPSE ((((((A),B),C),D),E)) ()    STOP))))))))))STOP```

The program collapses a nested list into an un-nested one. Here’s the same program in modern Lisp:

```(defun collapse (l)   (cond ((atom l) (cons l nil))         ((null (cdr l))          (cond ((atom (car l)) l)              (t (collapse (car l)))))         (t (append (collapse (car l))                    (collapse (cdr l))))))```

Your task is to write a function to un-nest a nested list. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 9 Responses to “An Early LISP Program”

1. […] today’s Programming Praxis exercise, our goal is to write a function to un-nest a list. Let’s get […]

Solution 1:

```collapse_data :: List a -> [a]
collapse_data (E x) = [x]
collapse_data (L xs) = collapse_data =<< xs
```

Solution 2:

```import Data.Dynamic

collapse_dyn :: Typeable a => Dynamic -> [a]
collapse_dyn x = maybe (maybe [] return \$ fromDynamic x)
(collapse_dyn =<<) (fromDynamic x)
```

Solution 3:

```{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies,
FlexibleInstances, UndecidableInstances #-}

class Collapsible a b | a -> b where
collapse :: a -> [b]

instance (Collapsible a c, Collapsible b c) => Collapsible (a, b) c where
collapse (a, b) = collapse a ++ collapse b

instance Collapsible Char Char where
collapse c = [c]
```
3. Graham said

Basically a translation:

```def collapse(x):
if not isinstance(x, list):
return [x]
elif len(x) == 0:
return x
else:
return collapse(x) + collapse(x[1:])
```

I was curious whether I could get a more “Pythonic” version going, since this could run up against
Python’s recursion limit if fed a suitably hideous list. Without much time today, I decided to research
what others had come up with; I ran across this “trampolined-style” version, which is certainly stretching my mind a bit.

4. Mike said

Here’s a generator that returns the items of the input iterable in “flattened-order”.
You have to collect the output in a list or tuple. Note that handling of strings is
somewhat ambiguous in python, because a string is an iterable. I chose to treat strings
as atoms rather than nested iterables.

Likely to raise an exception if the input is nested more than 1000 deep.

```from collections import Iterable

def flatten(arg):
'''returns items from nested iterables in 'flattened' order.
>>> seq = (xrange(2,5),'abc',(n*n for n in range(1,5)))
>>> list(flatten(seq))
[2, 3, 4, 'abc', 1, 4, 9, 16]
'''

if isinstance(arg, Iterable) and not isinstance(arg, (str, unicode)):
for item in arg:
for subitem in flatten(item):
yield subitem
else:
yield arg

```
5. Graham said

Nice generator, Mike! If you wanted to avoid the import, you could use

```def is_iterable(arg):
return hasattr(arg, "__iter__")
```

and then modify your line 10 as needed (or just call `hasattr(arg, "__iter__")` directly in line 10).

6. […] Aujourd’hui, j’écrirais ce programme comme ça : ; Flatten a Slist (i.e [Sexp]) ; Slist -> [Symbol] (define collapse   (lambda (lst)     (mappend collapse-sexp lst))) ; Flatten a Sexp (Symbol | Slist) ; Sexp -> [Symbol] (define collapse-sexp   (lambda (sexp)     (if (list? sexp)       (collapse sexp)       (list sexp)))) […]

7. Mike said

Thanks Graham.

Here are two non-recursive versions. The first flattens a list ‘in-place’, the second is a generator that works with nested Iterables.

```
def flatten1(lst):
""" Flatten nested list 'in-place'

>>> x = [1,2,[3,4,[5,6,[]],7],8,9]
>>> flatten1(x)
>>> x
[1, 2, 3, 4, 5, 6, 7, 8, 9]
"""
end = len(lst)
n = 0
while n < end:
if isinstance(lst[n], list):
lst[n:n+1] = lst[n]
end = len(lst)
else:
n += 1

# version 2
from itertools import chain

def flatten2(iterable):
""" generator that returns items from nested iterables in flattened order.

>>> x = [1,2,[3,4,[5,6,[]],7],8,9]
>>> list(flatten2(x))
[1, 2, 3, 4, 5, 6, 7, 8, 9]
"""
seq = iter(iterable)
while True:
item = seq.next()
if isinstance(item,Iterable) and not isinstance(item, basestring):
seq = chain(item,seq)
else:
yield item
```
8. Lautaro Pecile said
```def flatten(l):
lst = []
for e in l:
if isinstance(e, list):
lst.extend(foo(e))
else:
lst.append(e)
return lst
```
9. Zelah said
```(define (flatten tree)
(cond ((null? tree) '())
((not (pair? tree)) tree)
((null? (car tree))
(flatten (cdr tree)))
((pair? (car tree))
(append (flatten (car tree))
(flatten (cdr tree))))
(else (cons (car tree)
(flatten (cdr tree))))))

(display (flatten '((((()) 1 2) 3) (()) 4 (5))))

```

run the code here