Programming Praxis

9 Responses to “An Early LISP Program”

1. Programming Praxis – An Early LISP Program « Bonsai Code said

   March 1, 2011 at 10:43 AM

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

   March 1, 2011 at 10:43 AM

   My Haskell solutions (see http://bonsaicode.wordpress.com/2011/03/01/programming-praxis-an-early-lisp-program/ 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

   March 1, 2011 at 2:51 PM

   Basically a translation:

   def collapse(x):
       if not isinstance(x, list):
           return [x]
       elif len(x) == 0:
           return x
       else:
           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

   March 1, 2011 at 8:09 PM

   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

   March 2, 2011 at 1:19 AM

   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. Histoire lispienne said

   March 4, 2011 at 12:10 PM

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

   March 7, 2011 at 11:35 PM

   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

   March 10, 2011 at 9:05 PM

   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

   July 12, 2012 at 9:35 PM

   (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