RE: group-by: question

To Vincent St-Amour: thanks for your answer.
I'll do some timing tests,
but it may take me some days.
(I have other duties too)
I guess that for small amounts of data, alists may be faster,
but for very large amounts of data hashes may be faster.
Let's see what my measurements will say.
Jos 

-----Original Message-----
From: Vincent St-Amour [mailto:[email protected]] 
Sent: 25 June 2018 16:37
To: Jos Koot
Cc: 'Shu-Hung You'; 'Racket Users'
Subject: Re: [racket-users] group-by: question

Jos,

Thanks for taking a look!

Functionality-wise, a custom hash should work fine.

If I recall correctly, we picked alists in that case because they have
lower overhead. But I don't recall us ever doing actual measurements.

So if you'd like to try it out, I'd be happy to review your pull request!

Vincent



On Sat, 23 Jun 2018 07:11:12 -0500,
Jos Koot wrote:
> 
> Hi,
> Procedure group-by uses an alist if the
> equivalence relation is not eq?, eqv? or equal?,
> but would a custom hash as shown below not to be preferred?
> (See lines marked with <======)
> Best wishes, Jos
> 
> #lang racket
> ;; (x -> y) (listof x) [(y y -> bool)] -> (listof (listof x))
> ;; groups together elements that are considered equal
> ;; =? should be reflexive, transitive and commutative
> (define (group-by key l [=? equal?])
> 
>   (unless (and (procedure? key)
>                (procedure-arity-includes? key 1))
>     (raise-argument-error 'group-by "(-> any/c any/c)" 0 key l))
>   (unless (and (procedure? =?)
>                (procedure-arity-includes? =? 2))
>     (raise-argument-error 'group-by "(any/c any/c . -> . any/c)" 2 key l =?))
>   (unless (list? l)
>     (raise-argument-error 'group-by "list?" 1 key l))
> 
>   (define-values (base update in)  ; <=========
>     (cond [(equal? =? eq?)    (values (hasheq)    hash-update in-hash)]
>           [(equal? =? eqv?)   (values (hasheqv)   hash-update in-hash)]
>           [(equal? =? equal?) (values (hash)      hash-update in-hash)]
>           [else
>            (define make-dict
>             (let-values (((a b c d e f g) (make-custom-hash-types =?))) e))
>                               (values (make-dict) dict-update in-dict)]))
> 
>   (define classes
>     (for/fold ([res base])
>         ([elt (in-list l)]
>          [idx (in-naturals)]) ; to keep ordering stable
>       (define k (key elt))
>       (define v (cons idx elt))
>       (update res k (lambda (o) (cons v o)) '())))
>   (define sorted-classes
>     (if (list? classes)
>         (for/list ([p (in-list classes)])
>           (sort (cdr p) < #:key car))
>         (for/list ([(_ c) (in classes)]) ; <=======
>           (sort c < #:key car))))
>   ;; sort classes by order of first appearance, then remove indices
>   (for/list ([c (in-list (sort sorted-classes < #:key caar))])
>     (map cdr c)))
> 
> ; example
> 
> (group-by car
>           '(("A" . a) ("b" . b) ("C" . c) ("a" . a))
>           string-ci=?)
> 
> 
> -----Original Message-----
> From: Shu-Hung You [mailto:[email protected]] 
> Sent: 22 June 2018 22:08
> To: Jos Koot
> Cc: Racket Users
> Subject: Re: [racket-users] group-by: question
> 
> It can always be subsumed by `same?`, but can express the intention
> better when the supplied list has some internal structure, e.g. an
> association list:
> 
> (group-by car
>           '(("A" . a) ("b" . b) ("C" . c) ("a" . a))
>           string-ci=?)
> 
> In this example, `car` extracts the key from the association list and
> we wish to group the list by the key, case insensitively.
> 
> 
> -- 
> You received this message because you are subscribed to the Google Groups "Racket Users" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/[email protected]
> For more options, visit https://groups.google.com/d/optout.

-- 
You received this message because you are subscribed to the Google Groups "Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscribe-/JYPxA39Uh5TLH3MbocFF+G/[email protected]
For more options, visit https://groups.google.com/d/optout.