Path: ...!news.nobody.at!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: "B. Pym" <Nobody447095@here-nor-there.org>
Newsgroups: comp.lang.lisp,comp.lang.scheme
Subject: Re: A "killer" macro
Date: Sun, 8 Sep 2024 04:08:51 -0000 (UTC)
Organization: A noiseless patient Spider
Lines: 70
Message-ID: <vbj80e$1qbp8$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Injection-Date: Sun, 08 Sep 2024 06:08:52 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="28a2661e92d5fbf480e61cc300081820";
	logging-data="1912616"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX18cg+mHXHaPesvSVfyw2tj3"
User-Agent: XanaNews/1.18.1.6
Cancel-Lock: sha1:y/1Xs42rjoyAK86by9n+xps1XJ0=
Bytes: 3207

> could fit on one page of Prolog.  Better still, when I ran the new
> code against the old code for the same inputs (given 7 cards,
> evaluate, and return the best 5 card hand), it "disagreed" with the
> old code on about 5 hands out of several million randomly generated
> hands, and spit out different solutions for those hands.  When I
> analyzed the differences, I found that the Prolog solution was correct
> in those cases.  It was due to a few hard-to-find bugs in the old
> solution, which was to be expected simply because that code was much
> longer and more complex.  So the new Prolog solution, because of its
> simplicity, was also more correct, and uncovered bugs in the old
> solution.
> 
> To illustrate the conciseness of the Prolog solution, here is the code
> to recognize a "4 of a kind":
> 
> quad(A,B,C,D,E,F,G) :- permutation([A,B,C,D,E,F,G],[X,X,X,X,_,_,_]).
> 
> That's it - one line of code, and the input doesn't even need to be
> sorted beforehand, as the old solution's input did, so I get to remove
> an unnecessary sort.

That the code is concise doesn't mean that it is not grossly
inefficient. The mindless Prolog solution may have to generate
5040 permutations to determine that there are not four of a
kind.

Gauche Scheme

(use gauche.collection)  ;; group-collection

(define (quad? lst)
  (= 4 (apply max (map length (group-collection lst)))))

(quad? '(A B C D E F G))
  ===>
#f

(quad? '(A B A D A A G))
  ===>
#t

Don't have "group-collection"?  Use an association list.

(define (quad? cards)
  (let ((al '()))
    (dolist (c cards) (ainc! al c))
    (> (apply max (map cdr al)) 3)))

Both of these solutions have got to be more efficient
than the Prolog code.

It seems to me that association lists are not used enough
in Lispy languages.  The languages don't provide enough
functions for dealing with them.

Here's the macro for "ainc!".

(define-syntax ainc!
  (syntax-rules ()
    [(_ alist key val func default)
     (let ((pair (assoc key alist)))
       (if pair
         (set-cdr! pair (func val (cdr pair)))
         (set! alist (cons (cons key (func val default)) alist))))]
    [(_ alist key val func)
     (ainc! alist key val func 0)]
    [(_ alist key val)
     (ainc! alist key val +)]
    [(_ alist key)
     (ainc! alist key 1)]))