An Early LISP Program

March 1, 2011

Here’s our exact translation of that program to Scheme:

(define (collapse l)
  (cond ((atom? l) (cons l '()))
        ((null? (cdr l))
          (cond ((atom? (car l)) l)
                (else (collapse (car l)))))
        (else (append (collapse (car l))
                      (collapse (cdr l))))))

These examples come from the original Fox program listing:

> (collapse '((((a b) ((c))) ((d (e f)) (g) ((h))))))
(a b c d e f g h)
> (collapse '((a (b (c (d (e))) f (g (h j))))))
(a b c d e f g h j)
> (collapse '((((((a) b) c) d) e)))
(a b c d e)

You might find it instructive to compare collapse, given above, to the flatten function of the Standard Prelude, which performs the same task. If your Scheme system doesn’t provide atom?, use this:

(define (atom? x)
  (and (not (pair? x)) (not (null? x))))

You can run the program at .

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 […]

  2. My Haskell solutions (see for a version with comments):

    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
            return collapse(x[0]) + 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
            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)
                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 =
            if isinstance(item,Iterable) and not isinstance(item, basestring):
                seq = chain(item,seq)
                yield item
  8. Lautaro Pecile said
    def flatten(l):
        lst = []
        for e in l:
            if isinstance(e, list):
        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

Leave a Reply

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

You are commenting using your 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 )

Google+ photo

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

Connecting to %s


Get every new post delivered to your Inbox.

Join 687 other followers

%d bloggers like this: