I found the following "linear update" procedures that take procedural
arguments:
append-map! f clist1 clist2 ... -> value
map! f list1 clist2 ... -> list
filter! pred list -> list
partition! pred list -> [list list]
remove! pred list -> list
take-while! pred clist -> list
span! pred list -> [list list]
break! pred list -> [list list]
delete! x list [=] -> list
delete-duplicates! list [=] -> list
alist-delete! key alist [=] -> alist
lset-union! = list1 ... -> list
lset-intersection! = list1 list2 ... -> list
lset-difference! = list1 list2 ... -> list
lset-xor! = list1 ... -> list
lset-diff+intersection! = list1 list2 ... -> [list list]
I looked at the implementation of filter! in the sample implementation,
which is very elegant:
(define (filter! pred lis)
(check-arg procedure? pred filter!)
(let lp ((ans lis))
(cond ((null-list? ans) ans) ; Scan looking for
((not (pred (car ans))) (lp (cdr ans))) ; first cons of result.
;; ANS is the eventual answer.
;; SCAN-IN: (CDR PREV) = LIS and (CAR PREV) satisfies PRED.
;; Scan over a contiguous segment of the list that
;; satisfies PRED.
;; SCAN-OUT: (CAR PREV) satisfies PRED. Scan over a contiguous
;; segment of the list that *doesn't* satisfy PRED.
;; When the segment ends, patch in a link from PREV
;; to the start of the next good segment, and jump to
;; SCAN-IN.
(else (letrec ((scan-in (lambda (prev lis)
(if (pair? lis)
(if (pred (car lis))
(scan-in lis (cdr lis))
(scan-out prev (cdr lis))))))
(scan-out (lambda (prev lis)
(let lp ((lis lis))
(if (pair? lis)
(if (pred (car lis))
(begin (set-cdr! prev lis)
(scan-in lis (cdr lis)))
(lp (cdr lis)))
(set-cdr! prev lis))))))
(scan-in ans (cdr ans))
ans)))))
This sample implementation can be screwed up if pred captures and
replays its continuation.
My understanding of the term "linear update" (and I have to admit I
haven't found very many references to this term other than in SRFI 1) is
that having pred capture and replay its continuation is a violation of
the "linear update" assumption that the only pointer to the list
argument lis (and presumably all following pairs in the list, although I
don't remember whether this is stated explicitly in SRFI 1) is lis
itself, so having the pred procedure capture and replay its continuation
violates the "linear update" assumption, and a user doing such a thing
can go pound sand.
My question: Is this analysis correct?
My secondary question: Should one restrict the programming of filter! to
be the same as filter just to "save" someone who decides to use call/cc
in pred?
Brad
