Subject: Re: Detecting Infinite Looping From: Henry Thompson <ht@xxxxxxxxxxxxxxx> Date: 29 Jan 1998 09:40:24 +0000 |
node-list-contains? plus a slight change in perspective will do the trick for you (although if my memory serves, n-l-c? isn't defined in JADE -- a definition is offered at the end of this message). There are two idioms for building up a list recursively from an inductive definition: The simple version, isomorphic to the inductive definition of the desired result (substitute appropriately for P, F, NEXT, BASE (define f1 (lambda (x) (if P BASE (cons F (f1 NEXT))))) The substitutions P: (null? x) BASE: '() F: (car x) NEXT: (cdr x) would copy the top level of a list Note this formulation is not trivially tail-recursive. The alternative, tail-recursive, formulation, is as follows: (define f1 (lambda (x) (f1a x BASE))) (define f1a (lambda (x result) (if P result (f1a NEXT (append result (list F)))))) This computes exactly the same result, but has the advantages that it's tail recursive AND you have the result available to you as you go. It may be less efficient (because of the append), but if you don't care about order you can say (cons (F x) result) instead, or reverse the result in one go at the end. So the following would give a useful result on a circular list (not possible in DSSSL, I know): P: (or (null? x)(member (car x) result)) BASE: '() F: (car x) NEXT: (cdr x) This is in fact a misleading definition, because it bails at the first duplicate list ELEMENT, which is not what I said, but the paradigm should be clear by now, I hope! ht PS. You can see the tail recursion more clearly by using a named 'let' (define f1 (lambda (arg) (let loop ((x arg) (result BASE)) (if P result (loop NEXT (append result (list F))))))) -- Henry S. Thompson, Human Communication Research Centre, University of Edinburgh 2 Buccleuch Place, Edinburgh EH8 9LW, SCOTLAND -- (44) 131 650-4440 Fax: (44) 131 650-4587, e-mail: ht@xxxxxxxxxxxxxxx URL: http://www.cogsci.ed.ac.uk/~ht/ DSSSList info and archive: http://www.mulberrytech.com/dsssl/dssslist
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: Detecting Infinite Looping, Richard Light | Thread | RE: Detecting Infinite Looping, Pawson, David |
Re: Detecting Infinite Looping, Richard Light | Date | RE: Detecting Infinite Looping, Gavin Nicol |
Month |