Ludovic Courtès <ludo@gnu.org> writes:

> Hi!
>
> Christopher Baines <mail@cbaines.net> skribis:
>
>> There could be performance issues with member here, but only if there are lots
>> of replacements.
>>
>> * guix/scripts/weather.scm (all-packages): Return all exported packages, plus
>> non exported replacements, rather than including exported replacements twice.
>
> [...]
>
>> +  "Return the list of packages we are going to query."
>> +  (let* ((packages
>> +          (fold-packages (lambda (package result)
>> +                           (cons package result))
>> +                         '()
>> +
>> +                         ;; Dismiss deprecated packages but keep hidden packages.
>> +                         #:select? (negate package-superseded)))
>> +         (non-exported-replacement-packages
>> +          (fold-packages (lambda (package result)
>> +                           (let ((replacement (package-replacement package)))
>> +                             (if (and replacement
>> +                                      ;; Avoid double couting replacements
>> +                                      ;; that are themselves exported
>> +                                      (not (member replacement packages)))
>> +                                 (cons replacement result)
>> +                                 result)))
>> +                         '()
>> +
>> +                         ;; Dismiss deprecated packages but keep hidden packages.
>> +                         #:select? (negate package-superseded))))
>> +    (append
>> +     packages
>> +     non-exported-replacement-packages)))
>
> Is the goal to delete duplicates?

Not really, the goal is to have a list with no duplicates.

> In that case, how about wrapping the existing expression in
> (delete-duplicates … eq?) ?
>
> (Note that (member x lst) is O(N) is the number of packages, so the code
> above is quadratic in the number of packages, which should be avoided.
> Also, packages cannot be meaningfully compared with ‘equal?’ (which is
> expensive in case of different packages), so ‘eq?’ should be preferred.)

Replacing member with memq seems sensible.

My understanding of delete duplicates is that it's O(N^2), because it
constructs a new list, and keeps searching it in linear time. While that
sounds better, doing a linear search of packages for each replacement
should be quicker, assuming there's only a few replacements compared to
the number of packages.

I'm fine with either though, I don't actually know which is faster, and
it probably doesn't matter anyway. I'll send a patch with a
delete-duplicates approach.