I used the following code to solve Sum by Factors:

#lang racket
(provide sum-of-divided)

(define (sum-of-divided lst)
  (define (go ps n l)
    (define ((exhaust d) x)
      (define q (/ x d))
      (if (integer? q)
          ((exhaust d) q)
          (if (> x 1) `(,x) '())))
    (if (null? l)
        ps
        (if
          (for/or
            ([p ps])
            #:break (< n (sqr p))
            (= 0 (modulo n p)))
          (go ps (  n 1) l)
          (go
            (append ps `(,n))
            (  n 1)
            (append-map (exhaust n) l)))))
  (for*/list
    ([m (go '() 2 (map abs lst))]
     [s `(,(for/fold
       ([a '(0 #f)])
       ([x lst])
       (if (= 0 (modulo x m))
           `(,(  (car a) x) #t)
           a)))]
     #:when (cadr s))
    `(,m ,(car s))))

To my surprise, it passed the tests, which have a time limit of 12 s, only after I changed sequence-append in L20 to append. The documentation for sequence-append says:

The new sequence is constructed lazily.

But, as it turns out, it apparently means that the subsequent sequences aren't concatenated unless needed. But when their elements are needed, i.e. the sequence resulting from sequence-append is consumed far enough, the time cost linear in the sum of lengths of all previous sequences is incurred. Right? Is that why it was slow?

If so, how to work around it? (In this case append was performant enough, but suppose I really needed a structure which is at least a FIFO queue with the usual complexities.) Is there a good alternative within the racket language, without requireing additional packages (which may be unavailable, as is the case on Codewars)? Difference lists maybe (quite easy to implement from scratch)?

CodePudding user response：

I ended up using the obvious, hitherto purposely avoided: mutable lists:

#lang racket
(provide sum-of-divided)

(define (sum-of-divided lst)
  (define ps (mcons 0 '()))
  (define t ps)
  (for*/list
    ([m
      (let go ([n 2] [l (map abs lst)])
        (if (null? l)
            (mcdr ps)
            (go
              (  n 1)
              (if
                (for/or
                  ([p (mcdr ps)])
                  #:break (< n (sqr p))
                  (= 0 (modulo n p)))
                l
                (begin
                  (set-mcdr! t (mcons n '()))
                  (set! t (mcdr t))
                  (remq*
                    '(1)
                    (map
                      (λ (x)
                         (let exhaust ([s x])
                           (define q (/ s n))
                           (if (integer? q)
                               (exhaust q)
                               s)))
                      l)))))))]
     [s `(,(for/fold
       ([a '(0 #f)])
       ([x lst])
       (if (= 0 (modulo x m))
           `(,(  (car a) x) #t)
           a)))]
     #:when (cadr s))
    `(,m ,(car s))))

I also tried a purely functional approach with streams:

#lang racket
(provide sum-of-divided)

(define primes
  (letrec
    ([ps
      (stream*
        2
        (for*/stream
          ([i (in-naturals 3)]
           #:unless
             (for/or
               ([p ps])
               #:break (< i (sqr p))
               (= 0 (modulo i p))))
        i))])
    ps))

(define (sum-of-divided lst)
  (for/fold
    ([l lst]
     [r '()]
     #:result (reverse r))
    ([d primes])
    #:break (null? l)
    (values
      (remq*
        '(1)
        (map
          (λ (x)
             (let exhaust ([s x])
               (define q (/ s d))
               (if (integer? q)
                   (exhaust q)
                   s)))
          l))
      `(,@(for/fold
          ([a 0]
           [f #f]
           #:result
             (if f
                 `((,d ,a))
                 '()))
          ([n lst])
           (if (= 0 (modulo n d))
               (values (  a n) #t)
               (values a f)))
        ,@r))))

Surprisingly, it consistently times out, whereas the imperative one above never does. Having believed Racket implementors cared at least equally for performance with functional style, I'm disappointed.