While we are at it, will it be better to rewrite 'fold-packages' and
similar things (like 'search') using streams?

For example:

  #:use-module (ice-9 streams)

[...]

(define (fold-packages-lazy proc init)
  "Call (PROC PACKAGE RESULT) for each available package, using INIT as
the initial value of RESULT."
  (stream-fold
   (lambda (module result)
     (stream-fold (lambda (var result)
                    (if (package? var)
                        (proc var result)
                        result))
                  result
                  (list->stream
                   (module-map (lambda (sym var)
                                 (false-if-exception (variable-ref var)))
                               module))))
   init
   (list->stream (package-modules))))

'time' shows that the above is a bit slower than the current version.
Will it be faster when we have more packages?  What about memory?