I'm reading Paul Graham's ANSI Common Lisp, there's a problem in the
book which says:
Define a function that takes a list and returns a list indicating the
number of times each (eql) element appears, sorted from most common
element to least common:
> (occurrences ' ( a b a d a c d e a ) )
((A . 4) (C . 2) (D . 2) (B . 1))
So I wrote this:
(defun occurrence (list)
(let ((results ()))
(dolist (element list)
(let ((times (cdr (assoc element results))))
(if (null times)
(push (cons element 1) results)
(incf times))))
(sort results #'> :key #'car)))
to my surprise this function always returns with only one occurrence:
((A . 1) (C . 1) (D . 1) (B . 1))
Could anybody tell me why? Thanks!
On Aug 13, 4:36 pm, Wang Jiaji <··········@gmail.com> wrote:
> (defun occurrence (list)
> (let ((results ()))
> (dolist (element list)
> (let ((times (cdr (assoc element results))))
> (if (null times)
> (push (cons element 1) results)
> (incf times))))
> (sort results #'> :key #'car)))
Plus what Tamas told, pay attention to your :KEY argument in SORT.
OTOH, you might want to use a hash table (which has -- theoratically
-- O(1) access overhead) instead of an association list (which has
O(n) access overhead).
Volkan YAZICI <·············@gmail.com> writes:
> On Aug 13, 4:36 pm, Wang Jiaji <··········@gmail.com> wrote:
>> (defun occurrence (list)
>> (let ((results ()))
>> (dolist (element list)
>> (let ((times (cdr (assoc element results))))
>> (if (null times)
>> (push (cons element 1) results)
>> (incf times))))
>> (sort results #'> :key #'car)))
>
> Plus what Tamas told, pay attention to your :KEY argument in SORT.
>
> OTOH, you might want to use a hash table (which has -- theoratically
> -- O(1) access overhead) instead of an association list (which has
> O(n) access overhead).
Premature, and ill-conceived optimization. The use case presented
shows only founr keys. In most implementations, assoc will be faster
than a hash-table on so few keys.
Last time I benchmarked, the break point was at about 5 for sbcl, and
>30 for clisp.
--
__Pascal Bourguignon__
On Wed, 13 Aug 2008 06:36:57 -0700, Wang Jiaji wrote:
> I'm reading Paul Graham's ANSI Common Lisp, there's a problem in the
> book which says:
>
> Define a function that takes a list and returns a list indicating the
> number of times each (eql) element appears, sorted from most common
> element to least common:
>> (occurrences ' ( a b a d a c d e a ) )
> ((A . 4) (C . 2) (D . 2) (B . 1))
>
> So I wrote this:
>
> (defun occurrence (list)
> (let ((results ()))
> (dolist (element list)
> (let ((times (cdr (assoc element results))))
> (if (null times)
> (push (cons element 1) results)
> (incf times))))
> (sort results #'> :key #'car)))
>
> to my surprise this function always returns with only one occurrence:
> ((A . 1) (C . 1) (D . 1) (B . 1))
>
> Could anybody tell me why? Thanks!
You read the number from the association list, put it in a local
variable, and increment that. Instead, you want to increment the
original. I won't spoil it by telling you how, but you can easily find
out.
Tamas
On Aug 13, 9:36 pm, Wang Jiaji <··········@gmail.com> wrote:
> I'm reading Paul Graham's ANSI Common Lisp, there's a problem in the
> book which says:
>
> Define a function that takes a list and returns a list indicating the
> number of times each (eql) element appears, sorted from most common
> element to least common:> (occurrences ' ( a b a d a c d e a ) )
>
> ((A . 4) (C . 2) (D . 2) (B . 1))
>
> So I wrote this:
>
> (defun occurrence (list)
> (let ((results ()))
> (dolist (element list)
> (let ((times (cdr (assoc element results))))
> (if (null times)
> (push (cons element 1) results)
> (incf times))))
> (sort results #'> :key #'car)))
>
> to my surprise this function always returns with only one occurrence:
> ((A . 1) (C . 1) (D . 1) (B . 1))
>
> Could anybody tell me why? Thanks!
Thanks for your indication, I can see that it'll work if I replace
every 'times' with (cdr (assoc element results)), but this will make
the code a little lousy.
Is there a way to get a variable to hold a 'place' instead of its
value (I've tried setf, but it didn't work)? In fact, I thought since
cdr returns a place, times will also be a place.
On Aug 14, 3:33 am, Wang Jiaji <··········@gmail.com> wrote:
> On Aug 13, 9:36 pm, Wang Jiaji <··········@gmail.com> wrote:
>
>
>
> > I'm reading Paul Graham's ANSI Common Lisp, there's a problem in the
> > book which says:
>
> > Define a function that takes a list and returns a list indicating the
> > number of times each (eql) element appears, sorted from most common
> > element to least common:> (occurrences ' ( a b a d a c d e a ) )
>
> > ((A . 4) (C . 2) (D . 2) (B . 1))
Btw, the answer is wrong for this example.
>
> > So I wrote this:
>
> > (defun occurrence (list)
> > (let ((results ()))
> > (dolist (element list)
> > (let ((times (cdr (assoc element results))))
> > (if (null times)
> > (push (cons element 1) results)
> > (incf times))))
> > (sort results #'> :key #'car)))
>
> > to my surprise this function always returns with only one occurrence:
> > ((A . 1) (C . 1) (D . 1) (B . 1))
>
> > Could anybody tell me why? Thanks!
You are manipulating times, but it is not part of (i.e. not tied to)
the alist you are building up as your result. It just holds the
_value_ of (cdr (assoc element results)) in your code.
> Thanks for your indication, I can see that it'll work if I replace
> every 'times' with (cdr (assoc element results)), but this will make
> the code a little lousy.
Why not use the the result returned by assoc directly, like so:
(defun occurences (lst)
(let (res)
(dolist (item lst (sort res #'> :key #'cdr))
(let ((occur (assoc item res)))
(if occur
(incf (cdr occur))
(setf res (acons item 1 res)))))))
> Is there a way to get a variable to hold a 'place' instead of its
> value (I've tried setf, but it didn't work)?
In this case you can get to the place by going "up" to the cons
(returned by assoc) like I did in my example above.
> In fact, I thought since
> cdr returns a place, times will also be a place.
cdr is a place and that place will be assigned a new value (or a
pointer to the new value, depending on the data and the
implementation) when set (e.g.
(setf (cdr some-cons) value) ).
cdr will return the _value_ of the place (or the value being pointed
to) when asked for it's contents (e.g. (cdr some-cons) ).
See Common Lisp: A Gentle Introduction to Symbolic Computation,
especially chapters 1 to 3, for a, uhm, gentle introduction with
pictures (http://www.cs.cmu.edu/~dst/LispBook/index.html).
Or, for a more functional solution to your problem (not necessarily
efficient), where you don't have to explicitly store and built up the
result:
(defun occurences2 (lst)
(sort (mapcar #'(lambda (item)
(cons item (count item lst)))
(remove-duplicates lst))
#'> :key #'cdr))
HTH.
Nico
Wang Jiaji wrote:
> On Aug 13, 9:36 pm, Wang Jiaji <··········@gmail.com> wrote:
>> I'm reading Paul Graham's ANSI Common Lisp, there's a problem in the
>> book which says:
>>
>> Define a function that takes a list and returns a list indicating the
>> number of times each (eql) element appears, sorted from most common
>> element to least common:> (occurrences ' ( a b a d a c d e a ) )
>>
>> ((A . 4) (C . 2) (D . 2) (B . 1))
>>
>> So I wrote this:
>>
>> (defun occurrence (list)
>> (let ((results ()))
>> (dolist (element list)
>> (let ((times (cdr (assoc element results))))
>> (if (null times)
>> (push (cons element 1) results)
>> (incf times))))
>> (sort results #'> :key #'car)))
>>
>> to my surprise this function always returns with only one occurrence:
>> ((A . 1) (C . 1) (D . 1) (B . 1))
>>
>> Could anybody tell me why? Thanks!
>
> Thanks for your indication, I can see that it'll work if I replace
> every 'times' with (cdr (assoc element results)), but this will make
> the code a little lousy.
You are looking for symbol-macrolet, it can hide all that for you if you
like.
> Is there a way to get a variable to hold a 'place' instead of its
> value (I've tried setf, but it didn't work)? In fact, I thought since
> cdr returns a place, times will also be a place.
cdr does not return a place, cdr is a place.
your brain is stuck in pointerthink. instead of explaining to us what a
language you have used for a day should do, you should -- I feel a
naggum coming on -- stop trying to impose your prior understanding on a
new experience. You are like an American tourist landing in Kinshasha
and going in search of a Burger King. Sadly they do not have to go far.
I digress.
kt
--
$$$$$: http://www.theoryyalgebra.com/
Cells: http://common-lisp.net/project/cells/
BSlog: http://smuglispweeny.blogspot.com/
Kenny wrote:
> Wang Jiaji wrote:
> > On Aug 13, 9:36 pm, Wang Jiaji <··········@gmail.com> wrote:
> >> I'm reading Paul Graham's ANSI Common Lisp, there's a problem in the
> >> book which says:
> >>
> >> Define a function that takes a list and returns a list indicating the
> >> number of times each (eql) element appears, sorted from most common
> >> element to least common:> (occurrences ' ( a b a d a c d e a ) )
> >>
> >> ((A . 4) (C . 2) (D . 2) (B . 1))
> >>
> >> So I wrote this:
> >>
> >> (defun occurrence (list)
> >> (let ((results ()))
> >> (dolist (element list)
> >> (let ((times (cdr (assoc element results))))
> >> (if (null times)
> >> (push (cons element 1) results)
> >> (incf times))))
> >> (sort results #'> :key #'car)))
> >>
> >> to my surprise this function always returns with only one occurrence:
> >> ((A . 1) (C . 1) (D . 1) (B . 1))
> >>
> >> Could anybody tell me why? Thanks!
> >
> > Thanks for your indication, I can see that it'll work if I replace
> > every 'times' with (cdr (assoc element results)), but this will make
> > the code a little lousy.
>
> You are looking for symbol-macrolet, it can hide all that for you if you
> like.
I think the above problem is fairly common and we don't have a good
idiom for doing it, at least not one that I'm aware about. Just look
at q solution for a simgliar grouping problem.
(defun count (list)
(let ((hash (make-hash-table)))
(dolist (el list)
(incf (gethash (cadr el) hash 0) (car el)))
(let (result)
(maphash (lambda (key val)
(push (list val key) result))
hash)
result)))
vs
flip(count each group v[;1];unique v[;1])
bobi
Slobodan Blazeski wrote:
> Kenny wrote:
> > Wang Jiaji wrote:
> > > On Aug 13, 9:36 pm, Wang Jiaji <··········@gmail.com> wrote:
> > >> I'm reading Paul Graham's ANSI Common Lisp, there's a problem in the
> > >> book which says:
> > >>
> > >> Define a function that takes a list and returns a list indicating the
> > >> number of times each (eql) element appears, sorted from most common
> > >> element to least common:> (occurrences ' ( a b a d a c d e a ) )
> > >>
> > >> ((A . 4) (C . 2) (D . 2) (B . 1))
> > >>
> > >> So I wrote this:
> > >>
> > >> (defun occurrence (list)
> > >> (let ((results ()))
> > >> (dolist (element list)
> > >> (let ((times (cdr (assoc element results))))
> > >> (if (null times)
> > >> (push (cons element 1) results)
> > >> (incf times))))
> > >> (sort results #'> :key #'car)))
> > >>
> > >> to my surprise this function always returns with only one occurrence:
> > >> ((A . 1) (C . 1) (D . 1) (B . 1))
> > >>
> > >> Could anybody tell me why? Thanks!
> > >
> > > Thanks for your indication, I can see that it'll work if I replace
> > > every 'times' with (cdr (assoc element results)), but this will make
> > > the code a little lousy.
> >
> > You are looking for symbol-macrolet, it can hide all that for you if you
> > like.
>
>
> I think the above problem is fairly common and we don't have a good
> idiom for doing it, at least not one that I'm aware about. Just look
> at q solution for a simgliar grouping problem.
>
> (defun count (list)
> (let ((hash (make-hash-table)))
> (dolist (el list)
> (incf (gethash (cadr el) hash 0) (car el)))
> (let (result)
> (maphash (lambda (key val)
> (push (list val key) result))
> hash)
> result)))
>
> vs
> flip(count each group v[;1];unique v[;1])
>
> bobi
Sorry I forgot the link http://www.nsl.com/papers/kisntlisp.htm
Incremental posting :)
bobi
On Aug 13, 9:36 am, Wang Jiaji <··········@gmail.com> wrote:
> I'm reading Paul Graham's ANSI Common Lisp, there's a problem in the
> book which says:
>
> Define a function that takes a list and returns a list indicating the
> number of times each (eql) element appears, sorted from most common
> element to least common:> (occurrences ' ( a b a d a c d e a ) )
>
> ((A . 4) (C . 2) (D . 2) (B . 1))
>
> So I wrote this:
>
> (defun occurrence (list)
> (let ((results ()))
> (dolist (element list)
> (let ((times (cdr (assoc element results))))
> (if (null times)
> (push (cons element 1) results)
> (incf times))))
> (sort results #'> :key #'car)))
>
> to my surprise this function always returns with only one occurrence:
> ((A . 1) (C . 1) (D . 1) (B . 1))
>
> Could anybody tell me why? Thanks!
Since it looks like you understand why this doesn't work and have come
up with a solution on your own, I'll show you what I did to solve this
problem:
(defun occurrences (lst)
(and (consp lst)
(let ((result-list nil))
(mapcar #'(lambda (x)
(let ((pair (assoc x result-list)))
(if (null pair)
(push (cons x 1) result-list)
(incf (cdr pair)))))
lst)
(sort result-list #'> :key #'cdr))))
I have to say, having spent years developing in other languages, I was
pretty jaded coming to lisp. Java? Just like C++ with some extra
features and libraries. C#? MS's java. No real surprises.
Lisp is different though. In the short time I've been learning it,
I've had almost daily epiphanies. "Oh! So THAT'S how you do that.
Nice!" I may still be an "American in Kinshasa", but I'm definitely
developing a taste for Doro Wat!
On Aug 14, 10:08 am, vttoonses <·········@gmail.com> wrote:
> On Aug 13, 9:36 am, Wang Jiaji <··········@gmail.com> wrote:
>
>
>
> > I'm reading Paul Graham's ANSI Common Lisp, there's a problem in the
> > book which says:
>
> > Define a function that takes a list and returns a list indicating the
> > number of times each (eql) element appears, sorted from most common
> > element to least common:> (occurrences ' ( a b a d a c d e a ) )
>
> > ((A . 4) (C . 2) (D . 2) (B . 1))
>
> > So I wrote this:
>
> > (defun occurrence (list)
> > (let ((results ()))
> > (dolist (element list)
> > (let ((times (cdr (assoc element results))))
> > (if (null times)
> > (push (cons element 1) results)
> > (incf times))))
> > (sort results #'> :key #'car)))
>
> > to my surprise this function always returns with only one occurrence:
> > ((A . 1) (C . 1) (D . 1) (B . 1))
>
> > Could anybody tell me why? Thanks!
>
> Since it looks like you understand why this doesn't work and have come
> up with a solution on your own, I'll show you what I did to solve this
> problem:
>
> (defun occurrences (lst)
> (and (consp lst)
> (let ((result-list nil))
> (mapcar #'(lambda (x)
> (let ((pair (assoc x result-list)))
> (if (null pair)
> (push (cons x 1) result-list)
> (incf (cdr pair)))))
> lst)
> (sort result-list #'> :key #'cdr))))
>
> I have to say, having spent years developing in other languages, I was
> pretty jaded coming to lisp. Java? Just like C++ with some extra
> features and libraries. C#? MS's java. No real surprises.
>
> Lisp is different though. In the short time I've been learning it,
> I've had almost daily epiphanies. "Oh! So THAT'S how you do that.
> Nice!" I may still be an "American in Kinshasa", but I'm definitely
> developing a taste for Doro Wat!
Seems simpler to do the counts with a hash, convert to an alist,
then sort the alist:
(defun occurrences (list)
(let ((h (make-hash-table)))
(mapc (lambda (key) (incf (gethash key h 0))) list)
(let ((a nil))
(maphash (lambda (key value) (push (cons key value) a)) h)
(sort a #'> :key #'cdr)
)))
--S
Thanks for all your replies. Having spent several days in Lisp, I
think that Lisp is really a good language to learn when you just want
to learn something.
smallpond <·········@juno.com> writes:
> Seems simpler to do the counts with a hash, convert to an alist,
> then sort the alist:
>
> (defun occurrences (list)
> (let ((h (make-hash-table)))
> (mapc (lambda (key) (incf (gethash key h 0))) list)
> (let ((a nil))
> (maphash (lambda (key value) (push (cons key value) a)) h)
> (sort a #'> :key #'cdr)
> )))
What's simplier is to abstract away.
(defun make-histogram () ...)
(defun increment-histogram-entry (histogram entry &optional (increment 1)) ...)
(defun histogram-as-alist (histogram) ...)
(defun occurrences (list)
(let ((h (make-histogram)))
(mapc (lambda (key) (increment-histogram-entry h key)) list)
(sort (histogram-as-alist h) #'> :key #'cdr)))
It doesn't matter whether you implement histograms as a-list or as
hash-tables or anything else. Since we don't know we'll have more
than a few entries, I'd say implement it as an a-list, since it'd be
faster:
(defstruct histogram (test (function eql)) alist) ; this is the implementation of make-histogram!
(defun increment-histogram-entry (histogram entry &optional (increment 1))
(let ((ass (assoc entry (histogram-alist histogram)
:test (histogram-test histogram))))
(if ass
(incf (cdr ass) increment)
(push (cons entry increment) (histogram-alist histogram)))))
(defun histogram-as-alist (histogram)
(mapcar (lambda (pair) (cons (car pair) (cdr pair)))
(histogram-alist histogram)))
--
__Pascal Bourguignon__ http://www.informatimago.com/
Until real software engineering is developed, the next best practice
is to develop with a dynamic system that has extreme late binding in
all aspects. The first system to really do this in an important way
is Lisp. -- Alan Kay
P� Tue, 16 Sep 2008 20:24:51 +0200, skrev Joost Diepenmaat
<·····@zeekat.nl>:
> smallpond <·········@juno.com> writes:
>
>> Seems simpler to do the counts with a hash, convert to an alist,
>> then sort the alist:
>>
>> (defun occurrences (list)
>> (let ((h (make-hash-table)))
>> (mapc (lambda (key) (incf (gethash key h 0))) list)
>> (let ((a nil))
>> (maphash (lambda (key value) (push (cons key value) a)) h)
>> (sort a #'> :key #'cdr)
>> )))
>>
>> --S
>
> Since everybody's doing it, I thought I'd show off my version:
>
> (defun occurrence (list)
> (let ((results))
> (dolist (e list)
> (incf (cdr (or (assoc e results)
> (car (push (cons e 0) results))))))
> (sort results #'> :key #'cdr)))
>
>
Here's another.. Gave me a chance to play with some rarely used options to
defstruct. It shows that alist's don't have to work on only on (key .
value) pairs. Tossed in PG's aif as well. Also removed some unnecessary
consing in mapcar by using mapc. I find defstruct on lists to be fine for
prototyping as it saves some work writing readers and writers for objects
while making the code's intentions clearer.
(defmacro aif (test true-branch &optional false-branch)
`(let ((it ,test))
(if it
,true-branch
,false-branch)))
(defstruct (occurence-pair
(:type list)
(:constructor oc-make (symbol))
(:conc-name oc-))
symbol
(count 1 :type integer))
(defun occurences (list)
(check-type list list)
(let (result)
(mapc (lambda (sym)
(aif (assoc sym result)
(incf (oc-count it))
(push (oc-make sym) result)))
list)
(sort result #'> :key #'oc-count)))
CL-USER 10 > (occurences '(a b a d a c d e a))
((A 4) (D 2) (E 1) (C 1) (B 1))
--------------
John Thingstad
"John Thingstad" <·······@online.no> writes:
> P� Tue, 16 Sep 2008 20:24:51 +0200, skrev Joost Diepenmaat
> <·····@zeekat.nl>:
>
>> smallpond <·········@juno.com> writes:
>>
>>> Seems simpler to do the counts with a hash, convert to an alist,
>>> then sort the alist:
>>>
>>> (defun occurrences (list)
>>> (let ((h (make-hash-table)))
>>> (mapc (lambda (key) (incf (gethash key h 0))) list)
>>> (let ((a nil))
>>> (maphash (lambda (key value) (push (cons key value) a)) h)
>>> (sort a #'> :key #'cdr)
>>> )))
>>>
>>> --S
>>
>> Since everybody's doing it, I thought I'd show off my version:
>>
>> (defun occurrence (list)
>> (let ((results))
>> (dolist (e list)
>> (incf (cdr (or (assoc e results)
>> (car (push (cons e 0) results))))))
>> (sort results #'> :key #'cdr)))
>>
>>
>
> Here's another.. Gave me a chance to play with some rarely used
> options to defstruct. It shows that alist's don't have to work on
> only on (key . value) pairs. Tossed in PG's aif as well. Also removed
> some unnecessary consing in mapcar by using mapc. I find defstruct on
> lists to be fine for prototyping as it saves some work writing
> readers and writers for objects while making the code's intentions
> clearer.
>
> (defmacro aif (test true-branch &optional false-branch)
> `(let ((it ,test))
> (if it
> ,true-branch
> ,false-branch)))
>
> (defstruct (occurence-pair
> (:type list)
> (:constructor oc-make (symbol))
> (:conc-name oc-))
> symbol
> (count 1 :type integer))
>
> (defun occurences (list)
> (check-type list list)
> (let (result)
> (mapc (lambda (sym)
> (aif (assoc sym result)
> (incf (oc-count it))
> (push (oc-make sym) result)))
> list)
> (sort result #'> :key #'oc-count)))
>
> CL-USER 10 > (occurences '(a b a d a c d e a))
> ((A 4) (D 2) (E 1) (C 1) (B 1))
Here's one using some of the earlier ideas, plus a double sprinkling
of loop and a little gratuitous obfuscation::
(defun occurrences (list)
(sort (loop for key being the hash-keys of
(let ((ht (make-hash-table)))
(loop for elt in list
do (incf (gethash elt ht 0)))
ht)
using (hash-value val)
collect (cons key val))
#'> :key #'cdr))
* Raymond Wiker <··············@RAWMBP.local> :
Wrote on Tue, 16 Sep 2008 23:00:51 +0200:
| "John Thingstad" <·······@online.no> writes:
|
|> På Tue, 16 Sep 2008 20:24:51 +0200, skrev Joost Diepenmaat
|> <·····@zeekat.nl>:
|>
|>> smallpond <·········@juno.com> writes:
|>>
|>>> Seems simpler to do the counts with a hash, convert to an alist,
|>>> then sort the alist:
|>>>
|>>> (defun occurrences (list)
|>>> (let ((h (make-hash-table)))
|>>> (mapc (lambda (key) (incf (gethash key h 0))) list)
|>>> (let ((a nil))
|>>> (maphash (lambda (key value) (push (cons key value) a)) h)
|>>> (sort a #'> :key #'cdr)
|>>> )))
|
|>> Since everybody's doing it, I thought I'd show off my version:
|>>
|>> (defun occurrence (list)
|>> (let ((results))
|>> (dolist (e list)
|>> (incf (cdr (or (assoc e results)
|>> (car (push (cons e 0) results))))))
|>> (sort results #'> :key #'cdr)))
|>>
|>>
|>
|> (defmacro aif (test true-branch &optional false-branch)
|> `(let ((it ,test))
|> (if it
|> ,true-branch
|> ,false-branch)))
|>
|> (defstruct (occurence-pair
|> (:type list)
|> (:constructor oc-make (symbol))
|> (:conc-name oc-))
|> symbol
|> (count 1 :type integer))
|>
|> (defun occurences (list)
|> (check-type list list)
|> (let (result)
|> (mapc (lambda (sym)
|> (aif (assoc sym result)
|> (incf (oc-count it))
|> (push (oc-make sym) result)))
|> list)
|> (sort result #'> :key #'oc-count)))
|>
|
| Here's one using some of the earlier ideas, plus a double sprinkling
| of loop and a little gratuitous obfuscation::
|
| (defun occurrences (list)
| (sort (loop for key being the hash-keys of
| (let ((ht (make-hash-table)))
| (loop for elt in list
| do (incf (gethash elt ht 0)))
| ht)
| using (hash-value val)
| collect (cons key val))
| #'> :key #'cdr))
And here's an untested one that that keeps the list sorted in reverse
order all the time for no good reason :)
Well maybe except to avoid a final SORT
(defun occurrences (list &aux result)
(loop for x in list do
(loop for l on result for c = (car l)
when (eql x (car c)) do
(incf (cdr c))
(let ((idx (loop for i from 0 for (a . n) in (cdr l)
if (< n (cdr c)) return nil
if (> n (cdr c)) return i)))
(when idx
(rotatef (elt l 0) (elt l idx))))
(return)
finally (push (cons x 1) result)))
(nreverse result))
--
Madhu
* Madhu <··············@moon.robolove.meer.net> :
Wrote on Wed, 17 Sep 2008 17:27:33 +0530:
| And here's an untested one that that keeps the list sorted
Should've tested it before sending.
| order all the time for no good reason :)
| Well maybe except to avoid a final SORT
|
| (defun occurrences (list &aux result)
| (loop for x in list do
| (loop for l on result for c = (car l)
| when (eql x (car c)) do
| (incf (cdr c))
| (let ((idx (loop for i from 0 for (a . n) in (cdr l)
| if (< n (cdr c)) return nil
| if (> n (cdr c)) return i)))
These two lines should've been
if (< n (cdr c)) return i
if (> n (cdr c)) return nil)))
|
| (when idx
| (rotatef (elt l 0) (elt l idx))))
| (return)
| finally (push (cons x 1) result)))
| (nreverse result))
--
Blargh
* Madhu <··············@moon.robolove.meer.net> :
Wrote on Wed, 17 Sep 2008 17:27:33 +0530:
| And here's an untested one that that keeps the list sorted
Should've tested it before sending.
| order all the time for no good reason :)
| Well maybe except to avoid a final SORT
|
| (defun occurrences (list &aux result)
| (loop for x in list do
| (loop for l on result for c = (car l)
| when (eql x (car c)) do
| (incf (cdr c))
| (let ((idx (loop for i from 0 for (a . n) in (cdr l)
| if (< n (cdr c)) return nil
| if (> n (cdr c)) return i)))
These two lines should've been
if (< n (cdr c)) return 1 ;; extra obfuscation!
if (> n (cdr c)) return nil)))
|
| (when idx
| (rotatef (elt l 0) (elt l idx))))
| (return)
| finally (push (cons x 1) result)))
| (nreverse result))
--
Blargh
* Madhu <··············@moon.robolove.meer.net> :
Wrote on Wed, 17 Sep 2008 17:27:33 +0530:
| And here's an untested one that that keeps the list sorted
Should've tested it before sending.
| (defun occurrences (list &aux result)
| (loop for x in list do
| (loop for l on result for c = (car l)
| when (eql x (car c)) do
| (incf (cdr c))
| (let ((idx (loop for i from 0 for (a . n) in (cdr l)
| if (< n (cdr c)) return nil
| if (> n (cdr c)) return i)))
These three lines should've been
(let ((idx (loop for j = 0 then i
for i from 1 for (a . n) in (cdr l)
if (>= n (cdr c)) return j)))
|
| (when idx
| (rotatef (elt l 0) (elt l idx))))
| (return)
| finally (push (cons x 1) result)))
| (nreverse result))
--
Double Blargh!
* Madhu <··············@moon.robolove.meer.net> :
Wrote on Wed, 17 Sep 2008 17:27:33 +0530:
| And here's an untested one that that keeps the list sorted
Should've tested it before sending.
| (defun occurrences (list &aux result)
| (loop for x in list do
| (loop for l on result for c = (car l)
| when (eql x (car c)) do
| (incf (cdr c))
| (let ((idx (loop for i from 0 for (a . n) in (cdr l)
| if (< n (cdr c)) return nil
| if (> n (cdr c)) return i)))
These two lines should've been
if (>= n (cdr c)) return i
finally (return i))))
|
| (when idx
| (rotatef (elt l 0) (elt l idx))))
| (return)
| finally (push (cons x 1) result)))
| (nreverse result))
--
Double Blargh!
On Aug 14, 9:08 am, vttoonses <·········@gmail.com> wrote:
> On Aug 13, 9:36 am, Wang Jiaji <··········@gmail.com> wrote:
>
>
>
> > I'm reading Paul Graham's ANSI Common Lisp, there's a problem in the
> > book which says:
>
> > Define a function that takes a list and returns a list indicating the
> > number of times each (eql) element appears, sorted from most common
> > element to least common:> (occurrences ' ( a b a d a c d e a ) )
>
> > ((A . 4) (C . 2) (D . 2) (B . 1))
>
> > So I wrote this:
>
> > (defun occurrence (list)
> > (let ((results ()))
> > (dolist (element list)
> > (let ((times (cdr (assoc element results))))
> > (if (null times)
> > (push (cons element 1) results)
> > (incf times))))
> > (sort results #'> :key #'car)))
>
> > to my surprise this function always returns with only one occurrence:
> > ((A . 1) (C . 1) (D . 1) (B . 1))
>
> > Could anybody tell me why? Thanks!
>
> Since it looks like you understand why this doesn't work and have come
> up with a solution on your own, I'll show you what I did to solve this
> problem:
>
> (defun occurrences (lst)
> (and (consp lst)
> (let ((result-list nil))
> (mapcar #'(lambda (x)
> (let ((pair (assoc x result-list)))
> (if (null pair)
> (push (cons x 1) result-list)
> (incf (cdr pair)))))
> lst)
> (sort result-list #'> :key #'cdr))))
Let's convert from ancient COBOL to modern Ruby.
def occurrences array
h = {} ; h.default = 0
array.each{|x| h[x] += 1 }
h.sort_by{|a| -a.last }
end
>
> I have to say, having spent years developing in other languages, I was
> pretty jaded coming to lisp. Java? Just like C++ with some extra
> features and libraries. C#? MS's java. No real surprises.
>
> Lisp is different though. In the short time I've been learning it,
> I've had almost daily epiphanies. "Oh! So THAT'S how you do that.
> Nice!" I may still be an "American in Kinshasa", but I'm definitely
> developing a taste for Doro Wat!
William James <·········@yahoo.com> writes:
> Let's convert from ancient COBOL to modern Ruby.
>
> def occurrences array
> h = {} ; h.default = 0
> array.each{|x| h[x] += 1 }
> h.sort_by{|a| -a.last }
> end
I think you missed the newsgroup.
What you want is comp.lang.ruby
--
Thomas A. Russ, USC/Information Sciences Institute
William James <·········@yahoo.com> wrote in news:37a4cb9f-c691-440b-b34e-
············@79g2000hsk.googlegroups.com:
> def occurrences array
> h = {} ; h.default = 0
> array.each{|x| h[x] += 1 }
> h.sort_by{|a| -a.last }
> end
Can you please explain how the above Ruby code works? Since this isn't a
Ruby newsgroup, we can't be expected to understand it. In particular, what
is h? Is it an array of associations, associating each symbol with a
count? How do the symbols get there? Vaguely interpreting the code
without knowing the language, it looks like it's making a sequence of
numbers, and incrementing those numbers to make it a histogram. As long as
it remains in the correct order, it looks like it should be usable. But
once you sort it, it relies on the presence of the symbols. But how do the
symbols get there? I don't see you putting them there. I assume this is
just because I don't know Ruby. And that's why I would like an explanation
of how this code works.
In article <···················@fe085.usenetserver.com>,
Anagram <·······@nearmonopolyirkswuss.com> wrote:
> William James <·········@yahoo.com> wrote in news:37a4cb9f-c691-440b-b34e-
> ············@79g2000hsk.googlegroups.com:
>
> > def occurrences array
> > h = {} ; h.default = 0
> > array.each{|x| h[x] += 1 }
> > h.sort_by{|a| -a.last }
> > end
>
> Can you please explain how the above Ruby code works? Since this isn't a
> Ruby newsgroup, we can't be expected to understand it. In particular, what
> is h? Is it an array of associations, associating each symbol with a
> count? How do the symbols get there? Vaguely interpreting the code
> without knowing the language, it looks like it's making a sequence of
> numbers, and incrementing those numbers to make it a histogram. As long as
> it remains in the correct order, it looks like it should be usable. But
> once you sort it, it relies on the presence of the symbols. But how do the
> symbols get there? I don't see you putting them there. I assume this is
> just because I don't know Ruby. And that's why I would like an explanation
> of how this code works.
Don't care how it works. Just enjoy its beauty!
It reminds me of this little gem:
#define X
#define XX
#define XXX
#define XXXX
#define XXXXX
#define XXXXXX
#define XXXXXXX
#define orfa for
#define XXXXXXXXX
#define archa char
#define ainma main
#define etcharga getchar
#define utcharpa putchar
X X
X X X X
X X X X
X X X X
X X X X
X X X X
X X X X
X X X X X X
X XX X X XX X
X XXX X XXXXXXXXX X XXX X
X XXX X XXXX XXXX X XXX X
X XXXX X XX ainma(){ archa XX X XXXX X
X XXXX X oink[9],*igpa, X XXXX X
X XXXXXX atinla=etcharga(),iocccwa XXXXXX X
X XXXX ,apca='A',owla='a',umna=26 XXXX X
X XXX ; orfa(; (atinla+1)&&(!((( XXX X
X XX atinla-apca)*(apca+umna-atinla) XX X
X X >=0)+((atinla-owla)*(owla+umna- X X
X atinla)>=0))); utcharpa(atinla), X
X X atinla=etcharga()); orfa(; atinla+1; X X
X X ){ orfa( igpa=oink ,iocccwa=( X X
X X (atinla- XXX apca)*( XXX apca+umna- X X
X atinla)>=0) XXX XXX ; (((( X
X atinla-apca XXXXX XXXXXXX XXXXX )*(apca+ X
X umna-atinla XXXXXX )>=0) XXXXXX +((atinla- X
X owla)*(owla+ XXXX umna- XXXX atinla)>=0)) X
X &&"-Pig-" XX "Lat-in" XX "COb-fus" X
X "ca-tion!!"[ X (((atinla- X apca)*(apca+ X
X umna-atinla) X >=0)?atinla- X apca+owla: X
X atinla)-owla X ]-'-')||((igpa== X oink)&&!(*( X
X igpa++)='w') X )||! X (*( X igpa X ++)=owla); * X
X (igpa++)=(( X ( XXX XXX X atinla-apca X
X )*(apca+ X umna XXX - XXX X atinla)>=0) X
X ?atinla- X apca XXX + XXX owla X :atinla), X
X atinla= X X X X etcharga()) X
X ; orfa( X atinla=iocccwa?(( X (atinla- X
X owla)*(owla+ X umna-atinla)>=0 X )?atinla- X
X owla+apca: X atinla): X atinla; ((( X
X atinla-apca)* X (apca+umna- X atinla)>=0)+( X
X (atinla-owla)* X (owla+ X umna-atinla)>= X
X 0)); utcharpa( XX XX atinla),atinla X
X =etcharga()); XXXXXXX orfa(*igpa=0, X
X igpa=oink; * igpa; utcharpa( X
X *(igpa++))); orfa(; (atinla+1)&&(!((( X
X atinla-apca )*(apca+ X
X umna- XXXXX XXXXX atinla)>=0 X
X )+(( XXXXX atinla- X
XX owla)*( owla+umna- XX
XX atinla)>=0))); utcharpa XX
XX (atinla),atinla= XX
XX etcharga()); } XX
XXXX } XXXX
XXXXXXXXX
--
http://lispm.dyndns.org/
On Tue, 16 Sep 2008 11:00:12 -0700, William James wrote:
> Let's convert from ancient COBOL to modern Ruby.
>
> def occurrences array
> h = {} ; h.default = 0
> array.each{|x| h[x] += 1 }
> h.sort_by{|a| -a.last }
> end
I thought of asking why you are posting Ruby code (which no one asked
for) on c.l.l. But hey, who cares? The nice people who wrote my
newsreader thought of the possibility of encountering your ilk. Ignore
Author... done. Problem solved.
Tamas
On 2008-09-16, William James <·········@yahoo.com> wrote:
>> (defun occurrences (lst)
>> (and (consp lst)
>> (let ((result-list nil))
>> (mapcar #'(lambda (x)
>> (let ((pair (assoc x result-list)))
>> (if (null pair)
>> (push (cons x 1) result-list)
>> (incf (cdr pair)))))
>> lst)
>> (sort result-list #'> :key #'cdr))))
>
> Let's convert from ancient COBOL to modern Ruby.
>
> def occurrences array
> h = {} ; h.default = 0
> array.each{|x| h[x] += 1 }
> h.sort_by{|a| -a.last }
> end
Well done. Now convert this one:
(quote
(defun occurrences (lst)
(and (consp lst)
(let ((result-list nil))
(mapcar #'(lambda (x)
(let ((pair (assoc x result-list)))
(if (null pair)
(push (cons x 1) result-list)
(incf (cdr pair)))))
lst)
(sort result-list #'> :key #'cdr)))))
Bonus points: no usef of character strings.
Code is data in the ``ancient COBOL'', by design. Not just any data, but data
that is programmer-visible and convenient. This is a key functional
requirement, and the syntax is that way to satisfy the requirement.
Code is a character string in ``modern'' Ruby. Representing code as data is not
considered a functional requirement. The lexical syntax can therefore be
designed without regard for such a requirement.
There are situations when it's desireable to have freely-designed lexical
syntax, without consideration for any requirement that it be isomorphic to an
abstract syntax tree data structure. For such situations, Common Lisp offers a
programmable lexical syntax.
For instance, we can make Lisp understand {|x,y| x + y} to be a notation which
means the same thing as (lambda (x y) (+ x y)).
For instance, there is an ready-made, portable infix package which lets you
write code like f(x,y[3+4]) instead of (f x (aref y (+ 3 4))).
In spite of the ready availability, nobody uses this.
Lispers do use the programmable lexical syntax, but for other things.
So, you can see the difficult you face as a troll trying to evangelize the
terse notation of another programming language. Lispers generally don't prefer
to to use terse notations even when someone else has already developed them in
such a way that they can be easily loaded into the Lisp image.
William James <·········@yahoo.com> wrote:
> Let's convert from ancient COBOL to modern Ruby.
>
> def occurrences array
> h = {} ; h.default = 0
> array.each{|x| h[x] += 1 }
> h.sort_by{|a| -a.last }
> end
Your modern Ruby code looks broken to me.
Ancient COBOL:
? (occurrences '((1 2) (1 2)))
(((1 2) . 1) ((1 2) . 1))
Good!
Modern Ruby:
?> occurrences [[1,2],[1,2]]
=> [[[1, 2], 2]]
Not so good.
--
Paolo Micossi
William James schrieb:
> On Aug 14, 9:08 am, vttoonses <·········@gmail.com> wrote:
>> On Aug 13, 9:36 am, Wang Jiaji <··········@gmail.com> wrote:
>>
>>
>>
>>> I'm reading Paul Graham's ANSI Common Lisp, there's a problem in the
>>> book which says:
>>> Define a function that takes a list and returns a list indicating the
>>> number of times each (eql) element appears, sorted from most common
>>> element to least common:> (occurrences ' ( a b a d a c d e a ) )
>>> ((A . 4) (C . 2) (D . 2) (B . 1))
>>> So I wrote this:
>>> (defun occurrence (list)
>>> (let ((results ()))
>>> (dolist (element list)
>>> (let ((times (cdr (assoc element results))))
>>> (if (null times)
>>> (push (cons element 1) results)
>>> (incf times))))
>>> (sort results #'> :key #'car)))
>>> to my surprise this function always returns with only one occurrence:
>>> ((A . 1) (C . 1) (D . 1) (B . 1))
>>> Could anybody tell me why? Thanks!
>> Since it looks like you understand why this doesn't work and have come
>> up with a solution on your own, I'll show you what I did to solve this
>> problem:
>>
>> (defun occurrences (lst)
>> (and (consp lst)
>> (let ((result-list nil))
>> (mapcar #'(lambda (x)
>> (let ((pair (assoc x result-list)))
>> (if (null pair)
>> (push (cons x 1) result-list)
>> (incf (cdr pair)))))
>> lst)
>> (sort result-list #'> :key #'cdr))))
>
> Let's convert from ancient COBOL to modern Ruby.
>
> def occurrences array
> h = {} ; h.default = 0
> array.each{|x| h[x] += 1 }
> h.sort_by{|a| -a.last }
> end
Nice.
But in Lisp it has a smaller complexity:
(defun occurrences (array)
(let ((h (make-hash-table)))
(each array (lambda (x) (incf (gethash x h))))
(sort-by h (lambda (a) (- (htlast a))))))
The Lisp program has 24 program points. Your Ruby code has 29.
A mentionable difference of 20%.
From character count Ruby wins, but that doesn�t matter for programmers
brains. While {|x| ...} has fewer chars than (lambda (x) ...) it�s both
times still three points in the program complexity.
Andr�
--
On Fri, 19 Sep 2008 08:34:09 +0200, André Thieme wrote:
> The Lisp program has 24 program points. Your Ruby code has 29. A
> mentionable difference of 20%.
> From character count Ruby wins, but that doesn’t matter for programmers
> brains. While {|x| ...} has fewer chars than (lambda (x) ...) it’s both
> times still three points in the program complexity.
I enjoy comparison of < 10 line code snippets as the next man, but I do
hope that all participants in these kind of discussions realize that they
are not relevant when comparing programming languages. What you care
about is how your programming language handles the complexity of _large_
projects, and that is where Lisp shines.
Comparison of languages using small code snippets is a pretty pointless
exercise. "Look how elegantly my language can calculate the Fibonacci
series!" So what?
Tamas
Tamas K Papp schrieb:
> On Fri, 19 Sep 2008 08:34:09 +0200, André Thieme wrote:
>
>> The Lisp program has 24 program points. Your Ruby code has 29. A
>> mentionable difference of 20%.
>> From character count Ruby wins, but that doesn’t matter for programmers
>> brains. While {|x| ...} has fewer chars than (lambda (x) ...) it’s both
>> times still three points in the program complexity.
>
> I enjoy comparison of < 10 line code snippets as the next man, but I do
> hope that all participants in these kind of discussions realize that they
> are not relevant when comparing programming languages. What you care
> about is how your programming language handles the complexity of _large_
> projects, and that is where Lisp shines.
>
> Comparison of languages using small code snippets is a pretty pointless
> exercise. "Look how elegantly my language can calculate the Fibonacci
> series!" So what?
>
Tamas, you are obviously right. Or we could say: obviously for people
who already actually do work.
Some people (like William for example) don’t understand this yet and
still have a good bit of way before them. Even small or medium sized
projects already won’t be much different, regardless of your language
used.
William does not understand that all his examples show nothing.
He tricks himself into believing that Ruby was able to beat Lisp,
because in some cases it offered functions in its standard library
or because it saves 7 chars (compared with lambda) when using a
block, or because some functions have shorter names, like Rubys map vs
mapcar.
If he continues to study programming and finally does some real work
he will realize that this didn’t win anything.
A programmer wants to see an algorithm, that he can’t do in his
programming language because of some restrictions in the language
design - only then he could acknowledge that this other lang can
actually solve that task better.
But we were only shown programming techniques that are used since
decades in Lisp and other languages. All these little snippets can
be solved exactly the same way as they were solved in Ruby.
This is mostly the point that I wanted to make. But yeah, I fully
agree with what you said. No real piece of software will be written
faster because the programmer has to type
foo.inject(4){|x| ...} instead of
(reduce (lambda (x) ...) foo :initial-value 4).
Although this can impress the unexperienced people when they find it
in 2-liners in usenet.
André
--
Wang Jiaji wrote:
> I'm reading Paul Graham's ANSI Common Lisp, there's a problem in the
> book which says:
>
> Define a function that takes a list and returns a list indicating the
> number of times each (eql) element appears, sorted from most common
> element to least common:
> > (occurrences ' ( a b a d a c d e a ) )
> ((A . 4) (C . 2) (D . 2) (B . 1))
>
> So I wrote this:
>
> (defun occurrence (list)
> (let ((results ()))
> (dolist (element list)
> (let ((times (cdr (assoc element results))))
> (if (null times)
> (push (cons element 1) results)
> (incf times))))
> (sort results #'> :key #'car)))
>
> to my surprise this function always returns with only one occurrence:
> ((A . 1) (C . 1) (D . 1) (B . 1))
>
> Could anybody tell me why? Thanks!
Try this, tested only with your example but looks ok:.
(defun occ (l &optional r)
(if l (occ (remove (car l) l) (cons (list (car l) (count (car l) l))
r)) r))
bobi
Slobodan Blazeski wrote:
> Wang Jiaji wrote:
> > I'm reading Paul Graham's ANSI Common Lisp, there's a problem in the
> > book which says:
> >
> > Define a function that takes a list and returns a list indicating the
> > number of times each (eql) element appears, sorted from most common
> > element to least common:
> > > (occurrences ' ( a b a d a c d e a ) )
> > ((A . 4) (C . 2) (D . 2) (B . 1))
> >
> > So I wrote this:
> >
> > (defun occurrence (list)
> > (let ((results ()))
> > (dolist (element list)
> > (let ((times (cdr (assoc element results))))
> > (if (null times)
> > (push (cons element 1) results)
> > (incf times))))
> > (sort results #'> :key #'car)))
> >
> > to my surprise this function always returns with only one occurrence:
> > ((A . 1) (C . 1) (D . 1) (B . 1))
> >
> > Could anybody tell me why? Thanks!
> Try this, tested only with your example but looks ok:.
> (defun occ (l &optional r)
> (if l (occ (remove (car l) l) (cons (list (car l) (count (car l) l))
> r)) r))
>
> bobi
Sorry forgot the sorting
(defun occ (l &optional r)
(if l (occ (remove (car l) l) (cons (list (car l) (count (car l) l))
r)) (sort r #'> :key #'cadr)))
OCC
CL-USER 28 : 2 > (occ l)
((A 4) (D 2) (E 1) (C 1) (B 1))
bobi