From: John Thingstad
Subject: flattening a nested list functionally
Date: Wed, 06 Dec 2006 19:35:41 +0000
Message-ID: <op.tj5kprfrpqzri1@pandora.upc.no>

Wrote this function to flatten a nested list.

(defparameter *test-list* '((1 2 3) (4 5 6 (7 8 9)) 10))

(defun flatten-reverse (element)
   (let ((new-element nil))
     (mapc
      (lambda (e)
        (if (consp e)
            (setf new-element (append (flatten-reverse e) new-element))
          (push e new-element)))
      element)
     new-element))

(defun flatten (list)
   (nreverse (flatten-reverse list)))

CL-USER 27 > (flatten *test-list*)
(1 2 3 4 5 6 7 8 9 10)

Not too bad if I may say so but what I was trying to do was write it in a
purely functional style. How do I do this without introducing a variable?

-- 
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/

• Re: flattening a nested list functionally Andras Simon
• Re: flattening a nested list functionally Giorgos Keramidas
  • Re: flattening a nested list functionally Kaz Kylheku

From: Andras Simon
Subject: Re: flattening a nested list functionally
Date: Wed, 06 Dec 2006 23:40:38 +0000
Message-ID: <vcdejrcegp5.fsf@csusza.math.bme.hu>

"John Thingstad" <··············@chello.no> writes:

> Wrote this function to flatten a nested list.
> 
> (defparameter *test-list* '((1 2 3) (4 5 6 (7 8 9)) 10))
> 
> (defun flatten-reverse (element)
>    (let ((new-element nil))
>      (mapc
>       (lambda (e)
>         (if (consp e)
>             (setf new-element (append (flatten-reverse e) new-element))
>           (push e new-element)))
>       element)
>      new-element))
> 
> (defun flatten (list)
>    (nreverse (flatten-reverse list)))
> 
> CL-USER 27 > (flatten *test-list*)
> (1 2 3 4 5 6 7 8 9 10)
> 
> Not too bad if I may say so but what I was trying to do was write it in a
> purely functional style. How do I do this without introducing a variable?

(defun flatten (list)
       (mapcan #'(lambda (e) (if (consp e) (flatten e) (list e))) list))

Doesn't look too good, but it's a start.

Andras

From: Giorgos Keramidas
Subject: Re: flattening a nested list functionally
Date: Sun, 24 Dec 2006 02:15:33 +0000
Message-ID: <87wt4ijayi.fsf@kobe.laptop>

On Wed, 06 Dec 2006 20:35:41 +0100,
John Thingstad" <··············@chello.no> wrote:
> Wrote this function to flatten a nested list.
>
> (defparameter *test-list* '((1 2 3) (4 5 6 (7 8 9)) 10))
>
> (defun flatten-reverse (element)
>   (let ((new-element nil))
>     (mapc
>      (lambda (e)
>        (if (consp e)
>            (setf new-element (append (flatten-reverse e) new-element))
>          (push e new-element)))
>      element)
>     new-element))
>
> (defun flatten (list)
>   (nreverse (flatten-reverse list)))
>
> CL-USER 27 > (flatten *test-list*)
> (1 2 3 4 5 6 7 8 9 10)
>
> Not too bad if I may say so but what I was trying to do was write it in a
> purely functional style. How do I do this without introducing a variable?

One way to flatten without a variable, since removing the intermediate
variables seems to be what you are after, is:

% CL-USER> (defun flatten (list)
%            (apply #'append
%                   (mapcar (lambda (item)
%                             (cond ((consp item) (flatten item))
%                                   (t (list item))))
%                           list)))
% FLATTEN
% CL-USER> (flatten '((1 2) nil 3 4 (5 6 (7 8)  9 10)))
% (1 2 NIL 3 4 5 6 7 8 9 10)
% CL-USER>

Arguably, using recursion is, however, just a way of using 'hidden'
intermediate variables, so this may not be 100% satisfactory either.

From: Kaz Kylheku
Subject: Re: flattening a nested list functionally
Date: Wed, 27 Dec 2006 18:08:48 +0000
Message-ID: <1167242928.898358.286810@a3g2000cwd.googlegroups.com>

Giorgos Keramidas wrote:
> Arguably, using recursion is, however, just a way of using 'hidden'
> intermediate variables, so this may not be 100% satisfactory either.

In that case, using a Von Neumann machine is also a way of using hidden
variables.