Re: [PATCH] Make some local functions public (was: Re: lily-library.scm question)

[Mark Polesky]

Jay Anderson wrote:

> > last-pair is an O(n) operation, since it has to traverse the whole list,
> > making split-at-predicate O(n^2) instead of O(n), as it should be. You'd be
> > better off building L0 backwards and reversing it at the end, so that the
> > element you need is always at the beginning of a list.
>
> Also it should avoid length when a null? check will do. Here's the
> function with those changes:
> 
> (define-public (split-at-predicate predicate lst)
>   "Split a list into 2 lists at the first element that returns #f for
>   (predicate previous_element element). Return the two parts as a pair.
>   Example: (split-at-predicate < '(1 2 3 2 1)) ==> ((1 2 3) . (2 1))"
>   (if (or (null? lst) (null? (cdr lst)))
>     (list lst)
>     (let loop ((lst-a (list (car lst))) (lst-b (cdr lst)))
>       (cond ((null? lst-b) (list lst))
>             ((predicate (car lst-a) (car lst-b))
>               (loop (cons (car lst-b) lst-a) (cdr lst-b)))
>             (else (cons (reverse lst-a) lst-b))))))


I know, I know, I just won't let this die. I rewrote this silly
function yet again (by now it's more of a programming exercise
than anything else). But the things I've learned from everyone so
far have found their way into my other LilyPond work, so I don't
think it's a waste of time.

I discovered 2 procedures from srfi-1 that can work in tandem for
this: list-index and split-at. I'm left wondering if this is an
improvement or not. I don't know the implications of use-modules;
perhaps there's some overhead that I don't know about that isn't
worth it. Or maybe list-index and split-at are less optimal than
than Jay's loop-and-reverse solution.

Just wanting to learn...

Thanks,
Mark
___________________________

(use-modules (srfi srfi-1))

(define-public (split-at-predicate predicate lst)
  "Split a list into 2 lists at the first element that returns #f for
  (PREDICATE previous_element element). Return the two parts as a pair.
  Example: (split-at-predicate < '(1 2 3 2 1)) ==> ((1 2 3) . (2 1))"
  (let ((i (list-index predicate(cdr lst) lst)))
    (if i
        (call-with-values (lambda () (split-at lst (1+ i)))
                          cons)
        `(,lst))))
___________________________

p.s. see the current version for comparison in this post:
http://lists.gnu.org/archive/html/lilypond-devel/2009-06/msg00226.html