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

[Jay Anderson]

On Mon, Jun 15, 2009 at 3:03 AM, Joe Neeman<address@hidden> wrote:
>
> On Mon, Jun 8, 2009 at 3:59 AM, Mark Polesky <address@hidden> 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))))))