I needed to flatten a (somewhat) arbitrary list, and failing to find
a builtin cl:flatten, I came up with, in "spring to mind fasion":
(defun walk (list fn)
(dolist (e list)
(if (listp e)
(walk e fn)
(funcall fn e))))
(defun flatten (list)
(let ((r nil))
(walk list (lambda(x) (push x r)))
(nreverse r)))
and tested it:
(defstruct st s1 s2)
(defparameter *values* '((a 3) (+ "hello") (nil) (3.14s0 2.718d0) #1a(2
3 4) #S(st :s1 nil :s2 nil)))
CL-USER> (format t "~a~%" (flatten *values*))
(a 3 + hello 3.1399994S0 2.718D0 #(2 3 4) #S(st :s1 nil :s2 nil))
But then, I thought that surely that must be a standard everyone
writes, and indeed, Google returned:
(defun flatten (l)
(cond ((null l) ())
((atom l) (list l))
(t (append (flatten (car l))
(flatten (cdr l))))))
The question is this: is "my" version an indication that
I'm still too encumbered with procedural thinking?
On the upside, I can reuse "walk" as in:
CL-USER> (walk *values* (lambda(x) (format t "~a is of type ~a~%" x
(type-of x))))
a is of type symbol
3 is of type fixnum
+ is of type symbol
hello is of type simple-base-string
3.1399994S0 is of type short-float
2.718D0 is of type double-float
#(2 3 4) is of type (simple-vector 3)
#S(st :s1 nil :s2 nil) is of type st
on the downside, "my" flatten needs a final nreverse that
the "standard" version doesn't need.
Is there a clear winner? Is this just a matter of taste?
Any base case that my version ignores apart from (flatten 'a)
that fails in walk's dolist? (I'm happy with the runtime
catching this type of programming error)
Which version does a "true Lisper" find more idiomatic, and why?
Any other (simpler?) contender?
Many thanks
--
JFB
verec <·····@mac.com> writes:
> ...I came up with...
>
> (defun walk (list fn)
> (dolist (e list)
> (if (listp e)
> (walk e fn)
> (funcall fn e))))
>
> (defun flatten (list)
> (let ((r nil))
> (walk list (lambda(x) (push x r)))
> (nreverse r)))
<snip>
> But then, I thought that surely that must be a standard everyone
> writes, and indeed, Google returned:
>
> (defun flatten (l)
> (cond ((null l) ())
> ((atom l) (list l))
> (t (append (flatten (car l))
> (flatten (cdr l))))))
>
<snip>
> Any base case that my version ignores apart from (flatten 'a) that
> fails in walk's dolist? (I'm happy with the runtime catching this
> type of programming error)
Because you don't handle the case where the argument to FLATTEN is an
atom, your version can't handle dotted lists:
CL-USER> (flatten '(a . b))
The value B is not of type LIST.
[Condition of type TYPE-ERROR]
The other implementation will handle dotted lists, but not circular
ones.
Also, neither version handles circular lists:
CL-USER> (walk '#1=(a (b c #1#)) #'print)
A
B
C
A
B
C
A
B
C
A
B
C
.
.
.
Of course since you're making up the problem you're permitted to
stipulate that dotted and circular lists aren't in the problem domain.
--
RmK
> But then, I thought that surely that must be a standard everyone
> writes, and indeed, Google returned:
>
> (defun flatten (l)
> (cond ((null l) ())
> ((atom l) (list l))
> (t (append (flatten (car l))
> (flatten (cdr l))))))
Super. Just super. No wonder Lisp is slow and, thx to Google, getting
slower. Where are all the clowns who laughed when I said a Lisper had to
understand consing? Hiding? I understand.
kt
--
http://www.theoryyalgebra.com/
"We are what we pretend to be." -Kurt Vonnegut
On 2007-10-10 05:49:12 +0100, Ken Tilton <···········@optonline.net> said:
>> But then, I thought that surely that must be a standard everyone
>> writes, and indeed, Google returned:
>>
>> (defun flatten (l)
>> (cond ((null l) ())
>> ((atom l) (list l))
>> (t (append (flatten (car l))
>> (flatten (cdr l))))))
>
> Super. Just super. No wonder Lisp is slow and, thx to Google, getting
> slower. Where are all the clowns who laughed when I said a Lisper had
> to understand consing? Hiding? I understand.
Whether slow or not, that's probably beside the point. And I
wouldn't want to waste a single brain cell to "optimize" unless
this very function turned out to be one of the major bottlenecks.
After profiling, of course :-)
Who said: "Lispers know the value of everything but the cost of nothing" ?
:-)
In any case, thank you Google, again %=>
--
JFB
verec wrote:
> On 2007-10-10 05:49:12 +0100, Ken Tilton <···········@optonline.net> said:
>
>>> But then, I thought that surely that must be a standard everyone
>>> writes, and indeed, Google returned:
>>>
>>> (defun flatten (l)
>>> (cond ((null l) ())
>>> ((atom l) (list l))
>>> (t (append (flatten (car l))
>>> (flatten (cdr l))))))
>>
>>
>> Super. Just super. No wonder Lisp is slow and, thx to Google, getting
>> slower. Where are all the clowns who laughed when I said a Lisper had
>> to understand consing? Hiding? I understand.
>
>
> Whether slow or not, that's probably beside the point.
No, that is precisely the point. If one understands the consing, one
would never write that. If one does not, one will write that.
Everywhere. All over the application. Including -- and here is the
problem you miss because you do not write enough Lisp -- someplace that
turns out to get called a kajillion times.
You /only/ think this is about a trivial optimization.
kenny
--
http://www.theoryyalgebra.com/
"Mother always told me, if you tell a lie,
always rehearse it. If it don't sound good
to you, it won't sound good to no one else."
- Satchel Paige
Ken Tilton wrote:
>
>
> verec wrote:
>> On 2007-10-10 05:49:12 +0100, Ken Tilton <···········@optonline.net>
>> said:
>>
>>>> But then, I thought that surely that must be a standard everyone
>>>> writes, and indeed, Google returned:
>>>>
>>>> (defun flatten (l)
>>>> (cond ((null l) ())
>>>> ((atom l) (list l))
>>>> (t (append (flatten (car l))
>>>> (flatten (cdr l))))))
>>>
>>>
>>> Super. Just super. No wonder Lisp is slow and, thx to Google, getting
>>> slower. Where are all the clowns who laughed when I said a Lisper had
>>> to understand consing? Hiding? I understand.
>>
>>
>> Whether slow or not, that's probably beside the point.
>
> No, that is precisely the point. If one understands the consing, one
> would never write that. If one does not, one will write that.
> Everywhere. All over the application. Including -- and here is the
> problem you miss because you do not write enough Lisp -- someplace that
> turns out to get called a kajillion times.
>
> You /only/ think this is about a trivial optimization.
>
> kenny
>
besides, that's bound to be one of these utility function to be used
again and again. A bit of polish can't hurt.
Sacha
Sacha wrote:
> Ken Tilton wrote:
>
>>
>>
>> verec wrote:
>>
>>> On 2007-10-10 05:49:12 +0100, Ken Tilton <···········@optonline.net>
>>> said:
>>>
>>>>> But then, I thought that surely that must be a standard everyone
>>>>> writes, and indeed, Google returned:
>>>>>
>>>>> (defun flatten (l)
>>>>> (cond ((null l) ())
>>>>> ((atom l) (list l))
>>>>> (t (append (flatten (car l))
>>>>> (flatten (cdr l))))))
>>>>
>>>>
>>>>
>>>> Super. Just super. No wonder Lisp is slow and, thx to Google,
>>>> getting slower. Where are all the clowns who laughed when I said a
>>>> Lisper had to understand consing? Hiding? I understand.
>>>
>>>
>>>
>>> Whether slow or not, that's probably beside the point.
>>
>>
>> No, that is precisely the point. If one understands the consing, one
>> would never write that. If one does not, one will write that.
>> Everywhere. All over the application. Including -- and here is the
>> problem you miss because you do not write enough Lisp -- someplace
>> that turns out to get called a kajillion times.
>>
>> You /only/ think this is about a trivial optimization.
>>
>> kenny
>>
>
> besides, that's bound to be one of these utility function to be used
> again and again. A bit of polish can't hurt.
Well, to me the problem is the great honking sign saying "I should not
be programming in Lisp". "Lisp is slow" comes from "Lisp makes it dead
easy to just hose a CPU if I do not know about list structure". If I do
know about list structure I use the right functions without a second
thought, using th other would be like flushing the toilet after brushing
your teeth. No, I have no idea what that means.
What I am trying to say is not that it is bad to use the inefficient
function unnecessarily, what is bad is not knowing Lisp.
hth, kenny
--
http://www.theoryyalgebra.com/
"Mother always told me, if you tell a lie,
always rehearse it. If it don't sound good
to you, it won't sound good to no one else."
- Satchel Paige
> Well, to me the problem is the great honking sign saying "I should not
> be programming in Lisp". "Lisp is slow" comes from "Lisp makes it dead
> easy to just hose a CPU if I do not know about list structure". If I do
> know about list structure I use the right functions without a second
> thought, using th other would be like flushing the toilet after brushing
> your teeth. No, I have no idea what that means.
>
> What I am trying to say is not that it is bad to use the inefficient
> function unnecessarily, what is bad is not knowing Lisp.
How fast is the fastest Lisp solution for flatten of list of n
lists with n elements that "Lisp expert" can manage? Is it
still O(n^2)?
Majorinc wrote:
>>Well, to me the problem is the great honking sign saying "I should not
>>be programming in Lisp". "Lisp is slow" comes from "Lisp makes it dead
>>easy to just hose a CPU if I do not know about list structure". If I do
>>know about list structure I use the right functions without a second
>>thought, using th other would be like flushing the toilet after brushing
>>your teeth. No, I have no idea what that means.
>>
>>What I am trying to say is not that it is bad to use the inefficient
>>function unnecessarily, what is bad is not knowing Lisp.
>
>
> How fast is the fastest Lisp solution for flatten of list of n
> lists with n elements that "Lisp expert" can manage? Is it
> still O(n^2)?
Is that infix? That looks like infix. Kenny does not do infix.
Left as an exercise is the destructive version that does not cons at
all. Due Monday. The neat thing is by the time you get it working you
will have earned your consing wings.
I hope that answers your question.
kenny
--
http://www.theoryyalgebra.com/
"Mother always told me, if you tell a lie,
always rehearse it. If it don't sound good
to you, it won't sound good to no one else."
- Satchel Paige
In article <···················@newsfe12.lga>,
···········@optonline.net says...
>
>
> Majorinc wrote:
> >>Well, to me the problem is the great honking sign saying "I should not
> >>be programming in Lisp". "Lisp is slow" comes from "Lisp makes it dead
> >>easy to just hose a CPU if I do not know about list structure". If I do
> >>know about list structure I use the right functions without a second
> >>thought, using th other would be like flushing the toilet after brushing
> >>your teeth. No, I have no idea what that means.
> >>
> >>What I am trying to say is not that it is bad to use the inefficient
> >>function unnecessarily, what is bad is not knowing Lisp.
> >
> >
> > How fast is the fastest Lisp solution for flatten of list of n
> > lists with n elements that "Lisp expert" can manage? Is it
> > still O(n^2)?
>
> Is that infix? That looks like infix. Kenny does not do infix.
>
> Left as an exercise is the destructive version that does not cons at
> all. Due Monday. The neat thing is by the time you get it working you
> will have earned your consing wings.
Actually, it is not _only_ about consing, but generally about
running time. What's the fastest flatten of n x n list one can
do in Lisp? Is it O(n^2)?
The point is, one can be grandmaster in consing, but it is
still slow. Am I right?
Majorinc wrote:
> In article <···················@newsfe12.lga>,
> ···········@optonline.net says...
>
>>
>>Majorinc wrote:
>>
>>>>Well, to me the problem is the great honking sign saying "I should not
>>>>be programming in Lisp". "Lisp is slow" comes from "Lisp makes it dead
>>>>easy to just hose a CPU if I do not know about list structure". If I do
>>>>know about list structure I use the right functions without a second
>>>>thought, using th other would be like flushing the toilet after brushing
>>>>your teeth. No, I have no idea what that means.
>>>>
>>>>What I am trying to say is not that it is bad to use the inefficient
>>>>function unnecessarily, what is bad is not knowing Lisp.
>>>
>>>
>>>How fast is the fastest Lisp solution for flatten of list of n
>>>lists with n elements that "Lisp expert" can manage? Is it
>>>still O(n^2)?
>>
>>Is that infix? That looks like infix. Kenny does not do infix.
>>
>>Left as an exercise is the destructive version that does not cons at
>>all. Due Monday. The neat thing is by the time you get it working you
>>will have earned your consing wings.
>
>
>
> Actually, it is not _only_ about consing, but generally about
> running time. What's the fastest flatten of n x n list one can
> do in Lisp? Is it O(n^2)?
>
> The point is, one can be grandmaster in consing, but it is
> still slow. Am I right?
>
No, consing is fast. You are wrong.
hth, kenny
--
http://www.theoryyalgebra.com/
"Mother always told me, if you tell a lie,
always rehearse it. If it don't sound good
to you, it won't sound good to no one else."
- Satchel Paige
Majorinc wrote:
> Actually, it is not _only_ about consing, but generally about
> running time. What's the fastest flatten of n x n list one can
> do in Lisp? Is it O(n^2)?
Unless I've confused myself with the notation, the fastest one can
traverse a singly-linked list of length n in *any* language is O(n),
so any operation that involves traversing a list of lists is going to
have O(n*n) as a lower bound, yes.
> The point is, one can be grandmaster in consing, but it is
> still slow. Am I right?
The point is, use a more appropriate data structure if this is going to
be an issue. It sounds like you want an array, not a list.
-dan
···@telent.net wrote:
> Majorinc wrote:
>> Actually, it is not _only_ about consing, but generally about running
>> time. What's the fastest flatten of n x n list one can do in Lisp? Is
>> it O(n^2)?
>
> Unless I've confused myself with the notation, the fastest one can
> traverse a singly-linked list of length n in *any* language is O(n),
> so any operation that involves traversing a list of lists is going to
> have O(n*n) as a lower bound, yes.
>
Traversing a list of lists is not O(n^2), unless you find a very very
bad way of doing it ... I'd say a simple recursive traversal would be
O(n), though you might want to take the nesting depth into account.
Sacha
Sacha wrote:
> ···@telent.net wrote:
>
>> Majorinc wrote:
>>
>>> Actually, it is not _only_ about consing, but generally about running
>>> time. What's the fastest flatten of n x n list one can do in Lisp? Is
>>> it O(n^2)?
>>
>>
>> Unless I've confused myself with the notation, the fastest one can
>> traverse a singly-linked list of length n in *any* language is O(n),
>> so any operation that involves traversing a list of lists is going to
>> have O(n*n) as a lower bound, yes.
>>
>
>
> Traversing a list of lists is not O(n^2), unless you find a very very
> bad way of doing it ... I'd say a simple recursive traversal would be
> O(n), though you might want to take the nesting depth into account.
Right. The confusion arises from using terminology associated with the
analysis of algorithms when describing a population. We get concerned
when the cost of an algorithm increases more than linearly with the
population of the data being processed, but we are not at all surprised
when the area of a square increases more than linearly with the length
of a side. Thus it is fine that the queen would have to make 36 more
moves to visit every square were a chessboard to grow two new columns
and rows, fine for the algorithm and fine for the chessboard to have 36
more squares. but majorinc may just have been confusing himself with
fancy terminology and trying to ask a more innocent question: is consing
slow? Sadly, slow as an absolute does not work so well. Lists are
certainly an insanely powerful data structure, hell, we named the
language after them, and the first slow to worry about is development
speed, so consing is the anithesis of slow unless the algorithm is
brought into view at which point some other data structure might be
faster for that algorithm. For some you'll be greenspunning lists and
come up short. But many a noob and veteran alike suffer from
consaphobia, and that might be majorinc's problem, in which case he
should get over it, write an application, and fix the slow bits if/when
they arise. as long as his list manipulation is not wasteful I guarantee
the slow bits will not be fixed by reducing consing.
kenxo
--
http://www.theoryyalgebra.com/
"Mother always told me, if you tell a lie,
always rehearse it. If it don't sound good
to you, it won't sound good to no one else."
- Satchel Paige
On Fri, 12 Oct 2007 06:31:41 -0400, Ken Tilton <···········@optonline.net> wrote:
> Sadly, slow as an absolute does not work so well. Lists are
> certainly an insanely powerful data structure, hell, we named the
> language after them, and the first slow to worry about is
> development speed, so consing is the anithesis of slow unless the
> algorithm is brought into view at which point some other data
> structure might be faster for that algorithm. For some you'll be
> greenspunning lists and come up short. But many a noob and veteran
> alike suffer from consaphobia, and that might be majorinc's problem,
> in which case he should get over it, write an application, and fix
> the slow bits if/when they arise. as long as his list manipulation
> is not wasteful I guarantee the slow bits will not be fixed by
> reducing consing.
Consaphobia. Wonderful, thanks. I'd like to nominate this one for
c.l.l article of the year.
Edi.
--
Lisp is not dead, it just smells funny.
Real email: (replace (subseq ·········@agharta.de" 5) "edi")
Edi Weitz wrote:
> On Fri, 12 Oct 2007 06:31:41 -0400, Ken Tilton <···········@optonline.net> wrote:
>
>
>>Sadly, slow as an absolute does not work so well. Lists are
>>certainly an insanely powerful data structure, hell, we named the
>>language after them, and the first slow to worry about is
>>development speed, so consing is the anithesis of slow unless the
>>algorithm is brought into view at which point some other data
>>structure might be faster for that algorithm. For some you'll be
>>greenspunning lists and come up short. But many a noob and veteran
>>alike suffer from consaphobia, and that might be majorinc's problem,
>>in which case he should get over it, write an application, and fix
>>the slow bits if/when they arise. as long as his list manipulation
>>is not wasteful I guarantee the slow bits will not be fixed by
>>reducing consing.
>
>
> Consaphobia. Wonderful, thanks. I'd like to nominate this one for
> c.l.l article of the year.
Thx, but I need a spellcheck: shouldn't that be consophobia?
kenny
--
http://www.theoryyalgebra.com/
"Mother always told me, if you tell a lie,
always rehearse it. If it don't sound good
to you, it won't sound good to no one else."
- Satchel Paige
On Fri, 12 Oct 2007 11:17:23 -0400, Ken Tilton <···········@optonline.net> wrote:
> Thx, but I need a spellcheck: shouldn't that be consophobia?
That was my initial reaction as well, but I convinced myself that
consaphobia also sounds nice. Also, Google says there's prior art for
consophobia (some yobbos on #scheme), so if you want to cash in on
this later, you better stick with a word you invented.
--
Lisp is not dead, it just smells funny.
Real email: (replace (subseq ·········@agharta.de" 5) "edi")
On 2007-10-10 05:49:12 +0100, Ken Tilton <···········@optonline.net> said:
>> But then, I thought that surely that must be a standard everyone
>> writes, and indeed, Google returned:
>>
>> (defun flatten (l)
>> (cond ((null l) ())
>> ((atom l) (list l))
>> (t (append (flatten (car l))
>> (flatten (cdr l))))))
>
> Super. Just super. No wonder Lisp is slow and, thx to Google, getting
> slower. Where are all the clowns who laughed when I said a Lisper had
> to understand consing? Hiding? I understand.
>
> kt
It occurs to me that this comment is not even accurate.
If you define flatten as a black box with any possible
implementation whatsoever, what we do know, from the outset,
is that the result willl have as many "cons cells" as there
are leaves in the input.
And since I wouldn't want to consider a destructive
version of flatten, those output cells have to be allocated
no matter what.
It turns out that the "Google" version does "consing"
on line 3 "(list l)" => 1 cons cell and line 4 "append"
=> 1 cons cell, ALL OF WHICH are retained in the final
output as "glue" between the leaves.
I would be really enlightened if someone were to point
out *any* garbage cons created by this version, where
by garbage, I really mean cons cells created during the
recursion but not otherwise part of the final output.
That said, other contributors have provided very nice
variants I'm still marvelling at, regardless of whether
they produce any garbage at all: a truly beautiful
piece of code always manages to hide its warts :-)
--
JFB
verec wrote:
> On 2007-10-10 05:49:12 +0100, Ken Tilton <···········@optonline.net> said:
>
>>> But then, I thought that surely that must be a standard everyone
>>> writes, and indeed, Google returned:
>>>
>>> (defun flatten (l)
>>> (cond ((null l) ())
>>> ((atom l) (list l))
>>> (t (append (flatten (car l))
>>> (flatten (cdr l))))))
>>
>>
>> Super. Just super. No wonder Lisp is slow and, thx to Google, getting
>> slower. Where are all the clowns who laughed when I said a Lisper had
>> to understand consing? Hiding? I understand.
>>
>> kt
>
>
> It occurs to me that this comment is not even accurate.
>
> If you define flatten as a black box with any possible
> implementation whatsoever, what we do know, from the outset,
> is that the result willl have as many "cons cells" as there
> are leaves in the input.
>
> And since I wouldn't want to consider a destructive
> version of flatten, those output cells have to be allocated
> no matter what.
>
> It turns out that the "Google" version does "consing"
> on line 3 "(list l)" => 1 cons cell and line 4 "append"
> => 1 cons cell, ALL OF WHICH are retained in the final
> output as "glue" between the leaves.
>
> I would be really enlightened if someone were to point
> out *any* garbage cons created by this version, where
> by garbage, I really mean cons cells created during the
> recursion but not otherwise part of the final output.
I will simply point out that your detailed analysis falls down where you
forgot to look up a lisp function it turns out you do not know which I
suppose is why you forgot to look it up, so to correct myself you forgot
you do not know Lisp but I enjoyed immensely being lectured by you on it
anyway, and offer a clue: one of the alternatives used mapcan for a
reason and, yes, you will need to look that up, too, or you will think
of a different and perfectly good but to this non-debate irrelevant reason.
kenny
--
http://www.theoryyalgebra.com/
"Mother always told me, if you tell a lie,
always rehearse it. If it don't sound good
to you, it won't sound good to no one else."
- Satchel Paige
On 2007-10-10 21:28:23 +0100, Ken Tilton <···········@optonline.net> said:
>
>
> verec wrote:
>> On 2007-10-10 05:49:12 +0100, Ken Tilton <···········@optonline.net> said:
>>
>>>> But then, I thought that surely that must be a standard everyone
>>>> writes, and indeed, Google returned:
>>>>
>>>> (defun flatten (l)
>>>> (cond ((null l) ())
>>>> ((atom l) (list l))
>>>> (t (append (flatten (car l))
>>>> (flatten (cdr l))))))
>>>
>>>
>>> Super. Just super. No wonder Lisp is slow and, thx to Google, getting
>>> slower. Where are all the clowns who laughed when I said a Lisper had
>>> to understand consing? Hiding? I understand.
>>>
>>> kt
>>
>>
>> It occurs to me that this comment is not even accurate.
>>
>> If you define flatten as a black box with any possible
>> implementation whatsoever, what we do know, from the outset,
>> is that the result willl have as many "cons cells" as there
>> are leaves in the input.
>>
>> And since I wouldn't want to consider a destructive
>> version of flatten, those output cells have to be allocated
>> no matter what.
>>
>> It turns out that the "Google" version does "consing"
>> on line 3 "(list l)" => 1 cons cell and line 4 "append"
>> => 1 cons cell, ALL OF WHICH are retained in the final
>> output as "glue" between the leaves.
>>
>> I would be really enlightened if someone were to point
>> out *any* garbage cons created by this version, where
>> by garbage, I really mean cons cells created during the
>> recursion but not otherwise part of the final output.
>
> I will simply point out that your detailed analysis falls down where
> you forgot to look up a lisp function it turns out you do not know
> which I suppose is why you forgot to look it up, so to correct myself
> you forgot you do not know Lisp but I enjoyed immensely being lectured
> by you on it anyway, and offer a clue: one of the alternatives used
> mapcan for a reason and, yes, you will need to look that up, too, or
> you will think of a different and perfectly good but to this non-debate
> irrelevant reason.
>
> kenny
Ah! Now we're getting somewhere :-)
I tried another contributor's version, here called flatten-2
(defun flatten-2 (thing)
(typecase thing
(list (mapcan #'flatten-2 thing))
(atom (list thing))))
that I constrasted with the "Google" version
(defun flatten-1 (l)
(cond ((null l) ())
((atom l) (list l))
(t (append (flatten-1 (car l))
(flatten-1 (cdr l))))))
and used time to get an approximate idea of the consing:
(defstruct st s1 s2)
(defparameter *values* '((a 3) (+ "hello") (nil) (3.14s0 2.718d0) #1a(2
3 4) #S(st :s1 nil :s2 nil)))
PREC 10 > (time (flatten-1 *values*))
Timing the evaluation of (flatten-1 *values*)
User time = 0.000
System time = 0.000
Elapsed time = 0.000
Allocation = 264 bytes
0 Page faults
(a 3 + "hello" 3.1399994S0 2.718D0 #(2 3 4) #S(st :s1 nil :s2 nil))
PREC 11 > (time (flatten-2 *values*))
Timing the evaluation of (flatten-2 *values*)
User time = 0.000
System time = 0.000
Elapsed time = 0.000
Allocation = 96 bytes
0 Page faults
(a 3 + "hello" 3.1399994S0 2.718D0 #(2 3 4) #S(st :s1 nil :s2 nil))
A ratio of nearly 1 to 3 is obviously nothing to sneer at.
> you forgot you do not know Lisp
Tss, tss, tss ....
I certainly can't forget that! I would argue that I don't
even know how to count! And I have a dead serious theory to back
it up. Some other day ... :)
> one of the alternatives used mapcan for a reason and, yes, you
> will need to look that up
Indeed. I'm now puzzling about those interstitial cons cells that
"nconc" skips, but "list" provides ...
Thanks for the enlightenment, Sir K
--
JFB
verec wrote:
> On 2007-10-10 21:28:23 +0100, Ken Tilton <···········@optonline.net> said:
>
>>
>>
>> verec wrote:
>>
>>> On 2007-10-10 05:49:12 +0100, Ken Tilton <···········@optonline.net>
>>> said:
>>>
>>>>> But then, I thought that surely that must be a standard everyone
>>>>> writes, and indeed, Google returned:
>>>>>
>>>>> (defun flatten (l)
>>>>> (cond ((null l) ())
>>>>> ((atom l) (list l))
>>>>> (t (append (flatten (car l))
>>>>> (flatten (cdr l))))))
>>>>
>>>>
>>>>
>>>> Super. Just super. No wonder Lisp is slow and, thx to Google,
>>>> getting slower. Where are all the clowns who laughed when I said a
>>>> Lisper had to understand consing? Hiding? I understand.
>>>>
>>>> kt
>>>
>>>
>>>
>>> It occurs to me that this comment is not even accurate.
>>>
>>> If you define flatten as a black box with any possible
>>> implementation whatsoever, what we do know, from the outset,
>>> is that the result willl have as many "cons cells" as there
>>> are leaves in the input.
>>>
>>> And since I wouldn't want to consider a destructive
>>> version of flatten, those output cells have to be allocated
>>> no matter what.
>>>
>>> It turns out that the "Google" version does "consing"
>>> on line 3 "(list l)" => 1 cons cell and line 4 "append"
>>> => 1 cons cell, ALL OF WHICH are retained in the final
>>> output as "glue" between the leaves.
>>>
>>> I would be really enlightened if someone were to point
>>> out *any* garbage cons created by this version, where
>>> by garbage, I really mean cons cells created during the
>>> recursion but not otherwise part of the final output.
>>
>>
>> I will simply point out that your detailed analysis falls down where
>> you forgot to look up a lisp function it turns out you do not know
>> which I suppose is why you forgot to look it up, so to correct myself
>> you forgot you do not know Lisp but I enjoyed immensely being lectured
>> by you on it anyway, and offer a clue: one of the alternatives used
>> mapcan for a reason and, yes, you will need to look that up, too, or
>> you will think of a different and perfectly good but to this
>> non-debate irrelevant reason.
>>
>> kenny
>
>
> Ah! Now we're getting somewhere :-)
>
> I tried another contributor's version, here called flatten-2
>
> (defun flatten-2 (thing)
> (typecase thing
> (list (mapcan #'flatten-2 thing))
> (atom (list thing))))
>
> that I constrasted with the "Google" version
>
> (defun flatten-1 (l)
> (cond ((null l) ())
> ((atom l) (list l))
> (t (append (flatten-1 (car l))
> (flatten-1 (cdr l))))))
>
> and used time to get an approximate idea of the consing:
>
> (defstruct st s1 s2)
> (defparameter *values* '((a 3) (+ "hello") (nil) (3.14s0 2.718d0) #1a(2
> 3 4) #S(st :s1 nil :s2 nil)))
>
> PREC 10 > (time (flatten-1 *values*))
> Timing the evaluation of (flatten-1 *values*)
>
> User time = 0.000
> System time = 0.000
> Elapsed time = 0.000
> Allocation = 264 bytes
> 0 Page faults
> (a 3 + "hello" 3.1399994S0 2.718D0 #(2 3 4) #S(st :s1 nil :s2 nil))
>
> PREC 11 > (time (flatten-2 *values*))
> Timing the evaluation of (flatten-2 *values*)
>
> User time = 0.000
> System time = 0.000
> Elapsed time = 0.000
> Allocation = 96 bytes
> 0 Page faults
> (a 3 + "hello" 3.1399994S0 2.718D0 #(2 3 4) #S(st :s1 nil :s2 nil))
>
> A ratio of nearly 1 to 3 is obviously nothing to sneer at.
>
>> you forgot you do not know Lisp
>
>
> Tss, tss, tss ....
>
> I certainly can't forget that! I would argue that I don't
> even know how to count! And I have a dead serious theory to back
> it up. Some other day ... :)
>
>> one of the alternatives used mapcan for a reason and, yes, you
>> will need to look that up
>
>
> Indeed. I'm now puzzling about those interstitial cons cells that
> "nconc" skips, but "list" provides ...
>
> Thanks for the enlightenment, Sir K
Ah, since you called me that, I'll help you.*
Append copies all but the last list, in flatten's case the first list of
the two. At each level on the way back up the tree. Oops. Again and
again, all the way up. Your tree was pretty shallow but you still see
the cost. flatten "owns" all the structure cuzza that (list thing), it
does not have to copy anything. NCONC is the non-copying APPEND, as
MAPCAN would be the non-copying MAPPEND if there was one -- I think PG
did one in On Lisp.
Himself
* Hoping this too gets cited seriously in a blog somewhere as evidence
of Lisper arrogance. SK
--
http://www.theoryyalgebra.com/
"Mother always told me, if you tell a lie,
always rehearse it. If it don't sound good
to you, it won't sound good to no one else."
- Satchel Paige
On 2007-10-10 22:23:34 +0100, Ken Tilton <···········@optonline.net> said:
>> Indeed. I'm now puzzling about those interstitial cons cells that
>> "nconc" skips, but "list" provides ...
>>
>> Thanks for the enlightenment, Sir K
>
> Ah, since you called me that, I'll help you.*
>
> Append copies all but the last list, in flatten's case the first list
> of the two. At each level on the way back up the tree. Oops. Again and
> again, all the way up. Your tree was pretty shallow but you still see
> the cost. flatten "owns" all the structure cuzza that (list thing), it
> does not have to copy anything. NCONC is the non-copying APPEND, as
> MAPCAN would be the non-copying MAPPEND if there was one -- I think PG
> did one in On Lisp.
So I ran a few more experiments (non allocation related parts
of time's output not shown). FWIW, this is with LispWorks PE 5.0.1
(Intel), OS X
(defun my-car (x)
(car x))
(defun my-cdr (x)
(cdr x))
(defun my-list (l)
(list l))
PREC 20 > (time (my-car *values*))
Allocation = 0 bytes
PREC 21 > (time (my-cdr *values*))
Allocation = 0 bytes
PREC 23 > (time (my-list 'a))
Allocation = 12 bytes
From which I can assume now that neither car nor cdr do
cons (as I dared to expect, but who knows? :-) and that
list does. I'm thus now inferring that a cons cell uses
up 12 bytes of storage,
So I figured that if, in flatten-1:
(defun flatten-1 (l)
(cond ((null l) ())
((atom l) (list l))
(t (append (flatten-1 (car l))
(flatten-1 (cdr l))))))
I was to replace the "list copying" append, with
the "list modifying nconc", as in:
(defun flatten-3 (l)
(cond ((null l) ())
((atom l) (list l))
(t (nconc (flatten-3 (car l))
(flatten-3 (cdr l))))))
Then I would get the same amount of used space, and indeed:
PREC 24 > (setq *x* '(this list has exactly ten leaves (plus or minus zero)))
PREC 30 > (time (flatten-2 *x*))
Allocation = 120 bytes
PREC 31 > (time (flatten-3 *x*))
Allocation = 120 bytes
both of which are consistent with the 12 bytes estimate for a single
cons cell.
What gets me puzzled, though, is this:
(defun test-2 ()
(append '(a) 'b))
(defun test-3 ()
(nconc '(a) 'b))
PREC 8 > (time (test-2))
Allocation = 12 bytes
PREC 9 > (time (test-3))
Allocation = 2228 bytes
Yep! 2 KB! What gives?
Bonus question: anything other than times to get a (preferably)
more accurate and/or detailed view of the memory usage?
Many thanks
--
JFB
verec wrote:
> On 2007-10-10 22:23:34 +0100, Ken Tilton <···········@optonline.net> said:
>
>>> Indeed. I'm now puzzling about those interstitial cons cells that
>>> "nconc" skips, but "list" provides ...
>>>
>>> Thanks for the enlightenment, Sir K
>>
>>
>> Ah, since you called me that, I'll help you.*
>>
>> Append copies all but the last list, in flatten's case the first list
>> of the two. At each level on the way back up the tree. Oops. Again and
>> again, all the way up. Your tree was pretty shallow but you still see
>> the cost. flatten "owns" all the structure cuzza that (list thing), it
>> does not have to copy anything. NCONC is the non-copying APPEND, as
>> MAPCAN would be the non-copying MAPPEND if there was one -- I think PG
>> did one in On Lisp.
>
>
> So I ran a few more experiments (non allocation related parts
> of time's output not shown). FWIW, this is with LispWorks PE 5.0.1
> (Intel), OS X
>
> (defun my-car (x)
> (car x))
>
> (defun my-cdr (x)
> (cdr x))
>
> (defun my-list (l)
> (list l))
>
> PREC 20 > (time (my-car *values*))
> Allocation = 0 bytes
>
> PREC 21 > (time (my-cdr *values*))
> Allocation = 0 bytes
>
> PREC 23 > (time (my-list 'a))
> Allocation = 12 bytes
>
> From which I can assume now that neither car nor cdr do
> cons (as I dared to expect, but who knows? :-)
Well, they are functions, aren't they? They just report back what they
found in the cons.
> and that
> list does. I'm thus now inferring that a cons cell uses
> up 12 bytes of storage,
>
> So I figured that if, in flatten-1:
>
> (defun flatten-1 (l)
> (cond ((null l) ())
> ((atom l) (list l))
> (t (append (flatten-1 (car l))
> (flatten-1 (cdr l))))))
>
> I was to replace the "list copying" append, with
> the "list modifying nconc", as in:
>
> (defun flatten-3 (l)
> (cond ((null l) ())
> ((atom l) (list l))
> (t (nconc (flatten-3 (car l))
> (flatten-3 (cdr l))))))
>
> Then I would get the same amount of used space, and indeed:
>
> PREC 24 > (setq *x* '(this list has exactly ten leaves (plus or minus
> zero)))
>
> PREC 30 > (time (flatten-2 *x*))
> Allocation = 120 bytes
>
> PREC 31 > (time (flatten-3 *x*))
> Allocation = 120 bytes
>
> both of which are consistent with the 12 bytes estimate for a single
> cons cell.
>
> What gets me puzzled, though, is this:
>
> (defun test-2 ()
> (append '(a) 'b))
>
> (defun test-3 ()
> (nconc '(a) 'b))
>
> PREC 8 > (time (test-2))
> Allocation = 12 bytes
>
> PREC 9 > (time (test-3))
> Allocation = 2228 bytes
>
> Yep! 2 KB! What gives?
That would be the RAM required to generate the demons you may have seen
flying out your nose, which the compiler is permitted to do given that
you operated destructively on the literal '(a). Moscow may also have
been destroyed, you should check CNN.
kt
--
http://www.theoryyalgebra.com/
"Mother always told me, if you tell a lie,
always rehearse it. If it don't sound good
to you, it won't sound good to no one else."
- Satchel Paige
On 2007-10-11 23:17:36 +0100, Ken Tilton <···········@optonline.net> said:
>> What gets me puzzled, though, is this:
>>
>> (defun test-2 ()
>> (append '(a) 'b))
>>
>> (defun test-3 ()
>> (nconc '(a) 'b))
>>
>> PREC 8 > (time (test-2))
>> Allocation = 12 bytes
>>
>> PREC 9 > (time (test-3))
>> Allocation = 2228 bytes
>>
>> Yep! 2 KB! What gives?
>
> That would be the RAM required to generate the demons you may have seen
> flying out your nose, which the compiler is permitted to do given that
> you operated destructively on the literal '(a). Moscow may also have
> been destroyed, you should check CNN.
:-(
--
JFB
verec <·····@mac.com> writes:
> What gets me puzzled, though, is this:
>
> (defun test-2 ()
> (append '(a) 'b))
>
> (defun test-3 ()
> (nconc '(a) 'b))
This is very, very bad. You are modifying a constant. This can cause
no end of mischief. Not only that, but you are also passing a non-list
as the last argument. That's also a BAD IDEA(tm).
You need either:
(defun test-3 ()
(nconc (list 'a) '(b))) ; The last argument isn't modified
(defun test-3 ()
(nconc (copy-list '(a)) '(b)))
You can't (safely) destructively modify quoted list structure. You need
to make sure you have freshly allocated list structure. The reason this
isn't a problem in the FLATTEN code is that you are applying NCONC to
fresh lists.
> PREC 8 > (time (test-2))
> Allocation = 12 bytes
>
> PREC 9 > (time (test-3))
> Allocation = 2228 bytes
>
> Yep! 2 KB! What gives?
"Undefined consequences" can be rather scary at times!
> Bonus question: anything other than times to get a (preferably)
> more accurate and/or detailed view of the memory usage?
Not in the standard.
--
Thomas A. Russ, USC/Information Sciences Institute
On Thu, 11 Oct 2007 22:03:05 +0100, verec <·····@mac.com> wrote:
>
>PREC 23 > (time (my-list 'a))
>Allocation = 12 bytes
>
>... I'm thus now inferring that a cons cell uses
>up 12 bytes of storage,
Possibly, if your implementation includes a header word on its cons
cells. The cell itself need only hold 2 pointers.
The symbol 'a needs memory too, which will be allocated on the first
use of the symbol. But a symbol takes more than 4 bytes (it is a
structure) so it does look like your cons cells are 3 words long.
George
--
for email reply remove "/" from address
On Oct 10, 5:06 pm, verec <·····@mac.com> wrote:
> PREC 10 > (time (flatten-1 *values*))
> Timing the evaluation of (flatten-1 *values*)
>
> User time = 0.000
> System time = 0.000
> Elapsed time = 0.000
> Allocation = 264 bytes
> 0 Page faults
> (a 3 + "hello" 3.1399994S0 2.718D0 #(2 3 4) #S(st :s1 nil :s2 nil))
>
> PREC 11 > (time (flatten-2 *values*))
> Timing the evaluation of (flatten-2 *values*)
>
> User time = 0.000
> System time = 0.000
> Elapsed time = 0.000
> Allocation = 96 bytes
> 0 Page faults
> (a 3 + "hello" 3.1399994S0 2.718D0 #(2 3 4) #S(st :s1 nil :s2 nil))
>
Which interpreter are you using? I just copied/pasted those blocks of
code into SBCL and I got 0 bytes cons'ed for both flatten-1 and
flatten-2.
-Rudolf
OMouse wrote:
> On Oct 10, 5:06 pm, verec <·····@mac.com> wrote:
>
>>PREC 10 > (time (flatten-1 *values*))
>>Timing the evaluation of (flatten-1 *values*)
>>
>>User time = 0.000
>>System time = 0.000
>>Elapsed time = 0.000
>>Allocation = 264 bytes
>>0 Page faults
>>(a 3 + "hello" 3.1399994S0 2.718D0 #(2 3 4) #S(st :s1 nil :s2 nil))
>>
>>PREC 11 > (time (flatten-2 *values*))
>>Timing the evaluation of (flatten-2 *values*)
>>
>>User time = 0.000
>>System time = 0.000
>>Elapsed time = 0.000
>>Allocation = 96 bytes
>>0 Page faults
>>(a 3 + "hello" 3.1399994S0 2.718D0 #(2 3 4) #S(st :s1 nil :s2 nil))
>>
>
>
> Which interpreter are you using? I just copied/pasted those blocks of
> code into SBCL and I got 0 bytes cons'ed for both flatten-1 and
> flatten-2.
What drug are you using?
It's not the bytes consed, it's the conses byted we're talking about. I
deepened things and lost the curious structure thing and just changed
append to nconc:
(defparameter *values* '((((((2 (st :s1 nil :s2 nil) 3 4) 3.14s0
2.718d0) nil) + "hello") a 3)))
; 13 cons cells, 0 other bytes, 0 static bytes
versus
; 72 cons cells, 0 other bytes, 0 static bytes
Both timings compiled with some hydro I picked up in Amsterdam.
Mind you, if Kenny can look at the code and see append is superfluous,
why cannot a compiler? But /zero/ conses? Your hydro beats my hydro.
hth, kenny
--
http://www.theoryyalgebra.com/
"Mother always told me, if you tell a lie,
always rehearse it. If it don't sound good
to you, it won't sound good to no one else."
- Satchel Paige
On Oct 10, 11:08 pm, Ken Tilton <···········@optonline.net> wrote:
> OMouse wrote:
> > On Oct 10, 5:06 pm, verec <·····@mac.com> wrote:
>
> >>PREC 10 > (time (flatten-1 *values*))
> >>Timing the evaluation of (flatten-1 *values*)
>
> >>User time = 0.000
> >>System time = 0.000
> >>Elapsed time = 0.000
> >>Allocation = 264 bytes
> >>0 Page faults
> >>(a 3 + "hello" 3.1399994S0 2.718D0 #(2 3 4) #S(st :s1 nil :s2 nil))
>
> >>PREC 11 > (time (flatten-2 *values*))
> >>Timing the evaluation of (flatten-2 *values*)
>
> >>User time = 0.000
> >>System time = 0.000
> >>Elapsed time = 0.000
> >>Allocation = 96 bytes
> >>0 Page faults
> >>(a 3 + "hello" 3.1399994S0 2.718D0 #(2 3 4) #S(st :s1 nil :s2 nil))
>
> > Which interpreter are you using? I just copied/pasted those blocks of
> > code into SBCL and I got 0 bytes cons'ed for both flatten-1 and
> > flatten-2.
>
> What drug are you using?
>
None!
Ok, I think I got it now.
The first time I tossed in (time (flatten-1 *values*)) it gives me:
Evaluation took:
0.0 seconds of real time
0.0 seconds of user run time
0.0 seconds of system run time
0 calls to %EVAL
0 page faults and
8,184 bytes consed.
The second time I execute that, it gives me:
Evaluation took:
0.0 seconds of real time
0.0 seconds of user run time
0.0 seconds of system run time
0 calls to %EVAL
0 page faults and
0 bytes consed.
I don't get why there's a difference. Enlighten me, please :D
On 11 Oct, 04:08, Ken Tilton <···········@optonline.net> wrote:
> Mind you, if Kenny can look at the code and see append is superfluous,
> why cannot a compiler? But /zero/ conses? Your hydro beats my hydro.
Because a compiler doesn't know what your up to.
So we start with this:
(defun flatten (l)
(cond ((null l) ())
((atom l) (list l))
(t (append (flatten (car l))
(flatten (cdr l))))))
The compiler transforms it into:
(defun flatten (l)
(cond ((null l) ())
((atom l) (list l))
(t (nconc (flatten (car l))
(flatten (cdr l))))))
we write:
(let ((f #'flattern))
(defun flatten (l)
(cond ((null l) ())
((atom l) (list l))
((every #'atom l) l)
(t (append (flatten (car l))
(flatten (cdr l))))))
(funcall f list))
And suddenly our code, made of side effect free functions, can have
side effects.
* Ken Tilton <···········@optonline.net> <················@newsfe12.lga> :
|> But then, I thought that surely that must be a standard everyone
|> writes, and indeed, Google returned:
|>
|> (defun flatten (l)
|> (cond ((null l) ())
|> ((atom l) (list l))
|> (t (append (flatten (car l))
|> (flatten (cdr l))))))
|
| Super. Just super. No wonder Lisp is slow and, thx to Google, getting
| slower. Where are all the clowns who laughed when I said a Lisper had
| to understand consing? Hiding? I understand.
Unfortunately I had marked as No-Archive the fast stacked version of
FLATTEN I had posted last year on <··············@robolove.meer.net>
I'd like to think this style is as idiomatic to any "True Lisper" as any
other :)
(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))
(rec x)
(loop while stack do (funcall #'rec (pop stack)))
result))
--
Madhu
Madhu <·······@meer.net> wrote:
+---------------
| * Ken Tilton <···········@optonline.net> <················@newsfe12.lga> :
| |> (defun flatten (l)
| |> (cond ((null l) ())
| |> ((atom l) (list l))
| |> (t (append (flatten (car l))
| |> (flatten (cdr l))))))
| |
| | Super. Just super. No wonder Lisp is slow and, thx to Google, getting
| | slower. Where are all the clowns who laughed when I said a Lisper had
| | to understand consing? Hiding? I understand.
|
| Unfortunately I had marked as No-Archive the fast stacked version of
| FLATTEN I had posted last year on <··············@robolove.meer.net>
|
| I'd like to think this style is as idiomatic to any "True Lisper" as any
| other :)
|
| (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))
| (rec x)
| (loop while stack do (funcall #'rec (pop stack)))
| result))
+---------------
The one inside CMUCL conses much less than yours [and AFAICT,
conses the minimal amount possible], but uses more control
stack and thus will blow up in some cases where yours won't.
From "cmucl-19c/src/compiler/srctran.lisp":
;;; Simple utility to flatten a list
(defun flatten-list (x)
(labels ((flatten-helper (x r);; 'r' is the stuff to the 'right'.
(cond ((null x) r)
((atom x)
(cons x r))
(t (flatten-helper (car x)
(flatten-helper (cdr x) r))))))
(flatten-helper x nil)))
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Ken Tilton <···········@optonline.net> writes:
>> But then, I thought that surely that must be a standard everyone
>> writes, and indeed, Google returned:
>>
>> (defun flatten (l)
>> (cond ((null l) ())
>> ((atom l) (list l))
>> (t (append (flatten (car l))
>> (flatten (cdr l))))))
>
> Super. Just super. No wonder Lisp is slow and, thx to Google, getting
> slower. Where are all the clowns who laughed when I said a Lisper had to
> understand consing? Hiding? I understand.
>
Wow, that response reminds me of that MS support joke - The information you
provided is 100% accurate and 100% useless (to the OP).
This is an all too frequent question and one of those that show how
potentially misleading google can be. (though I'm not convinced its as bad
as Kenny implies)However, I have to say that it is responses like this that
help to perpetuate the situation. I can understand that due to the
frequency of this question, frustration levels can rise and only those with
extremely superior social skills can avoid the overwhelming desire to say
"Nah nah na nah nah I told you so", but really, we are shooting ourselves
in the foot by not occasionally providing something that can actually help
those all to few posters who appear to be prepared to put in the work and
research to try and understand and are not expecting to be spoon fed
(noting that the OP did provide both his own attempt, an example of what he
was able to find on line and asked for comments regarding his solution -
this is someone that looks to be putting in the effort, not someone wanting
spoon feeding).
We all had to start somewhere and its easy to forget the effort it took or
possibly the time required to grasp less obvious issues associated with
learning a new language. If for no other reason than to provide possibly
more informative google hits, can we at least try to post useful pointers
that the OP could use to deepen their understanding?
from the reading and some comparison tests I've performed, my understanding
is that -
1. consing can be an expensive operation (there is debate concerning the
'expense' as newer implementations with better gc, compiler type hints
etc have reduced the cost compared to earlier implementations.
2. An often quoted lisp commandment is "Thou shalt not cons in vain", which
I think means to think about it rather than don't use it. I think this
is Kenny's point (rather than interpret it as don't use cons).
3. Often, alternative data types, such as structures or arrays, can be more
efficient than lists, partially because they can reduce the amount of
consing, so consider using them rather than just relying on lists.
4. As with most languages, it is often a trade-off between efficiency and
readability. As I still consider myself to be a novice, I find many
solutions that more experienced users would consider inefficient due to
perceived high levels of consing to be much more readable than solutions
which go to considerable lengths to avoid consing. There is a version of
flattern I've seen which uses labels that I found as readable as a more
naive approach based on append. Most of the introductory books I've seen
tend to use examples that would be considered inefficient by Kenny and
others. I suspect this is because it is more readable to those learning
the language.
5. As with all languages, focusing on efficiency to early is a mistake. I
think clarity and correctness are more important. worry about efficiency
once you know there is a performance problem. At the same time, as
you gain experience, get to understand what is happening 'under the
hood' and use this knowledge to guide your coding.
My suggestion for the OP is to try what I've been doing with bits and
pieces I've seen on this group. Try to get a few different implementations
of flatern that use different approaches (i.e. labels, loop, iteration,
tail-recursion etc) and examine them with a profiler. Look at what is going
on and work out why there are performance differences. If possible, also
make some comparisons with compiled and interpreted versions as this can
show what your compiler is capable of. If you find bits that don't make
sense or you can't explain, then come back to this group with specific
questions. Try to develop the fastest 'flattern' function you can - take
note of how readable it is (isn't) compared to other solutions.
Many of the available CL implementations also include 'utility' packages
that have functions that are not part of the hyperspec, but are often
used. Get the sources and look at their implementation of flattern. some
implementations have sections in their manual on writing efficient code and
optimising code, read these sections and incorporate some of their
suggestions into your evaluation.
this may seem like a fair bit of work and a fair amount of time, but I do
agree with part of the sentiment expressed by Ken, to write good lisp, you
need to understand what is going on 'under the hood' and consing is quite
fundamental to many operations (some which are not obvious at first
glance). It is always beneficial, particularly in a language with automatic
gc, to know what operations involve potentially expensive operations, such
as memory allocation and deallocation. It is also important to understand
destructive and non-destructive operations and shared data structures and
the subtle differences between things like '(1 2 3) and (list 1 2 3).
Tim
--
tcross (at) rapttech dot com dot au
Tim X wrote:
> Ken Tilton <···········@optonline.net> writes:
>
>
>>>But then, I thought that surely that must be a standard everyone
>>>writes, and indeed, Google returned:
>>>
>>>(defun flatten (l)
>>> (cond ((null l) ())
>>> ((atom l) (list l))
>>> (t (append (flatten (car l))
>>> (flatten (cdr l))))))
>>
>>Super. Just super. No wonder Lisp is slow and, thx to Google, getting
>>slower. Where are all the clowns who laughed when I said a Lisper had to
>>understand consing? Hiding? I understand.
>>
>
>
> Wow, that response reminds me...
...that most of you are so primed with kneejerk responses to what you
expect to read that you cannot read what you are reading? I was
excoriating a mob of you expert clowns who years ago derided my
insistence that a Lisp noob had best master the cons cell on day one,
not the noob. Yes, you /read/ me as abusing the noob, but that is all
about you, not what I wrote. Furthermore, while I see I have
successfully deluded you into thinking this is comp.lang.kenny, the fact
remains it is a public newsgroup to which anyone can respond, though we
do have a committee reviewing your particular permissions. Since the
original code was so embarrassingly bad I assumed dozens of
recommendations of nconc would be sailing in my port, so I was content
to settle that old score and point out that, yeah, noobs really do need
to learn about conses. The scary thing is that absolutely no Lisp savant
(or even post-noob) offered an explication of my implicit indictment of
the excess consing. Indeed, the answer surfaced only when another noob
decided to lecture me on the error of my ways. Maybe you are right,
maybe I was too hard on the mob of Lips gurus who mocked my counsel on
consing -- it would seem they themselves knew nothing on the subject.
Which brings me back to my point: no wonder Lisp is slow, no one knows
how to program it any more.
> of that MS support joke - The information you
> provided is 100% accurate and 100% useless (to the OP).
>
> This is an all too frequent question and one of those that show how
> potentially misleading google can be. (though I'm not convinced its as bad
> as Kenny implies)
Yeah, but it was Norvig, not Google. Google is this really cool search
engine, see, and... oh what's the use?
> However, I have to say that it is responses like this that
> help to perpetuate the situation. I can understand that due to the
> frequency of this question, frustration levels can rise and only those with
> extremely superior social skills can avoid the overwhelming desire to say
> "Nah nah na nah nah I told you so", but really, we are shooting ourselves
> in the foot by not occasionally providing something that can actually help
> those all to few posters who appear to be prepared to put in the work and
> research to try and understand and are not expecting to be spoon fed
> (noting that the OP did provide both his own attempt, an example of what he
> was able to find on line and asked for comments regarding his solution -
> this is someone that looks to be putting in the effort, not someone wanting
> spoon feeding).
Pay attention, please. I am trying to drive all these noobs out of here
so I can get some sleep and keep Lisp to myself. But apparently I
needn't worry, you cons-crazy know-nothings have found a better way to
discourage noobs. One of you actually told them never to use destructive
functions until they had learned Lisp. That has a nice oxymoronic
quality to those of us in on the joke. I tip my hat to your genius.
kenny
ps. The drama of verec rising to slay Kenny the Arrogant with his
lexical analysis of the appendages only to be crushed by the weight of
the CLHS provided a vastly more entertaining and memorable lesson on
consing to any noob reading than your earnest, well-intended, and thus
yawn-inducing 90-minute lecture. If you think the fun was accidental...
k
--
http://www.theoryyalgebra.com/
"Mother always told me, if you tell a lie,
always rehearse it. If it don't sound good
to you, it won't sound good to no one else."
- Satchel Paige
> Is there a clear winner? Is this just a matter of taste?
> Any base case that my version ignores apart from (flatten 'a)
> that fails in walk's dolist? (I'm happy with the runtime
> catching this type of programming error)
> Which version does a "true Lisper" find more idiomatic, and why?
> Any other (simpler?) contender?
Norvig's "Paradigms of Artificial Intelligence Programming" (a.k.a.
"PAIP") addresses exactly this question, in the chapter on efficiency.
He starts with the version you found:
(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, consing
much less:
(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)))))
It's worth getting PAIP and reading that section.
verec <·····@mac.com> writes:
> I needed to flatten a (somewhat) arbitrary list, and failing to find
> a builtin cl:flatten, I came up with, in "spring to mind fasion":
>
> (defun walk (list fn)
> (dolist (e list)
> (if (listp e)
> (walk e fn)
> (funcall fn e))))
>
> (defun flatten (list)
> (let ((r nil))
> (walk list (lambda(x) (push x r)))
> (nreverse r)))
>
> and tested it:
>
> (defstruct st s1 s2)
> (defparameter *values* '((a 3) (+ "hello") (nil) (3.14s0 2.718d0) #1a(2
> 3 4) #S(st :s1 nil :s2 nil)))
>
> CL-USER> (format t "~a~%" (flatten *values*))
> (a 3 + hello 3.1399994S0 2.718D0 #(2 3 4) #S(st :s1 nil :s2 nil))
>
> But then, I thought that surely that must be a standard everyone
> writes, and indeed, Google returned:
>
> (defun flatten (l)
> (cond ((null l) ())
> ((atom l) (list l))
> (t (append (flatten (car l))
> (flatten (cdr l))))))
>
> The question is this: is "my" version an indication that
> I'm still too encumbered with procedural thinking?
Yes, your version is over complicated and the style of the
complications is procedural. It could be much simpler:
(defun flatten (thing)
(typecase thing
(list (mapcan #'flatten thing))
(atom (list thing))))
> On the upside, I can reuse "walk" as in:
Walk is a perfectly good piece of code. It is the way it
talks to your flatten, using a variable passed in as the
environment of a closure, that is a flight of technique, fun
but obscure.
> Is there a clear winner? Is this just a matter of taste?
> Any base case that my version ignores apart from (flatten 'a)
> that fails in walk's dolist? (I'm happy with the runtime
> catching this type of programming error)
> Which version does a "true Lisper" find more idiomatic, and why?
> Any other (simpler?) contender?
I think that the version you got off the internet shows the
bad side of tradition. Let me try to make a fairly subtle
point.
The obvious general purpose data structure is the
nested-list.
nested-list = atom
or
nested-list = ( nested-list* )
meaning that a nested-list is either an atom or a list of
zero or more nested lists.
That is nice to program with, but a naive attempt to
implement it is going to run into trouble.
Common Lisp uses S-expressions
sexp = atom
or
sexp = ( sexp . sexp )
You can think of them as lists that have exactly two
items. If you want 0,1,3,4,... items you are out of
luck. Well, that's no good.
The interesting idea is to embed nested-list in sexp.
Data, an atom or a sublist, goes in the car of the cons,
while the cdr contains another cons containing the next item
in the top level list, or is unused (eg stuffed with a
filler value such as nil)
That works very nicely, but there is an interesting
twist, either magical or disasterous depending on your
application.
Think about defining A*, trees over some base set A.
A* = [] ;the empty tree
or
A* = [a] ; the singleton tree containing one item from A
or
A* = [x]++[y] ; two trees joined together.
Why isn't A* the same as sexp?
Think about (a . (b . c)) and ((x . y) . z), trees with three
leaves. If we do a substitution, of ((x . y) . z) in place of
b we get (a . (((x . y) . z) . c)) a tree with 5 leaves.
The corresponding substitution of ([x]++[y])++[z] for b in
[a]++([b]++[c]) gives
[a]++([([x]++[y])++[z]]++[c])
Don't be confused by the parentheses. They are there because
we are not saying that ++ is associative. We are not
regarding ([x]++[y])++[z] as the same as [x]++([y]++[z]) so
we cannot drop the parens.
The new tree still has 3 leaves, one of the leaves is itself
a tree, with three leaves of its own.
S-expression includes the underlying set as a subset.
Trees are disjoint from their underlying set.
So S-expressions give you a magical splicing property
(* 5 7) and (* (+ 2 3) 7) work how you want for source
code. There is no need to dig (+ 2 3) out of some container
type.
On the other hand it would be a disaster if the tree was
supposed to be a leaf of a different tree. So you need to
think about how trees get embedded in S-expressions. In
source code one uses quote to mark a conventional boundary
between the tree of code and its data leaves.
Return now to thinking about flatten. It is obvious enough
what flatten means for nested-lists. What about trees? I
guess it just means: make a list of leaves. But how are we
marking leaves? We have car, cdr, atom as the raw commands
for traversing S-expressions, but S-expressions are not
exactly trees. We might decide to allow cons as leaves using
(defstruct leaf data)
as a container, in which case we probably want flatten to
extract the leaves from the container. Punting on these
issues by using ATOM to detect leaves is a recipe for
confusion.
If one is working on nested-lists one should use the list
operations such as dolist, mapcar, and mapcan, and refrain
from using car, cdr, null.
Alan Crowe
Proclaiming from the cathedral of Saint Giles
Edinburgh
Scotland
P� Wed, 10 Oct 2007 18:15:52 +0200, skrev Alan Crowe
<····@cawtech.freeserve.co.uk>:
>
> Yes, your version is over complicated and the style of the
> complications is procedural. It could be much simpler:
>
> (defun flatten (thing)
> (typecase thing
> (list (mapcan #'flatten thing))
> (atom (list thing))))
>
>
> If one is working on nested-lists one should use the list
> operations such as dolist, mapcar, and mapcan, and refrain
> from using car, cdr, null.
As a sidenote I played around with ways of counting leaves
(defun count-leaves (list)
(loop for element in list summing
(if (listp element) (count-leaves element) 1)))
(defun count-leaves (element)
(typecase element
(list (reduce #'+ (mapcar #'count-leaves element)))
(atom 1)))
Here I clearly prefer the first as it is MUCH more efficient (and also
slightly terser).
It seems to me the old school map functions either need a closure for sum
or create temporary consing.
On a similar line
(defun flatten (list)
(loop for element in list nconc
(if (listp element) (flatten element) (list element))))
seems faster as it eliminates half of the recursive calls.