Bengt Kleberg <bengtk@damek.kth.se> wrote:
+---------------
| Note that the real problem demands ... the use of (cons ..) in the
| construction of the _list_ of results. Ie, don't use an accumulator to
| make that part of the code tail-recursive. As you can see it is ok to use
| an accumulator for _one_ of the results.
| The toy example: Given a list '( 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 0) I want
| to get a result like this '(3 5 3 2). Ie, add the ones until you reach a 0,
| then start anew.
+---------------

Interesting coincidence! Just last night I had occasion to write some code
(as part of a small assembler for a weird RISC) that does something almost
identical, except the sub-results needed to be lists, too. That is, assuming
"0" is the magic delimiter and given a list '(1 2 3 0 5 0 5 2 1), return
((1 2 3) (5) (5 2 1)).  My solution was one tail-recursive routine, inside
a driver that special-cased null input:

  (define MAGIC-TOKEN 0)                      ; or whatever
  (define (DELIM-TEST x) (eq? x MAGIC-TOKEN)) ; or equal? or whatever

  (define (gather-between-delims ls)
    (letrec ((gather
	       (lambda (result partial input)
		 (cond
		   ((null? input)
		    (reverse (cons (reverse partial) result)))
		   ((DELIM-TEST (car input))
		    (gather (cons (reverse partial) result) '() (cdr input)))
		   (else
		    (gather result (cons (car input) partial) (cdr input)))))))
      (if (null? ls)
	ls
	(gather '() '() ls))))

Examples:

  (gather-between-delims '(1 2 3 0 5 0 4 2 1))
   ==> ((1 2 3) (5) (4 2 1))

  (gather-between-delims '(1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 0))
   ==> ((1 1 1) (1 1 1 1 1) (1 1 1) (1 1) ())

You can get Kleberg's "summation" result with:

  (map length (gather-between-delims '(1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 0)))
   ==> (3 5 3 2 0)

Though note that I deliberately chose not to suppress the empty list/count
at the end, since it was significant in my application.


-Rob

p.s. You can see what I was using it for if you replace "0" with ",",
and replace single-digit numbers with various other tokens (and add
a lexer to produce them):

  (define MAGIC-TOKEN #\,)

  (gather-between-delims
    (cdr (tokenize-string "addi t3,a0+1,tbl_end-tbl_beg+1)))
  ==> ((t3) (a0 #\+ 1) (tbl_end #\- tbl_beg #\+ 1))

Now all I need is to map a simple "infix->prefix" over that, and:

  ==> (t3 (+ a0 1) (+ (- tbl_end tbl_beg) 1))

-----
Rob Warnock, 7L-551		rpw3@sgi.com   http://reality.sgi.com/rpw3/
Silicon Graphics, Inc.		Phone: 650-933-1673 [New area code!]
2011 N. Shoreline Blvd.		FAX: 650-933-4392
Mountain View, CA  94043	PP-ASEL-IA