Re: ‘new text-spanner’ development

[David Nalesnik]

On Wed, Sep 23, 2015 at 6:54 AM, David Kastrup <address@hidden> wrote:

[...]

 

Well, I don't know who is responsible for this particular idiom
encountered frequently in here,

That would be me....

 

but the following open-coded loop is
both opaque and inefficient (namely O(n^2) as _appending_ to a list is
an O(n) operation):

extractLyricEventInfo =
#(define-scheme-function (lst) (ly:music?)
   "Given a music _expression_ @var{lst}, return a list of pairs.  The
@code{car} of each pair is the text of any @code{LyricEvent}, and the
@code{cdr} is a boolean representing presence or absence of a hyphen
associated with that @code{LyricEvent}."
   ;; TODO: include duration info, skips?
   (let ((grist (extract-named-music lst '(LyricEvent))))
     (let mill ((grist grist) (flour '()))
       (if (null? grist)
           flour
           (let* ((text (ly:music-property (car grist) 'text))
                  (hyphen (extract-named-music (car grist) 'HyphenEvent))
                  (hyphen? (not (null? hyphen))))
             (mill (cdr grist)
               (append flour (list (cons text hyphen?)))))))))

Open-coded, you are much better off writing:

   (let ((grist (extract-named-music lst '(LyricEvent))))
     (let mill ((grist grist) (flour '()))
       (if (null? grist)
           (reverse! flour)
           (let* ((text (ly:music-property (car grist) 'text))
                  (hyphen (extract-named-music (car grist) 'HyphenEvent))
                  (hyphen? (not (null? hyphen))))
             (mill (cdr grist)
               (cons (cons text hyphen?) flour))))))

Since cons is O(1) and the final reverse! O(n) is only done once, you
arrive at O(n) for all.  But why open-code in the first place?

  (map (lambda (elt)
         (let* ((text (ly:music-property elt 'text))
                (hyphen (extract-named-music elt 'HyphenEvent))
                (hyphen? (pair? hyphen)))
            (cons text hyphen)))
       (extract-named-music lst 'LyricEvent)))

For something that is one-on-one, this is far more transparent.  And
even for something that is one-to-some (namely resulting in possibly 0,
1, or more elements), (append-map (lambda (elt) ...) ...) tends to be
much clearer.

OK, thanks!  Will update accordingly.

DN