From: ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe)
Newsgroups: comp.lang.scheme
Subject: Re: Help with problem
Date: 7 Apr 92 06:53:33 GMT
Organization: Comp Sci, RMIT, Melbourne, Australia

In article <9209812.29806@mulga.cs.mu.OZ.AU>, simong@mundil.cs.mu.OZ.AU (Simon Alexander GREGORY) writes:
> Can anybody write me a procedure to construct this?
> Given this list '( 1 0 0 1 0 0 0 1 0 0 0 0 1 1)
> Result wanted is: ( 1 ( 0 0 ) 1 ( 0 0 0 ) 1 ( 0 0 0 0 ) 1 1)

The request is a bit more general; what is wanted is a function

	(cluster test? list) -> clustered list

By the way, the result is a VERY odd sort of shape.  It generally pays
to _try_ to make lists homogenous.  A much better result shape would be

	((unit 1) (group 0 0) (unit 1) (group 0 0 0)
	 (unit 1) (group 0 0 0 0) (unit 1) (unit 1))

So I'm going to write two functions:  nasty-cluster and nice-cluster.

It's all done with the aid of case analysis.

	(nasty-cluster test? list)

What are the possible (legal) cases for list ?
    a.  It is null
    b.  It is a pair

If it is a pair, what are the cases?

    b1. The first element passes the test (acts like 1)
    b2. The first element does not pass the test (acts like 0).

So we know that a good structure to try is

	(define (nasty-cluster test? list)
	    (if (null? list)
		<result for case a>
		(if (test? (car list))
		    <result for case b1>
		    <result for case b2>)))

What's the result for case a?  Another empty list.

What's the result for case b1?  The "1" at the front is to be consed
onto the result of clustering the rest of the list.

What's the result for case b2?  The "0"s at the front (we know there is
at least one) are to be picked off.  We'll use a function
	(take-until test? list)
to do that.  take-until returns the longest possible prefix of list
none of whose elements satisfies test.  That list is to be consed onto
the result of clustering the rest of the list after those "0"s.  We'll
use a function
	(drop-until test? list)
to skip over the "0"s.

	(define (take-until test? list)
	    (if (or (null? list)
		    (test? (car list)))
		'()
		(cons (car list) (take-until test? (cdr list)))))

	(define (drop-until test? list)
	    (if (or (null? list)
		    (test? (car list)))
		list
		(drop-until test? (cdr list))))

So we now have

	(define (nasty-cluster test? list)
	    (if (null? list)
		'()
		(if (test? (car list))
		    (cons (car list)
			  (nasty-cluster test? (cdr list)))
		    (cons (take-until test? list)
			  (nasty-cluster test? (drop-until test? list)) )) ))

All done by kindness.  It is possible to improve this so that it calls the
test? procedure exactly once per element, but that's just obvious
optimisation, and may not be worthwhile in your application.

Here's nice-cluster:

	(define (nice-cluster test? list)
	    (if (null? list)
		'()
		(if (test? (car list))
		    (cons (list 'unit (car list))
			  (nice-cluster test? (cdr list)))
		    (cons (cons 'group (take-until test? list))
			  (nice-cluster test? (drop-until test? list)) )) ))

Before you run away with the idea that I'm being a bit picky here;
what if some lists can satisfy the test?  With the "nasty" version,
you may have to dig really hard to tell the units from the groups;
with the "nice" version it's really obvious.

-- 
I am writing a book on debugging aimed at 1st & 2nd year CS students using
C/Modula/Pascal-like languages.  Please send suggestions (other than "you
_must_ cite "C Traps and Pitfalls") to ok@goanna.cs.rmit.oz.au