I am looking at CLHS, and I am having a hard time figuring out what list
processing functions would be suitable for me.
Suppose I have:
(defvar *list*
'((1 2)
(3 4)
(5 6)
(1 7)))
Now, suppose I want the "keys" of the list, defined by the first element
of the list. Is there a Lisp function which is callable something like:
(keys *list* :key #'first) ; => '(1 3 5)
Suppose further that I want to accumulate totals based on keys. The
first element in the list is the key, and the second element in the list
is the value. Is there a Lisp function which is callable something like:
(accum *list*) ; => '( (1 9) (3 4) (5 6) )
On 10 Nov., 11:11, Mark Carter <····@privacy.net> wrote:
> I am looking at CLHS, and I am having a hard time figuring out what list
> processing functions would be suitable for me.
>
> Suppose I have:
>
> (defvar *list*
> '((1 2)
> (3 4)
> (5 6)
> (1 7)))
>
> Now, suppose I want the "keys" of the list, defined by the first element
> of the list. Is there a Lisp function which is callable something like:
> (keys *list* :key #'first) ; => '(1 3 5)
see MAPCAR and REMOVE-DUPLICATES
>
> Suppose further that I want to accumulate totals based on keys. The
> first element in the list is the key, and the second element in the list
> is the value. Is there a Lisp function which is callable something like:
> (accum *list*) ; => '( (1 9) (3 4) (5 6) )
you have to write it...
Mark Carter <··@privacy.net> wrote:
+---------------
| Suppose I have: (defvar *list* '((1 2) (3 4) (5 6) (1 7)))
| Now, suppose I want the "keys" of the list, defined by the first element
| of the list. Is there a Lisp function which is callable something like:
| (keys *list* :key #'first) ; => '(1 3 5)
+---------------
Uh... What's wrong with just (MAPCAR #'FIRST *LIST*)?
[Oh, and your example output is wrong...]
+---------------
| Suppose further that I want to accumulate totals based on keys. The
| first element in the list is the key, and the second element in the list
| is the value. Is there a Lisp function which is callable something like:
| (accum *list*) ; => '( (1 9) (3 4) (5 6) )
+---------------
If the lists were really, *really* big, with lots of duplicate keys,
I'd probably use a hash table to store keys & sums. Otherwise I'd just
use a dumb, simple, N^2 cost insertion sum. You know, something like this:
> (defun accum-by-key (list)
(loop with result = nil
for (first second) in list
do (let ((found (find first result :key #'first)))
(if found
(incf (second found) second)
(push (list first second) result)))
finally (return (reverse result))))
ACCUM-BY-KEY
> (accum-by-key *list*)
((1 9) (3 4) (5 6))
>
-Rob
p.s. I would have used a WHEN (FIND...) (INCF (SECOND IT) SECOND) ELSE...
except that IT can *only* be used in RETURN or accumulation clauses
(COLLECT, SUM, etc.). (*sigh*)
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
····@rpw3.org (Rob Warnock) writes:
> Mark Carter <··@privacy.net> wrote:
> +---------------
> | Suppose I have: (defvar *list* '((1 2) (3 4) (5 6) (1 7)))
> | Now, suppose I want the "keys" of the list, defined by the first element
> | of the list. Is there a Lisp function which is callable something like:
> | (keys *list* :key #'first) ; => '(1 3 5)
> +---------------
>
> Uh... What's wrong with just (MAPCAR #'FIRST *LIST*)?
It does not remove the duplicates ... - but something like this might do
it:
(defun keys (list)
(remove-duplicates (sort (copy-seq (mapcar 'car list)) #'<)))
> [Oh, and your example output is wrong...]
True. It is
(1 3 5)
Cheers
Frank
--
Frank Goenninger
frgo(at)mac(dot)com
"Don't ask me! I haven't been reading comp.lang.lisp long enough to
really know ..."
Frank GOENNINGER <·············@nomail.org> wrote:
+---------------
| ····@rpw3.org (Rob Warnock) writes:
| > Mark Carter <··@privacy.net> wrote:
| > +---------------
| > | Suppose I have: (defvar *list* '((1 2) (3 4) (5 6) (1 7)))
| > | Now, suppose I want the "keys" of the list, defined by the first element
| > | of the list. Is there a Lisp function which is callable something like:
| > | (keys *list* :key #'first) ; => '(1 3 5)
| > +---------------
| >
| > Uh... What's wrong with just (MAPCAR #'FIRST *LIST*)?
|
| It does not remove the duplicates ... - but something like this
| might do it:
| (defun keys (list)
| (remove-duplicates (sort (copy-seq (mapcar 'car list)) #'<)))
+---------------
Yes, sorry. I didn't realize that I'd missed that portion of
the problem statement until I saw Rainer's parallel reply
(which also suggested MAPCAR and REMOVE-DUPLICATES).
+---------------
| > [Oh, and your example output is wrong...]
|
| True. It is
| (1 3 5)
+---------------
*Yowch!* Two zingers in one! [One to Mark, & one to me...] ;-}
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
On Nov 10, 6:01 am, ····@rpw3.org (Rob Warnock) wrote:
> Mark Carter <····@privacy.net> wrote:
>
> +---------------
> | Suppose I have: (defvar *list* '((1 2) (3 4) (5 6) (1 7)))
> | Now, suppose I want the "keys" of the list, defined by the first element
> | of the list. Is there a Lisp function which is callable something like:
> | (keys *list* :key #'first) ; => '(1 3 5)
> +---------------
>
> Uh... What's wrong with just (MAPCAR #'FIRST *LIST*)?
> [Oh, and your example output is wrong...]
>
> +---------------
> | Suppose further that I want to accumulate totals based on keys. The
> | first element in the list is the key, and the second element in the list
> | is the value. Is there a Lisp function which is callable something like:
> | (accum *list*) ; => '( (1 9) (3 4) (5 6) )
> +---------------
>
> If the lists were really, *really* big, with lots of duplicate keys,
> I'd probably use a hash table to store keys & sums. Otherwise I'd just
> use a dumb, simple, N^2 cost insertion sum. You know, something like this:
>
> > (defun accum-by-key (list)
> (loop with result = nil
> for (first second) in list
> do (let ((found (find first result :key #'first)))
> (if found
> (incf (second found) second)
> (push (list first second) result)))
> finally (return (reverse result))))
>
> ACCUM-BY-KEY
> > (accum-by-key *list*)
>
> ((1 9) (3 4) (5 6))
> >
>
> -Rob
>
The hash table idea seems simpler to me.
(defun accumulate-by-key (pairs)
(let ((hash (make-hash-table)))
(loop for (key value) in pairs
do (incf (gethash key hash 0) value))
(loop for key being the hash-keys of hash
using (hash-value value)
collect (list key value))))
Gene wrote:
> The hash table idea seems simpler to me.
Probably so, but remember that the list-based solutions preserve some
aspect of the original ordering of the source list, while
hash-table-based solutions do not. This might or might not matter,
depending on the application, but remember that ordering results might
be different on different implementations, or evenm on different
platforms of the same implementation, or even on different days of the
week on the same platform and the same implementation.
This might not matter, but think about providing a test suite for
portable code.
One of the things CL didn't get right, I think, was the notion of
mapping tables. The application programmer must choose between
linear-time solutions (e.g. lists and alists) and constant-time
solutions (hashing) in his code. Every implementation has some number
of entries at which the latter becomes more efficient than the former.
The programmer can, of course, code this dependency himself, but some
newer languages have abstracted this mapping concept, and it is
something which would have been a benefit for the application programmer.
X3J13 RIP.
On Nov 14, 9:28 pm, "Steven M. Haflich" <····@alum.mit.edu> wrote:
> Gene wrote:
> > The hash table idea seems simpler to me.
>
> Probably so, but remember that the list-based solutions preserve some
> aspect of the original ordering of the source list, while
> hash-table-based solutions do not. This might or might not matter,
> depending on the application, but remember that ordering results might
> be different on different implementations, or evenm on different
> platforms of the same implementation, or even on different days of the
> week on the same platform and the same implementation.
>
> This might not matter, but think about providing a test suite for
> portable code.
>
> One of the things CL didn't get right, I think, was the notion of
> mapping tables. The application programmer must choose between
> linear-time solutions (e.g. lists and alists) and constant-time
> solutions (hashing) in his code. Every implementation has some number
> of entries at which the latter becomes more efficient than the former.
> The programmer can, of course, code this dependency himself, but some
> newer languages have abstracted this mapping concept, and it is
> something which would have been a benefit for the application programmer.
>
> X3J13 RIP.
Sure. This is why other languages that don't have a general map or
table abstraction built into the language have adopted standard
container libraries. CL would be well-served by the same addition.
Mark Carter wrote:
> I am looking at CLHS, and I am having a hard time figuring out what list
> processing functions would be suitable for me.
>
> Suppose I have:
>
> (defvar *list*
> '((1 2)
> (3 4)
> (5 6)
> (1 7)))
>
>
> Now, suppose I want the "keys" of the list, defined by the first element
> of the list. Is there a Lisp function which is callable something like:
> (keys *list* :key #'first) ; => '(1 3 5)
>
> Suppose further that I want to accumulate totals based on keys. The
> first element in the list is the key, and the second element in the list
> is the value. Is there a Lisp function which is callable something like:
> (accum *list*) ; => '( (1 9) (3 4) (5 6) )
Are you looking for the association list functions like acons and
assoc?
On Nov 10, 4:11 am, Mark Carter <····@privacy.net> wrote:
> I am looking at CLHS, and I am having a hard time figuring out what list
> processing functions would be suitable for me.
>
> Suppose I have:
>
> (defvar *list*
> '((1 2)
> (3 4)
> (5 6)
> (1 7)))
>
> Now, suppose I want the "keys" of the list, defined by the first element
> of the list. Is there a Lisp function which is callable something like:
> (keys *list* :key #'first) ; => '(1 3 5)
>
> Suppose further that I want to accumulate totals based on keys. The
> first element in the list is the key, and the second element in the list
> is the value. Is there a Lisp function which is callable something like:
> (accum *list*) ; => '( (1 9) (3 4) (5 6) )
Ruby:
list = [1,2],[3,4],[5,6],[1,7]
p list.map{|k,v| k}.uniq
h = Hash.new(0)
list.each{|k,v| h[k] += v }
p h.sort
--- output ---
[1, 3, 5]
[[1, 9], [3, 4], [5, 6]]
On Nov 10, 2:11 am, Mark Carter <····@privacy.net> wrote:
> I am looking at CLHS, and I am having a hard time figuring out what list
> processing functions would be suitable for me.
>
> Suppose I have:
>
> (defvar *list*
> '((1 2)
> (3 4)
> (5 6)
> (1 7)))
>
> Now, suppose I want the "keys" of the list, defined by the first element
> of the list. Is there a Lisp function which is callable something like:
> (keys *list* :key #'first) ; => '(1 3 5)
>
> Suppose further that I want to accumulate totals based on keys. The
> first element in the list is the key, and the second element in the list
> is the value. Is there a Lisp function which is callable something like:
> (accum *list*) ; => '( (1 9) (3 4) (5 6) )
not a answer to your question, which others already did.
in case if you are in the stage of exploration, note that lisp is
actually the worst language for list processing, in comparison to
today's high-level languages such as perl, php, python, javascript,
mathematica.
extremely basic questions about varieties of list processing tasks
show up here monthly.
lisp's problem with list processing is due to its use of cons.
Technically, the lang does not support list as a primitive, only cons,
which is effectively a list with just limit of max of 2 items.
For more detail on this, see:
• Fundamental Problems of Lisp
http://xahlee.org/UnixResource_dir/writ/lisp_problems.html
on the section “The Cons Business”.
Here's a plain text excerpt:
The Cons Business
The above are some of the damages of irregularity in lisp's syntax.
The other fundamental problem in the language is its cons cells as its
list construction primitive.
Lisp at core is based on functional programing on lists. This is
comparatively a powerful paradigm. However, for historical reasons,
lisp's list is based on the hardware concept of “cons” cell. From a
mathematical point of view, what this means is that lisp's lists is
limited to a max of 2 elements. If you want a longer list, you must
nest it and interpret it in a special way. (i.e. effectively creating
a mini-protocol of nesting lists, known as proper lists.) The cons
fundamentally crippled the development of list processing.
Lisp being historically based the cons for like 2 or 3 decades. The
cons (and cdr, car, caadar etc) are fundamentally rooted in the lisp
langs, is thus not something that can be easily mended. This is
unfortunate. However, this situation could be improved. (by, for
example, exposing only higher-level list manipulation functions in all
newer literature, or even mark cons related functions as obsolete)
One of the myth that is quickly injected into budding lispers, is that
cons are powerful. It is powerful in the sense any assembly lang is
powerful. Lisp's cons is perhaps the greatest fuck up in the history
of computer languages.
The cons issue bugged me for 10 years, since i first tried to learn
scheme in ~1999. I've never worked with lisp (other than academic
reading) until in recent years with emacs lisp since 2005. Several
times i tried to explain to lispers this problem, but usually with
paragraphs and paragraphs of descriptions, analogies, examples,
frustrated by how hard it is to convey such a simple flaw (aided by
their blind, deep-seated, lisp fanaticism). Yesterday it hit on me.
The above mathematical aspect of lisp's cons is the first time i
formulated the cons problem concisely. (my previous verbose
explanation here: Lisp's List Problem )
Frequently Asked Questions
If you don't like cons, lisp has arrays and hashmaps, too.
Suppose there's a lang called gisp. In gisp, there's cons but also
fons. Fons are just like cons except it has 3 cells with car, cbr,
cdr. Now, gisp is a old lang, the fons are deeply rooted in the lang.
Every some 100 lines of code you'll see a use of fons and car, cbr,
cdr, or any one of the caar, cdar, cbbar, cdbbar, etc. You got annoyed
by this. You as a critic, complains that fons is bad. But then some
gisp fanatics retort by saying: “If you don't like fons, gisp has
cons, too.”.
You see, by “having something too”, does not solve the problem of
pollution. Sure, you can use just cons in gisp, but every lib or
other's code you encounter, there's a invasion of fons with its cbbar,
cdbbar, cbbbr. The problem created by fons cannot be solved by “having
cons too”.
I like the cons concept. Even in functional languages like Haskell it
is popular, e.g. when matching in the form of (x:xs), which is the
same like car/cdr in Lisp.
Languages that has a list data type and First, Rest functions do not
mean it has lisp's cons problem.
One part of the cons problem in lisp is that it forces programer to
think of list in a low-level nested of 2-item construction, with
explicit functions like “cons”, “car”, “cdr”, “caar”, “cadr”, “cdar”,
“cddr”, “caaar”, “caadr” etc.
In other langs, the programer is not forced to think of nested 2-
items.
The other problem with lisp's cons, is that it hinders any development
of tree data structure. For example, one might write a function that
extracts the leafs of a tree. But due to lisp's list made of cons,
there is a different interpretations of what's considered a leaf.
Similarly, binary tree in lisp can be implemented either using cons
natively, or use so-called “proper list” that is implemented on top of
cons. Worse, any proper list can be mixed with improper list. So, you
can have a list of cons, or cons of lists, cons of cons, list of
lists, or any mix. The overall effect of the cons is that it prevents
lisp to have a uniform view of tree structure, with the result that
development of functions that work on tree are inconsistent, few, or
otherwise hampered.
Further readings:
* Lisp's List Problem
* My First Encounter And Impression Of Lisp
* The Jargon “Lisp1” vs “Lisp2”
Why Lisp's Cons Problem Never Got Fixed?
Now, a little speculation.
We might wonder, why lisp has the cons problem and was never
addressed?
I guess at the time, 1960s and 1970s, the very fact that you could
have a concept like a list in a lang and manipulate it as a unit, is a
very advanced concept. The list, being built up by hardware cons, is
just something that is necessary for implementation for practical
considerations.
Having data as a single manipulatable object (list) didn't really
become popular until the 1990s. (notably due to Perl) And today, it is
THE most important feature of highlevel languages. (For example, among
langs i'm expert of: perl, python, php, javascript.).
The lisp's cons, as a underlying primitive that builds lists, even
though a bit cumbersome, but works just fine when list structure are
simple. Even today, with all the perl, python, php, javascript etc
langs that deal with lists, vast majority of list usage is just simple
flat list, sometimes 2 level of nesting (list of list, list of hash,
hash of list). 3 levels of nesting is seldom used unless its 3d
matrices used mostly in computer graphics or linear algebra
applications. Greater than 3 level is almost never seen. Systematic
manipulation and exploitation of nested list, such as mapping to
leafs, to particular level, transposition by permutation on level, or
list structure pattern matching in today's functional langs, etc is
hardly ever to be seen. (except in Mathematica, APL)
So, in general, when you just deal with simple lists, the
cumbersomeness in using cons, car, cdr, caardr etc for list doesn't
really surface. Further, the cons is fundamentally rooted in the
language. It's not something that can be easily changed except
creating a new language. When there is a specific need in a
application, there is a haphazard collection of functions that deal
with lists at a higher level.
Today, with list manipulation being mainstream, especially with the
uprising of many functional langs, the lisp's cons historical baggage
becomes more apparent and painful.
Summary:
* Lisp's list being cons as part of the language was necessary for
practical implementation in the early days.
* List as a unit in programing languages did not became popular
until 1990s.
* By then, the cons as a lang element is deeply rooted in lisp and
it is hard to change other then as a new lang.
* Most use of lists in programing tasks is just flat list. Nesting
of more than 3 levels is rarely used for typical programing tasks. So,
the problem of cons does not surface.
Xah
∑ http://xahlee.org/
☄
On Nov 10, 6:16 pm, ·······@gmail.com" <······@gmail.com> wrote:
>stuff
You clearly never took the time to learn lisp, and no one understands
your argument because you write in a terrible style.
1.) You don't even know how to block comment. ( #| comment comment
comment away |# )
2.) The dotted notation for a cons cell is hardly ever used.
In fact, in advanced lisp programs, lists are hardly used for data
either. Arrays and hash-tables are faster.
3.) The backquote/comma macro is an *extremely* powerful way of doing
complex substitutions.
Granted, you could do most of it with (quote ) and (list ), but
the entire point is syntactic sugar.
You will note that I make the distinction that it is a macro.
The backquote syntax expands to fully regular lisp code.
>Lisp at core is based on functional programing on lists. This is
>comparatively a powerful paradigm. However, for historical reasons,
>lisp's list is based on the hardware concept of “cons” cell. From a
>mathematical point of view, what this means is that lisp's lists is
>limited to a max of 2 elements. If you want a longer list, you must
>nest it and interpret it in a special way. (i.e. effectively creating
>a mini-protocol of nesting lists, known as proper lists.) The cons
>fundamentally crippled the development of list processing.
4.) No. You are incorrect. A cons is a data pair linked by a pointer.
Longer lists are constructed by adding a pointer from the last
element to the next element.
This is called a 'linked list'. While this is a theoretical
requirement,
you could just as easily implement lisp lists as vectors.
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-14.html#%_sec_2.1.3
I suggest you read this whole section on data abstraction. In
addition, i'd like to add that
most functions that are used to manipulate lists are also used
manipulate sequences (such as strings and vectors).
You seem to be making a mountain out of a molehill.
5.) Lisp is actually based on a tree structure, not a list structure.
XML is also a tree structure, and not a flat structure. (In fact,
the main difference between XML and lisp is that lisp is more flexible
and concise).
Associative databases use a tree structure.
Any marginally complex object-oriented program uses a tree
structure.
Nested conditionals are a tree structure.
Saying that the nth dimension nesting of lists is never used is
really admitting your own ignorance. It happens all the time,
it is just that the computer (and properly written code) abstracts
away the nesting part so that you don't have to look at it so
closely.
It seems that you are quite the prolific writer, and my suggestion to
you would be to read more and write less.
You have not yet taken the time to learn lisp.
On Mon, 10 Nov 2008 22:30:58 -0800 (PST), ················@gmail.com
wrote:
>On Nov 10, 6:16�pm, ·······@gmail.com" <······@gmail.com> wrote:
>>stuff
>
>You clearly never took the time to learn lisp, and no one understands
>your argument because you write in a terrible style.
Xah uses Emacs Lisp - not Common Lisp - and everything he thinks he
knows about Lisp is based on it. That he programs badly regardless is
a topic for another time.
George
did dear Jonathan Smith moron,
Jonathan Smith ···@gmail.com wrote:
> 1.) You don't even know how to block comment. ( #| comment comment
> comment away |# )
dear moron, that is not supported in lisp in general. For example, not
in elisp, and you can lookup specific examples where it is not
supported in scheme lisp.
dear moron, further, the specific point is about how the lisp's
comment “;” breaks its syntax regularity. Having a alternative form
does not change the fact.
> 2.) The dotted notation for a cons cell is hardly ever used.
> In fact, in advanced lisp programs, lists are hardly used for data
> either. Arrays and hash-tables are faster.
dear moron, if u are lisp newbie, better shut up.
> 3.) The backquote/comma macro is an *extremely* powerful way of doing
> complex substitutions.
> Granted, you could do most of it with (quote ) and (list ), but
> the entire point is syntactic sugar.
> You will note that I make the distinction that it is a macro.
> The backquote syntax expands to fully regular lisp code.
dear moron, the context is about syntax irregularity, not about
whether macro is powerful.
> 4.) No. You are incorrect. A cons is a data pair linked by a pointer.
dear moron, try to pickup basic mathematics to improve your
abstraction abilities.
> 5.) Lisp is actually based on a tree structure, not a list structure.
Moron, nested list are isomorphic to trees.
> It seems that you are quite the prolific writer, and my suggestion
> to you would be to read more and write less. You have not yet taken
> the time to learn lisp.
Moron, ur mom?
Xah
∑ http://xahlee.org/
☄
On Nov 12, 3:33 am, ·······@gmail.com" <······@gmail.com> wrote:
> did dear Jonathan Smith moron,
>
> Jonathan Smith ····@gmail.com wrote:
> > 1.) You don't even know how to block comment. ( #| comment comment
> > comment away |# )
>
> dear moron, that is not supported in lisp in general. For example, not
> in elisp, and you can lookup specific examples where it is not
> supported in scheme lisp.
>
> dear moron, further, the specific point is about how the lisp's
> comment “;” breaks its syntax regularity. Having a alternative form
> does not change the fact.
>
Who generalizes elisp or specific implementations of scheme to stand
in for all of lisp?
It is a ludicrous argument.
Comments are supposed to break syntax regularity. It makes them easier
to see.
> > 2.) The dotted notation for a cons cell is hardly ever used.
> > In fact, in advanced lisp programs, lists are hardly used for data
> > either. Arrays and hash-tables are faster.
>
> dear moron, if u are lisp newbie, better shut up.
I clearly spent more time learning than you did.
>
> > 3.) The backquote/comma macro is an *extremely* powerful way of doing
> > complex substitutions.
> > Granted, you could do most of it with (quote ) and (list ), but
> > the entire point is syntactic sugar.
> > You will note that I make the distinction that it is a macro.
> > The backquote syntax expands to fully regular lisp code.
>
> dear moron, the context is about syntax irregularity, not about
> whether macro is powerful.
>
The reader macro expands to regular syntax. That is the point...
You could (i suppose) rewrite them all to behave as you describe.
> > 4.) No. You are incorrect. A cons is a data pair linked by a pointer.
>
> dear moron, try to pickup basic mathematics to improve your
> abstraction abilities.
>
That's not much of a reply.
> > 5.) Lisp is actually based on a tree structure, not a list structure.
>
> Moron, nested list are isomorphic to trees.
>
Duh.
Again, not much of a reply.
> > It seems that you are quite the prolific writer, and my suggestion
> > to you would be to read more and write less. You have not yet taken
> > the time to learn lisp.
>
> Moron, ur mom?
>
> Xah
> ∑http://xahlee.org/
>
> ☄
I'm unimpressed.
·······@gmail.com" <······@gmail.com> wrote on Wed, 12 Nov 2008:
> Jonathan Smith ···@gmail.com wrote:
>> 1.) You don't even know how to block comment. ( #| comment comment
>> comment away |# )
>
> that is not supported in lisp in general.
There is no computer language that is "lisp in general". Lisp is a family
of related languages, not an actual concrete language.
In this newsgroup (comp.lang.lisp), as you've been told many times, the
default is to assume you are talking about the language Common Lisp unless
you explicitly specify otherwise. So the failure is yours, not Jonathan's.
> For example, not in elisp, and you can lookup specific examples where it is
> not supported in scheme lisp.
So what? There is no piece of concrete code that works in "lisp in general".
"Lisp in general" describes too wide a family of languages to allow _any_
piece of code to run across them all.
-- Don
_______________________________________________________________________________
Don Geddis http://don.geddis.org/ ···@geddis.org
Progressive (adj): Value-free; tolerant; non-judgemental.
For example, traditional archery instruction methods spent tedious hours
teaching the archer to hit a bulls-eye. Progressive methods achieved better
results by telling the student archer to shoot in the manner he or she found
most comfortable, then calling whatever the arrow hit the bulls-eye.
Mark Carter <··@privacy.net> writes:
> I am looking at CLHS, and I am having a hard time figuring out what
> list processing functions would be suitable for me.
>
> Suppose I have:
>
> (defvar *list*
> '((1 2)
> (3 4)
> (5 6)
> (1 7)))
>
>
> Now, suppose I want the "keys" of the list, defined by the first
> element of the list. Is there a Lisp function which is callable
> something like:
> (keys *list* :key #'first) ; => '(1 3 5)
>
> Suppose further that I want to accumulate totals based on keys. The
> first element in the list is the key, and the second element in the
> list is the value. Is there a Lisp function which is callable
> something like:
> (accum *list*) ; => '( (1 9) (3 4) (5 6) )
You need to read:
http://www-cgi.cs.cmu.edu/afs/cs.cmu.edu/user/dst/www/LispBook/index.html
http://www.cs.cmu.edu/~dst/LispBook/
Common Lisp: A Gentle Introduction to Symbolic Computation
David S. Touretzky
--
__Pascal Bourguignon__
On Nov 10, 5:11 am, Mark Carter <····@privacy.net> wrote:
> I am looking at CLHS, and I am having a hard time figuring out what list
> processing functions would be suitable for me.
>
> Suppose I have:
>
> (defvar *list*
> '((1 2)
> (3 4)
> (5 6)
> (1 7)))
>
> Now, suppose I want the "keys" of the list, defined by the first element
> of the list. Is there a Lisp function which is callable something like:
> (keys *list* :key #'first) ; => '(1 3 5)
>
> Suppose further that I want to accumulate totals based on keys. The
> first element in the list is the key, and the second element in the list
> is the value. Is there a Lisp function which is callable something like:
> (accum *list*) ; => '( (1 9) (3 4) (5 6) )
(defun accum-pairlist (list)
(let ((return-list nil))
(dolist (li list)
(if (assoc (first li) return-list)
(setf (second (assoc (first li) return-list))
(+
(second (assoc (first li) return-list))
(second li)))
(pushnew li return-list)))
return-list))
<················@gmail.com> wrote:
+---------------
| Mark Carter <····@privacy.net> wrote:
| > Suppose further that I want to accumulate totals based on keys. The
| > first element in the list is the key, and the second element in the list
| > is the value. Is there a Lisp function which is callable something like:
| > (accum *list*) ; => '( (1 9) (3 4) (5 6) )
|
| (defun accum-pairlist (list)
| (let ((return-list nil))
| (dolist (li list)
| (if (assoc (first li) return-list)
| (setf (second (assoc (first li) return-list))
| (+
| (second (assoc (first li) return-list))
| (second li)))
| (pushnew li return-list)))
| return-list))
+---------------
Careful!! Your solution has the same bug that my first
(and, thankfully, unpublished!) version I did -- it doesn't
give the same answer twice. [And *why* it behaves that way
is even *more* serious!!] E.g.:
> (defvar *list* '((1 2) (3 4) (5 6) (1 7)))
*LIST*
> (accum-pairlist *list*)
((5 6) (3 4) (1 9))
> (accum-pairlist *list*)
((5 6) (3 4) (1 16))
> (accum-pairlist *list*)
((5 6) (3 4) (1 23))
>
Hint: What's wrong with the following?
> *list*
((1 23) (3 4) (5 6) (1 7))
>
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
On Nov 11, 7:48 am, ····@rpw3.org (Rob Warnock) wrote:
> <················@gmail.com> wrote:
>
> +---------------
> | Mark Carter <····@privacy.net> wrote:
> | > Suppose further that I want to accumulate totals based on keys. The
> | > first element in the list is the key, and the second element in the list
> | > is the value. Is there a Lisp function which is callable something like:
> | > (accum *list*) ; => '( (1 9) (3 4) (5 6) )
> |
> | (defun accum-pairlist (list)
> | (let ((return-list nil))
> | (dolist (li list)
> | (if (assoc (first li) return-list)
> | (setf (second (assoc (first li) return-list))
> | (+
> | (second (assoc (first li) return-list))
> | (second li)))
> | (pushnew li return-list)))
> | return-list))
> +---------------
>
> Careful!! Your solution has the same bug that my first
> (and, thankfully, unpublished!) version I did -- it doesn't
> give the same answer twice. [And *why* it behaves that way
> is even *more* serious!!] E.g.:
>
> > (defvar *list* '((1 2) (3 4) (5 6) (1 7)))
>
> *LIST*
> > (accum-pairlist *list*)
>
> ((5 6) (3 4) (1 9))
> > (accum-pairlist *list*)
>
> ((5 6) (3 4) (1 16))
> > (accum-pairlist *list*)
>
> ((5 6) (3 4) (1 23))
> >
>
> Hint: What's wrong with the following?
>
> > *list*
>
> ((1 23) (3 4) (5 6) (1 7))
> >
>
> -Rob
>
> -----
> Rob Warnock <····@rpw3.org>
> 627 26th Avenue <URL:http://rpw3.org/>
> San Mateo, CA 94403 (650)572-2607
My mistake, I forgot the ever important copying part :)
This seems to behave better for me (than the other one I posted)?
(defun accum-pairlist (mylist)
(let ((return-list nil)
(list (copy-tree mylist)))
(dolist (li list)
(if (assoc (first li) return-list)
(setf (second (assoc (first li) return-list))
(+
(second (assoc (first li) return-list))
(second li)))
(pushnew li return-list)))
return-list))
//still a newbie
Rob Warnock wrote:
> <················@gmail.com> wrote:
> +---------------
> | Mark Carter <····@privacy.net> wrote:
> | > Suppose further that I want to accumulate totals based on keys. The
> | > first element in the list is the key, and the second element in the list
> | > is the value. Is there a Lisp function which is callable something like:
> | > (accum *list*) ; => '( (1 9) (3 4) (5 6) )
> |
> | (defun accum-pairlist (list)
> | (let ((return-list nil))
> | (dolist (li list)
> | (if (assoc (first li) return-list)
> | (setf (second (assoc (first li) return-list))
> | (+
> | (second (assoc (first li) return-list))
> | (second li)))
> | (pushnew li return-list)))
> | return-list))
> +---------------
>
> Careful!! Your solution has the same bug that my first
> (and, thankfully, unpublished!) version I did -- it doesn't
> give the same answer twice. [And *why* it behaves that way
> is even *more* serious!!]
When I see such mistakes (and I make them too), I can't help
mentioning how easy it is to do such things given a well
chosen set of higher order functions. For example in q:
q) f: {sum each x[;1] @ group x[;0]}
q) f (1 2;3 4;5 6;1 7)
1| 9
3| 4
5| 6
{..} is lambda, by default x names its first arg.
x[;0] selects column 0 of x: 1 3 5 1
x[;1] selects column 1 of x: 2 4 6 7
group x[;0] returns a dictionary, where keys are 1, 3, 5, and
corresponding values are *indices* where the keys occur in x[;1].
q) group 1 3 5 1
1| 0 3
3| ,1 // singleton lists are shown with a leading ,
5| ,2
x @ group y selects values from list x as per indices in y.
The result has the same shape as y. If y is a dictionary,
so is the result.
q) 2 4 6 7 @ group 1 3 5 1 // select indexed values
1| 2 7
3| ,4
5| ,6
f each x applies function f to each element of list x,
returning a list, or if x is a dictionary, f applies
f to each value, returning a dictionary.
q) sum each 2 4 6 7 @ group 1 3 5 1
1| 9
3| 4
5| 6
Now, I don't expect anyone to switch to q but some of its
ideas are worth expressing in lisp. each is basically an
extension of map to dictionaries. group uses the default
equality function for the list element type. Returning
indices instead of values is quite useful because they can
then be used for selecting elements from another list.
One reason I prefer such higher order functions is because
one easily see how similar patterns are useful in different
contexts (this gets lost in low level bitbanging code). As
an example the "list1 @ group list2" idiom in f can be used
to create an inverted file index. If file foo contains
<term> <filename> per line:
term1 file1
term2 file2
term3 file1
term1 file2
term3 file3
In q I can read this in like so:
q) tf: ("SS", " ")0: `:foo // read data from foo. two symbols per line
q) tf
term1 term2 term3 term1 term3 // row0 contains the first field
file1 file1 file1 file2 file3 // row1 contains the second field
Now an inverted index is simply:
q) invidx: tf[1] @ group tf[0]
q) invidx
term1| `file1`file2
term2| ,`file2
term3| `file1`file3
q) invidx `term3 // use it to look up which files contain term3
`file1`file3
From: William James
Subject: Re: Basic List processing
Date:
Message-ID: <gfcc0o$lbj$1@aioe.org>
Rob Warnock wrote:
> <················@gmail.com> wrote:
> +---------------
> | Mark Carter <····@privacy.net> wrote:
> | > Suppose further that I want to accumulate totals based on keys.
> The | > first element in the list is the key, and the second element
> in the list | > is the value. Is there a Lisp function which is
> callable something like: | > (accum list) ; => '( (1 9) (3 4) (5 6) )
> >
> > (defun accum-pairlist (list)
> > (let ((return-list nil))
> > (dolist (li list)
> > (if (assoc (first li) return-list)
> > (setf (second (assoc (first li) return-list))
> > (+
> > (second (assoc (first li) return-list))
> > (second li)))
> > (pushnew li return-list)))
> > return-list))
> +---------------
>
> Careful!! Your solution has the same bug that my first
> (and, thankfully, unpublished!) version I did -- it doesn't
> give the same answer twice. [And why it behaves that way
> is even more serious!!] E.g.:
>
> > (defvar list '((1 2) (3 4) (5 6) (1 7)))
>
> LIST
> > (accum-pairlist list)
>
> ((5 6) (3 4) (1 9))
> > (accum-pairlist list)
>
> ((5 6) (3 4) (1 16))
> > (accum-pairlist list)
>
> ((5 6) (3 4) (1 23))
Well, Jonathan, it seems that Xah Lee was right and you were
wrong. Lisp processing in archaic Lisp is more difficult than
it is in a modern language.
Ruby:
def accum_pairlist list
accum = []
list.each{ |key,val|
pair = accum.assoc(key) and
accum[accum.index(pair)][1] += val or
accum << [key,val] }
accum
end
p accum_pairlist( list )
p accum_pairlist( list )
--- output ---
[[1, 9], [3, 4], [5, 6]]
[[1, 9], [3, 4], [5, 6]]
"William James" <·········@yahoo.com> wrote on Tue, 11 Nov 2008:
> it seems that Xah Lee was right and you were wrong. Lisp processing in
> archaic Lisp is more difficult than it is in a modern language.
Please confine your comments to the technical aspects of what you are
discussing. Every programming language is full of tradeoffs, and each
such choice has both pros and cons. It is factually not the case that
Lisp's choices in this matter were made in a state of ignorance, and
that "everybody knows" today how to do it better.
Using loaded terms like "archaic" and "modern" serves no purpose other
than to add needless acrimony to an otherwise useful discussion.
And please, whatever you do, don't take the style of the Mighty Xah as
someone to emulate. The world isn't big enough for two of them. Given
the volumes of his postings and writings, I fear that a second one may
well clog up the remaining capacity of the internet's tubes.
-- Don
_______________________________________________________________________________
Don Geddis http://don.geddis.org/ ···@geddis.org
Incompetence: When you earnestly believe you can compensate for a lack of
skill by doubling your efforts, there's no end to what you can't do.
-- Despair.com
On Nov 11, 11:31 am, "William James" <·········@yahoo.com> wrote:
> Rob Warnock wrote:
> > <················@gmail.com> wrote:
> > +---------------
> > | Mark Carter <····@privacy.net> wrote:
> > | > Suppose further that I want to accumulate totals based on keys.
> > The | > first element in the list is the key, and the second element
> > in the list | > is the value. Is there a Lisp function which is
> > callable something like: | > (accum list) ; => '( (1 9) (3 4) (5 6) )
>
> > > (defun accum-pairlist (list)
> > > (let ((return-list nil))
> > > (dolist (li list)
> > > (if (assoc (first li) return-list)
> > > (setf (second (assoc (first li) return-list))
> > > (+
> > > (second (assoc (first li) return-list))
> > > (second li)))
> > > (pushnew li return-list)))
> > > return-list))
> > +---------------
>
> > Careful!! Your solution has the same bug that my first
> > (and, thankfully, unpublished!) version I did -- it doesn't
> > give the same answer twice. [And why it behaves that way
> > is even more serious!!] E.g.:
>
> > > (defvar list '((1 2) (3 4) (5 6) (1 7)))
>
> > LIST
> > > (accum-pairlist list)
>
> > ((5 6) (3 4) (1 9))
> > > (accum-pairlist list)
>
> > ((5 6) (3 4) (1 16))
> > > (accum-pairlist list)
>
> > ((5 6) (3 4) (1 23))
>
> Well, Jonathan, it seems that Xah Lee was right and you were
> wrong. Lisp processing in archaic Lisp is more difficult than
> it is in a modern language.
>
> Ruby:
>
> def accum_pairlist list
> accum = []
> list.each{ |key,val|
> pair = accum.assoc(key) and
> accum[accum.index(pair)][1] += val or
> accum << [key,val] }
> accum
> end
>
> p accum_pairlist( list )
> p accum_pairlist( list )
>
> --- output ---
> [[1, 9], [3, 4], [5, 6]]
> [[1, 9], [3, 4], [5, 6]]
I don't see how my making an error using destructive functions puts
lisp in the doghouse.
I never argued that lisp was the be-all and end-all of basic list
processing. Xah Lee argued that it was terrible for it. His arguments
come from a fundamental lack of knowledge about lisp and lisp
implementations (He thinks lisp doesn't have things that it does have,
he assumes that cons structures in modern lisp implementations are
implemented in the same way as they were in the 1960s). He also argued
(through a misunderstanding of what a macro is), that lisp has
irregular syntax structure....
(defun fn-pairlist (mylist fn)
(let ((return-list nil)
(list (copy-tree mylist)))
(print fn)
(dolist (li list)
(if (assoc (first li) return-list)
(setf (second (assoc (first li) return-list))
(apply fn
(list
(second (assoc (first li) return-list))
(second li))))
(pushnew li return-list)))
(reverse return-list)))
(defun accum-pairlist (mylist)
(fn-pairlist mylist #'+))
(defun gcd-pairlist (mylist)
(fn-pairlist mylist #'gcd))
(defun lcm-pairlist (mylist)
(fn-pairlist mylist #'lcm))
(defun subtract-pairlist (mylist)
(fn-pairlist mylist #'-))
(defun list-pairlist (mylist)
(fn-pairlist mylist #'(lambda (a b)
(if (listp a)
(append a b)
(list a b))
)))
You can expand it to fit whatever requirements you happen to have.
> (defun list-pairlist (mylist)
> (fn-pairlist mylist #'(lambda (a b)
> (if (listp a)
> (append a b)
> (list a b))
> )))
>
> You can expand it to fit whatever requirements you happen to have.
(defun list-pairlist (mylist)
(fn-pairlist mylist #'(lambda (a b)
(if (listp a)
(if (listp b)
(append a b)
(append a (list b)))
(list a b))
)))
(I'm terrible and forgetful)
On Nov 11, 3:17 pm, ················@gmail.com wrote:
> On Nov 11, 11:31 am, "William James" <·········@yahoo.com> wrote:
>
>
>
>
>
> > Rob Warnock wrote:
> > > <················@gmail.com> wrote:
> > > +---------------
> > > | Mark Carter <····@privacy.net> wrote:
> > > | > Suppose further that I want to accumulate totals based on keys.
> > > The | > first element in the list is the key, and the second element
> > > in the list | > is the value. Is there a Lisp function which is
> > > callable something like: | > (accum list) ; => '( (1 9) (3 4) (5 6) )
>
> > > > (defun accum-pairlist (list)
> > > > (let ((return-list nil))
> > > > (dolist (li list)
> > > > (if (assoc (first li) return-list)
> > > > (setf (second (assoc (first li) return-list))
> > > > (+
> > > > (second (assoc (first li) return-list))
> > > > (second li)))
> > > > (pushnew li return-list)))
> > > > return-list))
> > > +---------------
>
> > > Careful!! Your solution has the same bug that my first
> > > (and, thankfully, unpublished!) version I did -- it doesn't
> > > give the same answer twice. [And why it behaves that way
> > > is even more serious!!] E.g.:
>
> > > > (defvar list '((1 2) (3 4) (5 6) (1 7)))
>
> > > LIST
> > > > (accum-pairlist list)
>
> > > ((5 6) (3 4) (1 9))
> > > > (accum-pairlist list)
>
> > > ((5 6) (3 4) (1 16))
> > > > (accum-pairlist list)
>
> > > ((5 6) (3 4) (1 23))
>
> > Well, Jonathan, it seems that Xah Lee was right and you were
> > wrong. Lisp processing in archaic Lisp is more difficult than
> > it is in a modern language.
>
> > Ruby:
>
> > def accum_pairlist list
> > accum = []
> > list.each{ |key,val|
> > pair = accum.assoc(key) and
> > accum[accum.index(pair)][1] += val or
> > accum << [key,val] }
> > accum
> > end
>
> > p accum_pairlist( list )
> > p accum_pairlist( list )
>
> > --- output ---
> > [[1, 9], [3, 4], [5, 6]]
> > [[1, 9], [3, 4], [5, 6]]
>
> I don't see how my making an error using destructive functions puts
> lisp in the doghouse.
>
> I never argued that lisp was the be-all and end-all of basic list
> processing. Xah Lee argued that it was terrible for it. His arguments
> come from a fundamental lack of knowledge about lisp and lisp
> implementations (He thinks lisp doesn't have things that it does have,
> he assumes that cons structures in modern lisp implementations are
> implemented in the same way as they were in the 1960s). He also argued
> (through a misunderstanding of what a macro is), that lisp has
> irregular syntax structure....
>
> (defun fn-pairlist (mylist fn)
> (let ((return-list nil)
> (list (copy-tree mylist)))
> (print fn)
> (dolist (li list)
> (if (assoc (first li) return-list)
> (setf (second (assoc (first li) return-list))
> (apply fn
> (list
> (second (assoc (first li) return-list))
> (second li))))
> (pushnew li return-list)))
> (reverse return-list)))
>
> (defun accum-pairlist (mylist)
> (fn-pairlist mylist #'+))
>
> (defun gcd-pairlist (mylist)
> (fn-pairlist mylist #'gcd))
>
> (defun lcm-pairlist (mylist)
> (fn-pairlist mylist #'lcm))
>
> (defun subtract-pairlist (mylist)
> (fn-pairlist mylist #'-))
>
> (defun list-pairlist (mylist)
> (fn-pairlist mylist #'(lambda (a b)
> (if (listp a)
> (append a b)
> (list a b))
> )))
>
> You can expand it to fit whatever requirements you happen to have.- Hide quoted text -
Friends,
Programming languages only exist to match the programmers mental model
of a program to the nearly non-existent ability of machines to
understand it. It follows that complaints about language features are
really reflections of individual intellectual styles, abilities, and
limitations. Truly good programmers are so nimble in their thinking
that language features don't even reach the level of consciousness;
their ideas are bigger and more abstract. Consequently, those who
engage in language criticism are mostly revealing their shortcomings.
Refutations and defenses are, in turn, wasteful, bordering on self-
destructive.
On Nov 11, 5:48 pm, Gene <············@gmail.com> wrote:
> On Nov 11, 3:17 pm, ················@gmail.com wrote:
>
>
>
> > On Nov 11, 11:31 am, "William James" <·········@yahoo.com> wrote:
>
> > > Rob Warnock wrote:
> > > > <················@gmail.com> wrote:
> > > > +---------------
> > > > | Mark Carter <····@privacy.net> wrote:
> > > > | > Suppose further that I want to accumulate totals based on keys.
> > > > The | > first element in the list is the key, and the second element
> > > > in the list | > is the value. Is there a Lisp function which is
> > > > callable something like: | > (accum list) ; => '( (1 9) (3 4) (5 6) )
>
> > > > > (defun accum-pairlist (list)
> > > > > (let ((return-list nil))
> > > > > (dolist (li list)
> > > > > (if (assoc (first li) return-list)
> > > > > (setf (second (assoc (first li) return-list))
> > > > > (+
> > > > > (second (assoc (first li) return-list))
> > > > > (second li)))
> > > > > (pushnew li return-list)))
> > > > > return-list))
> > > > +---------------
>
> > > > Careful!! Your solution has the same bug that my first
> > > > (and, thankfully, unpublished!) version I did -- it doesn't
> > > > give the same answer twice. [And why it behaves that way
> > > > is even more serious!!] E.g.:
>
> > > > > (defvar list '((1 2) (3 4) (5 6) (1 7)))
>
> > > > LIST
> > > > > (accum-pairlist list)
>
> > > > ((5 6) (3 4) (1 9))
> > > > > (accum-pairlist list)
>
> > > > ((5 6) (3 4) (1 16))
> > > > > (accum-pairlist list)
>
> > > > ((5 6) (3 4) (1 23))
>
> > > Well, Jonathan, it seems that Xah Lee was right and you were
> > > wrong. Lisp processing in archaic Lisp is more difficult than
> > > it is in a modern language.
>
> > > Ruby:
>
> > > def accum_pairlist list
> > > accum = []
> > > list.each{ |key,val|
> > > pair = accum.assoc(key) and
> > > accum[accum.index(pair)][1] += val or
> > > accum << [key,val] }
> > > accum
> > > end
>
> > > p accum_pairlist( list )
> > > p accum_pairlist( list )
>
> > > --- output ---
> > > [[1, 9], [3, 4], [5, 6]]
> > > [[1, 9], [3, 4], [5, 6]]
>
> > I don't see how my making an error using destructive functions puts
> > lisp in the doghouse.
>
> > I never argued that lisp was the be-all and end-all of basic list
> > processing. Xah Lee argued that it was terrible for it. His arguments
> > come from a fundamental lack of knowledge about lisp and lisp
> > implementations (He thinks lisp doesn't have things that it does have,
> > he assumes that cons structures in modern lisp implementations are
> > implemented in the same way as they were in the 1960s). He also argued
> > (through a misunderstanding of what a macro is), that lisp has
> > irregular syntax structure....
>
> > (defun fn-pairlist (mylist fn)
> > (let ((return-list nil)
> > (list (copy-tree mylist)))
> > (print fn)
> > (dolist (li list)
> > (if (assoc (first li) return-list)
> > (setf (second (assoc (first li) return-list))
> > (apply fn
> > (list
> > (second (assoc (first li) return-list))
> > (second li))))
> > (pushnew li return-list)))
> > (reverse return-list)))
>
> > (defun accum-pairlist (mylist)
> > (fn-pairlist mylist #'+))
>
> > (defun gcd-pairlist (mylist)
> > (fn-pairlist mylist #'gcd))
>
> > (defun lcm-pairlist (mylist)
> > (fn-pairlist mylist #'lcm))
>
> > (defun subtract-pairlist (mylist)
> > (fn-pairlist mylist #'-))
>
> > (defun list-pairlist (mylist)
> > (fn-pairlist mylist #'(lambda (a b)
> > (if (listp a)
> > (append a b)
> > (list a b))
> > )))
>
> > You can expand it to fit whatever requirements you happen to have.- Hide quoted text -
>
> Friends,
>
> Programming languages only exist to match the programmers mental model
> of a program to the nearly non-existent ability of machines to
> understand it.
No, really? I thought it was like a magical incantation.
> It follows that complaints about language features are
> really reflections of individual intellectual styles, abilities, and
> limitations. Truly good programmers are so nimble in their thinking
> that language features don't even reach the level of consciousness;
> their ideas are bigger and more abstract.
Cripes you are full of it.
> Consequently, those who
> engage in language criticism are mostly revealing their shortcomings.
Or the shortcomings of a language in facilitating a certain way of
thought.
> Refutations and defenses are, in turn, wasteful, bordering on self-
> destructive.
Right. Well then, next time someone makes a post full of
misinformation, I'll make sure to ignore it.
On 2008-11-11 17:48:45 -0500, Gene <············@gmail.com> said:
> It follows that complaints about language features are
> really reflections of individual intellectual styles, abilities, and
> limitations.
Complaints about a language are valid when they reflect the real
limitations of that language. If a feature is missing from a language
then it is legitimate to complain about having to greenspun it, or
worse still, the language's inability to let you greenspun it short of
implementing a full blown interpreter for some other, more featureful
language.
On Nov 11, 6:49 pm, Raffael Cavallaro <················@pas-d'espam-
s'il-vous-plait-mac.com> wrote:
> On 2008-11-11 17:48:45 -0500, Gene <············@gmail.com> said:
>
> > It follows that complaints about language features are
> > really reflections of individual intellectual styles, abilities, and
> > limitations.
>
> Complaints about a language are valid when they reflect the real
> limitations of that language. If a feature is missing from a language
> then it is legitimate to complain about having to greenspun it, or
> worse still, the language's inability to let you greenspun it short of
> implementing a full blown interpreter for some other, more featureful
> language.
Ah, but you describe objective critism, which of course is good and
useful. Complaint is about personal discontent. Spending
intellectual and emotional energy on the merits of conses ... yikes.
On 2008-11-11 19:26:15 -0500, Gene <············@gmail.com> said:
> Spending
> intellectual and emotional energy on the merits of conses ... yikes.
Well as a matter of personal preference, yes, I'd agree with you. But
one can critique the lisp style cons from an objective standpoint.
Indeed, Rich Hickey has done just this and his whole clojure language
builds on this critique.
(for those who haven't seen the video, his critique is basically that
cons should not be a data structure but a funtional abstraction that
applies equally to a whole range of data types as long as they conform
to a seq protocol, so that the equivalent of:
(cdr #(1 2 3 4))
would be valid code.)
On 2008-11-13, Raffael Cavallaro
<················@pas-d'espam-s'il-vous-plait-mac.com> wrote:
> (for those who haven't seen the video, his critique is basically that
> cons should not be a data structure but a funtional abstraction that
> applies equally to a whole range of data types as long as they conform
> to a seq protocol, so that the equivalent of:
> (cdr #(1 2 3 4))
> would be valid code.)
Check this out:
(in-package 'vecons)
#<PACKAGE VECONS>
VC[2]> (cons 1 2)
#(1 2)
VC[3]> (car #(1 2))
1
VC[4]> (cdr #(1 2))
2
VC[5]> (cdr #(1 2 3 4))
#(2 3 4)
VC[6]> (append #(1 2 nil) #(4 5 nil))
#(1 2 4 5 NIL)
VC[7]> (append #(1 2 nil) #(4 5 6))
#(1 2 4 5 6)
VC[8]> (append #(1 2 nil) 6)
#(1 2 6)
VC[9]> (append 4 nil)
*** - APPEND: 4 is not a list
The following restarts are available:
ABORT :R1 ABORT
Break 1 VC[10]>
VC[11]> (append 4)
4
VC[12]> (append #(1 2 3) #(4 5 6))
** - APPEND: a proper list does not end with 3
Problem is that some of these operations are stupidly expensive. We expect
(cons <atom> <list>) to be a cheap operation. But making it work over vectors
means that <list> is reallocated. CDR can be done using displaced arrays. But
that's still workse than regular CDR, because it conses something: a memory
record to keep track of the displaced array object.
The source code:
(defpackage :vecons
(:nicknames :vc)
(:use :cl)
(:shadow . #1=(atom consp cons car cdr list list* append))
(:export . #1#))
(in-package :vecons)
(declaim (inline consp))
(declaim (inline atom))
(defun consp (x)
(and (vectorp x) (> (length x) 1)))
(defun atom (x)
(not (consp x)))
(defun cons (a d)
(if (atom d)
(vector a d)
(let ((v (make-array `(,(1+ (length d))))))
(setf (aref v 0) a)
(replace v d :start1 1)
v)))
(defun car (x)
(if (null x)
nil
(aref x 0)))
(defun cdr (x)
(cond
((null x) nil)
((<= (length x) 2)
(aref x 1))
(t
(make-array `(,(1- (length x)))
:displaced-to x
:displaced-index-offset 1))))
(defun list (&rest items)
(if (null items)
nil
(let ((v (make-array `(,(1+ (length items))))))
(replace v items)
v)))
(defun list* (&rest items)
(coerce 'vector items))
(defun improper-check (list error-sym)
(cond
((null list))
((atom list)
(error "~s: ~s is not a list" error-sym list))
(t (let ((term (aref list (1- (length list)))))
(unless (null term)
(error "~s: a proper list does not end with ~s" error-sym term))))))
(defun append (&rest lists)
(loop for l in lists
for count
when (consp l)
summing (1- (length l)) into total-length
finally
(return (let ((v (unless (zerop total-length)
(make-array `(,(1+ total-length))))))
(loop for l in lists
and for pos = 0 then (if (consp l)
(+ pos (length l) -1)
pos)
for num
if (< num (1- count))
do (improper-check l 'append)
else if (atom l)
do (if v
(setf (aref v pos) l)
(setf v l))
end
when (consp l)
do (replace v l :start1 pos)
finally (return v))))))
On 2008-11-13 18:44:39 -0500, Kaz Kylheku <········@gmail.com> said:
> Problem is that some of these operations are stupidly expensive. We expect
> (cons <atom> <list>) to be a cheap operation. But making it work over vectors
> means that <list> is reallocated.
First let me preface this by saying that some of this post is for the
benefit of others who may be reading since you will find a good part of
it quite obvious.
All these clojure sequence data types are persistent in the sense that
they are immutable. A function like cons (or conj) returns a new datum
that can share structure with its args. So the equivalent of (cons
<atom> <vector>):
user=> (def some-vector (vector 1 2 3 4 5))
#'user/some-vector
user=> (vec (cons 'foo some-vector))
[foo 1 2 3 4 5]
will return a new vector which may (or may not) share its tail with
some-vector.
Additionally, clojure vectors are functions of their indices, so you
can do vector ref with:
(my-vec 17)
Since these are immutable data with functional interfaces, there's no
requirement that vectors be represented as arrays:
"Vectors support access to items by index in log32N hops"
whereas "real" arrays have O(1) access time (agin, not directed at you Kaz).
Whether this greater expense is stupid depends on your application.
Presumably when you need the speed of real array access you'll use a
different underlying representation, the arrays available from Java:
user=> (def real-array (to-array some-vector))
#'user/real-array
user=> (aget real-array 0)
1
user=> real-array
[··················@67ec05
(i.e., real-array is a "native" Java array)
William James schrieb:
> Ruby:
>
> def accum_pairlist list
> accum = []
> list.each{ |key,val|
> pair = accum.assoc(key) and
> accum[accum.index(pair)][1] += val or
> accum << [key,val] }
> accum
> end
>
>
> p accum_pairlist( list )
> p accum_pairlist( list )
>
> --- output ---
> [[1, 9], [3, 4], [5, 6]]
> [[1, 9], [3, 4], [5, 6]]
The Ruby version looks good, and for a non-Lisp it’s really nice.
For a comparison here in Lisp:
Clojure:
(defn accum-pairlist [list]
(loop [[[f s] & r :as l] list
result {}]
(if l
(recur r (assoc result f (+ s (get result f 0))))
(sort result))))
Trying it in the repl:
user> (accum-pairlist *list*)
([1 9] [3 4] [5 6])
user> (accum-pairlist *list*)
([1 9] [3 4] [5 6])
Without counting the leading spaces in each row Ruby needs nearly 10%
more chars to express this simple algorithm, and 33% more LOC.
Imagine what would happen if we worked on non-trivial problems...
With your imperative language this won’t be a positive experience.
André
--
Lisp is not dead. It’s just the URL that has changed:
http://clojure.org/
On Nov 15, 11:22 pm, André Thieme <address.good.until.
···········@justmail.de> wrote:
> William James schrieb:
>
>
>
> > Ruby:
>
> > def accum_pairlist list
> > accum = []
> > list.each{ |key,val|
> > pair = accum.assoc(key) and
> > accum[accum.index(pair)][1] += val or
> > accum << [key,val] }
> > accum
> > end
>
> > p accum_pairlist( list )
> > p accum_pairlist( list )
>
> > --- output ---
> > [[1, 9], [3, 4], [5, 6]]
> > [[1, 9], [3, 4], [5, 6]]
>
> The Ruby version looks good, and for a non-Lisp it’s really nice.
> For a comparison here in Lisp:
>
> Clojure:
> (defn accum-pairlist [list]
> (loop [[[f s] & r :as l] list
> result {}]
> (if l
> (recur r (assoc result f (+ s (get result f 0))))
> (sort result))))
>
> Trying it in the repl:
> user> (accum-pairlist *list*)
> ([1 9] [3 4] [5 6])
> user> (accum-pairlist *list*)
> ([1 9] [3 4] [5 6])
>
> Without counting the leading spaces in each row Ruby needs nearly 10%
> more chars to express this simple algorithm, and 33% more LOC.
> Imagine what would happen if we worked on non-trivial problems...
> With your imperative language this won’t be a positive experience.
>
Cleaner with reduce:
(defn accum-pairlist [list]
(reduce (fn [m [k v]] (assoc m k (+ (m k 0) v)))
{} list))
or if the data were more idiomatically represented in Clojure:
(def *list* [{1 2} {3 4} {5 6} {1 7}])
(apply merge-with + *list*)
Both of which return a map, as it seems silly to throw away this
useful, fast, result type. You can always get a list of pairs by
calling seq on it.
> Lisp is not dead. It’s just the URL that has changed:
While I appreciate your enthusiasm for Clojure, it has served Clojure
well not to provoke/invade the community here. This is not a zero sum
game between languages, and certainly not between Lisps. Live and let
live.
Rich
Rich Hickey <··········@gmail.com> writes:
> Cleaner with reduce:
>
> (defn accum-pairlist [list]
> (reduce (fn [m [k v]] (assoc m k (+ (m k 0) v)))
> {} list))
>
> or if the data were more idiomatically represented in Clojure:
>
> (def *list* [{1 2} {3 4} {5 6} {1 7}])
>
> (apply merge-with + *list*)
Both of those versions are very aesthetically pleasing. As a Ruby
developer (wanting to learn more Lisp), I must admit I like this
*much* better.
> Both of which return a map, as it seems silly to throw away this
> useful, fast, result type. You can always get a list of pairs by
> calling seq on it.
>
>> Lisp is not dead. It’s just the URL that has changed:
>
> While I appreciate your enthusiasm for Clojure, it has served Clojure
> well not to provoke/invade the community here. This is not a zero sum
> game between languages, and certainly not between Lisps. Live and let
> live.
>
> Rich
Well said. You've done a great job designing Clojure, articulating its
benefits and representing it. Best of success w/ Clojure. I believe
the adage, "all ships rise with the tide", has some applicability
here.
--
Brian Adkins
http://www.lojic.com/
http://lojic.com/blog/
André Thieme <······························@justmail.de> writes:
> William James schrieb:
>
>> Ruby:
>>
>> def accum_pairlist list
>> accum = []
>> list.each{ |key,val|
>> pair = accum.assoc(key) and
>> accum[accum.index(pair)][1] += val or
>> accum << [key,val] }
>> accum
>> end
>>
>>
>> p accum_pairlist( list )
>> p accum_pairlist( list )
>>
>> --- output ---
>> [[1, 9], [3, 4], [5, 6]]
>> [[1, 9], [3, 4], [5, 6]]
>
>
> The Ruby version looks good, and for a non-Lisp it’s really nice.
> For a comparison here in Lisp:
>
>
> Clojure:
> (defn accum-pairlist [list]
> (loop [[[f s] & r :as l] list
> result {}]
> (if l
> (recur r (assoc result f (+ s (get result f 0))))
> (sort result))))
def accum_pairlist list
list.inject({}) {|r,p| r[p[0]] = (r[p[0]] || 0) + p[1]; r }.to_a
end
irb(main):004:0> accum_pairlist [[1,2],[3,4],[5,6],[1,7]]
=> [[5, 6], [1, 9], [3, 4]]
On 2008-11-10, Mark Carter <··@privacy.net> wrote:
> I am looking at CLHS, and I am having a hard time figuring out what list
> processing functions would be suitable for me.
>
> Suppose I have:
>
> (defvar *list*
> '((1 2)
> (3 4)
> (5 6)
> (1 7)))
>
>
> Now, suppose I want the "keys" of the list, defined by the first element
> of the list. Is there a Lisp function which is callable something like:
> (keys *list* :key #'first) ; => '(1 3 5)
>
> Suppose further that I want to accumulate totals based on keys. The
> first element in the list is the key, and the second element in the list
> is the value. Is there a Lisp function which is callable something like:
> (accum *list*) ; => '( (1 9) (3 4) (5 6) )
What we can do is define a somewhat general function for processing this type
of associative list.
(defun histogram (assoc-list reduce-func &rest reduce-args)
(let ((hash (make-hash-table :test #'eql)))
(loop for (key value) in assoc-list
do (push value (gethash key hash)))
(loop for key being the hash-keys of hash
using (hash-value value-list)
collect `(,key
,(apply #'reduce reduce-func value-list reduce-args)))))
What HISTOGRAM does is collates the values that share the same key into
lists, and then it processes each list through REDUCE, so that you can
summarize the values using arbitrary arithmetic, not only addition.
Some tests:
Add:
(histogram '((1 2) (3 4) (5 6) (1 7)) #'+)
-> ((5 6) (3 4) (1 9))
Multiply:
(histogram '((1 2) (3 4) (5 6) (1 7)) #'*)
-> ((5 6) (3 4) (1 14))
Add, supplying initial value for each summation:
(histogram '((1 2) (3 4) (5 6) (1 7)) #'+ :initial-value 100)
-> ((5 106) (3 104) (1 109))
Etc.