On Mon, Jun 15, 2009 at 3:03 AM, Joe Neeman<joenee...@gmail.com> wrote:
>
> On Mon, Jun 8, 2009 at 3:59 AM, Mark Polesky <markpole...@yahoo.com> wrote:
>>
>> my version:
>>
>> (define-public (split-at-predicate predicate lst)
>> "Split LST (into 2 lists) at the first element that returns #f for
>> (PREDICATE previous_element element), and return the 2 new lists as a
>> pair. Example: (split-at-predicate < '(1 2 3 2 1)) ==> ((1 2 3) 2 1)"
>> (if (< (length lst) 2)
>> (cons lst '())
>> (let loop ((L0 (list (car lst))) (L1 (cdr lst)))
>> (cond ((null? L1) (cons L0 L1))
>> ((predicate (car (last-pair L0))
>
> 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))))))
_______________________________________________
lilypond-devel mailing list
lilypond-devel@gnu.org
http://lists.gnu.org/mailman/listinfo/lilypond-devel
