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/
John Thingstad wrote:
> Wrote this function to flatten a nested list.
[...]
> 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?
Use an accumulator and foldl.
(defun rev-flatten (list acc)
(if (atom list)
(cons list acc)
(reduce (lambda (acc item)
(flatten item acc))
list :initial-value acc)))
CL-USER> (rev-flatten '(1 (2 3) (4 (5) 6 7) 8 (((9)))) nil)
(9 8 7 6 5 4 3 2 1)
Or, if you really don't like variables, you can try something like
(defconstant <> '<>)
(defun cut (function &rest args)
(lambda (&rest values)
(apply function (append (loop for arg in args
collect (if (eq arg <>)
(pop values)
arg))
values))))
(defun select (pred then &optional (else (constantly nil)))
(lambda (x &rest args)
(apply (if (funcall pred x)
then
else)
x args)))
(defun flip (fn)
(lambda (x y)
(funcall fn y x)))
(defun rev-flatten (list acc)
(funcall (select #'atom
#'cons
(cut #'reduce (flip #'rev-flatten) <> :initial-value
<>))
list acc))
If you like the latter, you might want to consider consulting a
professional or using Haskell.
Paul Khuong
·······@gmail.com wrote:
> John Thingstad wrote:
> > Wrote this function to flatten a nested list.
> [...]
> > 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?
>
> Use an accumulator and foldl.
>
> (defun rev-flatten (list acc)
> (if (atom list)
> (cons list acc)
> (reduce (lambda (acc item)
> (flatten item acc))
> list :initial-value acc)))
>
> CL-USER> (rev-flatten '(1 (2 3) (4 (5) 6 7) 8 (((9)))) nil)
> (9 8 7 6 5 4 3 2 1)
..I should have thought a bit more. There's also `use foldr and get the
re-reversal for free' :)
(defun flatten (list acc)
(if (not (listp list)) ;; also fixes the problem of () being treated
as a leaf
(cons list acc)
(reduce (lambda (item acc)
(flatten item acc))
list :initial-value acc :from-end t)))
CL-USER> (flatten '(1 (2 3) (4 (5) 6 7) 8 (((9)))) nil)
(1 2 3 4 5 6 7 8 9)
CL-USER> (flatten nil nil)
NIL
Paul Khuong
On Thu, 07 Dec 2006 03:20:42 +0100, Madhu <·······@meer.net> wrote:
> Or consider a non-recursive [clockwork orange style] antidote...
>
> (defun flatten (x &aux stack result)
> (flet ((rec (item)
> (if (atom item)
> (push item result)
> (loop for elem in item do (push elem stack)))))
> (declare (inline rec))
> (loop initialy (rec x)
> while stack do (rec (pop stack)))
> finally (return result)))
Nice! However it is not functional.
&aux is just another form of let (deprecated) and you are modifying the
vars.
Fairly fast though..
After correcting a few errors/warnings..
(defun flatten (x &aux stack result)
(flet ((rec (item)
(if (atom item)
(push item result)
(loop for elem in item do (push elem stack)))))
(declare (inline rec))
(loop initially (rec x)
while stack do (rec (pop stack))
finally return result))))
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
John Thingstad wrote:
> 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)
(cond
((null list) nil)
((atom list) (list list))
(t (reduce #'append (mapcar #'flatten list)))))
Note 1: () and NIL are treated as structure rather than atoms and so
disappear in the flattening.
Note 2: A lone atom is flattened into a list by being wrapped in one.
In other words, the semantics is to hunt down all of the atoms in the
argument structure and return a list of them.
Kaz Kylheku wrote:
> Note 1: () and NIL are treated as structure rather than atoms and so
> disappear in the flattening.
Of course, since these are the same object, I meant to say ``is
treated''. :)
On Wed, 06 Dec 2006 15:38:33 +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?
>
OK first sucessfull try..
(defparameter *test-list* '((1 2 3) (4 5 6 (7 8 9)) 10))
(defun flatten (element)
(cond
((null element) nil)
((atom element) element)
((atom (first element))
(cons (first element) (flatten (rest element))))
((consp (first element))
(append (flatten (first element)) (flatten (rest element))))))
Looks very inefficient though.
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
"John Thingstad" <··············@chello.no> writes:
> On Wed, 06 Dec 2006 15:38:33 +0100, John Thingstad
> <··············@chello.no> wrote:
>
>> Wrote this function to flatten a nested list.
>>
>> [...]
>>
>> 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?
>
> OK first sucessfull try..
>
> (defparameter *test-list* '((1 2 3) (4 5 6 (7 8 9)) 10))
>
> (defun flatten (element)
> (cond
> ((null element) nil)
> ((atom element) element)
> ((atom (first element))
> (cons (first element) (flatten (rest element))))
> ((consp (first element))
> (append (flatten (first element)) (flatten (rest element))))))
>
> Looks very inefficient though.
The standard way to write efficient functional code is to pass around
an accumulator variable.
(defun flatten* (item acc)
(cond ((null item)
acc)
((atom item)
(cons item acc))
(t
(flatten* (cdr item) (flatten* (car item) acc)))))
(defun flatten (list) (reverse (flatten* list nil)))
On Wed, 06 Dec 2006 22:22:09 +0100, Dan Schmidt <····@dfan.org> wrote:
>
> The standard way to write efficient functional code is to pass around
> an accumulator variable.
>
> (defun flatten* (item acc)
> (cond ((null item)
> acc)
> ((atom item)
> (cons item acc))
> (t
> (flatten* (cdr item) (flatten* (car item) acc)))))
>
> (defun flatten (list) (reverse (flatten* list nil)))
Looks about like what I came up with..
(defun flatten-reverse (item &optional (acc nil))
(declare (optimize (debug 2) (speed 3)))
(cond ((null item)
acc)
((atom item)
(cons item acc))
(t
(flatten-reverse (rest item) (flatten-reverse (first item)
acc)))))
(defun flatten (list) (nreverse (flatten-reverse list)))
A couple of points:
1. the optional get's rid of the need for a nil argument.
nice if you want to use both functions
2. the declare makes sure tail optimation get's done on systems that
support it
3. I feel nreverse is ok here since we have already copied original list
and it's faster
4. I use first and rest.. (car and cdr are a bit dated)
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
On Wed, 06 Dec 2006 15:38:33 +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?
>
OK first sucessfull try..
(defparameter *test-list* '((1 2 3) (4 5 6 (7 8 9)) 10))
(defun flatten (element)
(cond
((null element) nil)
((atom element) element)
((atom (first element))
(cons (first element) (flatten (rest element))))
((consp (first element))
(append (flatten (first element)) (flatten (rest element))))))
Looks very inefficient though.
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
John Thingstad wrote:
> Wrote this function to flatten a nested list.
>
> [elided]
>
> 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?
Norvig's "Paradigms of Artificial Intelligence Programming" addresses
this, in the chapter on efficiency:
He starts with a working but inefficient function:
(defun flatten (input)
"Return a flat list of the atoms in the input.
Ex. (flatten '((a) (b (c) d))) => (a b c d)."
(cond ((null input) nil)
((atom input) (list input))
(t (append (flatten (first input))
(flatten (rest input))))))
Then adds an accumulator, to produce a more efficient version:
(defun flatten (input &optional acc)
"Return a flat list of the atoms in the input.
Ex. (flatten '((a) (b (c) d))) => (a b c d)."
(cond ((null input) acc)
((atom input) (cons input acc))
(t (flatten (first input)
(flatten (rest input) acc)))))
But while the use of the accumulator reduces the amount of consing, I'm
not sure if that violates your "adding a variable" constraint.
Either way, it's worth reading that section of PAIP.