Hello,
So recently I've mentioned various combinators inspired by other
languages. For example, 'linrec' and 'binrec' come from Joy.
SRFI-1 has tons of recursive procedures. But the combinators I have in
my stockpile didn't seem to fit naturally or weren't general enough to
handle more than a couple. Also, when I *could* make them fit, in some
cases they allocated more than they should have.
There's a bunch of procedures in SRFI-1 which, in their "fast path"
unary case take as parameters: (procedure list). For example, filter,
map, find, etc. I decided to target those initially.
Here's the combinator I came up with
(define (list-recursion f g h)
(define (rec fun lst)
(let loop ((lst lst))
(if (null? lst)
(f lst)
(let ((hd (car lst))
(tl (cdr lst)))
(let ((val (fun hd)))
(if val
(g loop val hd tl)
(h loop val hd tl)))))))
rec)
Given that combinator, here's some of the procedures that can be defined
(fast path case):
(define filter (list-recursion null cons-head-recur recur))
(define map (list-recursion null cons-val-recur cons-val-recur))
(define for-each (list-recursion null recur recur))
(define find-tail (list-recursion false done-list recur))
(define take-while (list-recursion null cons-head-recur done-null))
(define drop-while (list-recursion null recur done-list))
(define any (list-recursion false done-true recur))
(define every (list-recursion true recur done-false))
(define count (list-recursion zero add-1-recur recur))
The second and third parameters are "control flow" combinators:
(define (cons-head-recur loop vl hd tl)
(cons hd (loop tl)))
(define (cons-val-recur loop vl hd tl)
(cons vl (loop tl)))
(define (recur loop vl hd tl)
(loop tl))
(define (add-1-recur loop vl hd tl)
(+ 1 (loop tl)))
(define (done x)
(lambda (loop vl hd tl)
x))
(define done-null (done '()))
(define done-true (done #t))
(define done-false (done #f))
(define done-zero (done 0))
(define done-list
(lambda (loop vl hd tl)
(cons hd tl)))
And a few standard constant functionals:
(define (null x) '())
(define (true x) #t)
(define (false x) #f)
(define (zero x) 0)
These are available as a library in dharmalab:
http://github.com/dharmatech/dharmalab/raw/master/misc/list-fp.sls
Ed
