WARNING! UGLY CODE AHEAD
I'm trying to work through the 1st Graham Book and I've come across an
exercise where he asks you to write a simple routine to walk a list of
numbers pair-wise and test that every pair matches (n, n + 1). The kicker is
that you are supposed to do this recursively, iteratively and using mapc and
return. I was pretty happy with my recursive solution and I thought the
iterative version was OK but the version with mapc and return is a mess.
It's not that it doesn't run and produce an answer, it's just that it's butt
ugly and I can't seem to fix that. I've got that feeling that there is
something obvious that will come to me in a second, but I've f***** around
with it for an hour and no joy. I keep producing variations on the same ugly
theme.
At this point I've got my head wedged so badly on one approach that I'm
probably incapable of ever seeing what's right in front of me. So if you can
stand the pain of looking at this crap, please help:
Welcome to Darwin!
[dslstat-bvi1-254:~] chrisg% cd Lisp/
[dslstat-bvi1-254:~/Lisp] chrisg% emacs diff
----:---F1 *scratch*
(Fundamental)--L1--All------------------------------------------------------
----------------------------------
Loading disp-table...done
--11:---F1 diff
(Fundamental)--L1--All------------------------------------------------------
----------------------------------
----:---F1 *scratch*
(Fundamental)--L1--All------------------------------------------------------
----------------------------------
Loading disp-table...done
(when (not (= (- y x) 1))
(return nil)))
lst))))
(setf result (mapc #'sub lst))))
(setf result (mapc #'sub lst))))
(values lst1 lst2)))
(defun diff-m (lst)
(let ((lst1)
(lst2)
(result))
(setf result (mapc #'sub lst))))
(defun sub (x y)
(when (not (= (- y x) 1))
(return nil))
--1-:**-F1 diff.lisp (Lisp:COMMON-LISP-USER
:ready)--L28--Bot-----------------------------------------------------------
-----------
> Type :POP to abort.
Type :? for other options.
1 > :pop
? (load "diff.lisp")
;Compiler warnings :
; Unused lexical variable LST1, in DIFF-M.
; Unused lexical variable LST2, in DIFF-M.
; Unused lexical variable RESULT, in DIFF-M.
> Error: Unexpected end of file on #<FILE-CHARACTER-INPUT-STREAM
("/Users/chrisg/Lisp/diff.lisp" [4]) #x5248AB6>
> While executing: CCL::%READ-CHAR-NO-EOF
> Type :POP to abort.
Type :? for other options.
1 > :pop
?
--11:**-F1 *openmcl* (ILISP
:ready)--L32--Bot-----------------------------------------------------------
---------------------------
(do ((i 0 (+ 2 i))
(j 1 (+ 2 j)))
((> i len))
(setf lst1 (append lst1 (list (nth i lst))))
(setf lst2 (append lst2 (list (nth j lst)))))
(values lst1 lst2)))
(defun diff-m (lst)
(let ((lst1)
(lst2)
(result))
(setf result (mapc #'sub lst))))
(defun sub (x y)
(when (not (= (- y x) 1))
(return nil))
--1-:**-F1 diff.lisp (Lisp:COMMON-LISP-USER
:ready)--L25--Bot-----------------------------------------------------------
-----------
> Type :POP to abort.
Type :? for other options.
1 > :pop
? (load "diff.lisp")
;Compiler warnings :
; Unused lexical variable LST1, in DIFF-M.
; Unused lexical variable LST2, in DIFF-M.
; Unused lexical variable RESULT, in DIFF-M.
> Error: Unexpected end of file on #<FILE-CHARACTER-INPUT-STREAM
("/Users/chrisg/Lisp/diff.lisp" [4]) #x5248AB6>
> While executing: CCL::%READ-CHAR-NO-EOF
> Type :POP to abort.
Type :? for other options.
1 > :pop
?
--11:**-F1 *openmcl* (ILISP
:ready)--L32--Bot-----------------------------------------------------------
---------------------------
(result))
(if (null lst)
t
(let ((dif (- (second lst) (first lst))))
(and (= dif 1) (diff-r (rest (rest lst)))))))
(defun diff-i (lst)
(let ((len (1- (length lst))))
(do ((i 0 (+ i 2)))
((>= i len) t)
(when (not (= (- (nth (1+ i) lst) (nth i lst)) 1))
(return nil)))))
> If continued: Retry getting the value of DIFF.LISP.
Type :? for other options.
1 > :pop
? (load "diff.lisp")
;Compiler warnings :
; Unused lexical variable LST1 (2 references), in DIFF-M.
; Unused lexical variable LST2 (2 references), in DIFF-M.
; Unused lexical variable RESULT, in DIFF-M.
> Error: Unexpected end of file on #<FILE-CHARACTER-INPUT-STREAM
("/Users/chrisg/Lisp/diff.lisp" [4]) #x525462E>
> While executing: CCL::%READ-CHAR-NO-EOF
> Type :POP to abort.
Type :? for other options.
1 > :pop
? (load "diff.lisp")
> Error: Unexpected end of file on #<FILE-CHARACTER-INPUT-STREAM
("/Users/chrisg/Lisp/diff.lisp" [4]) #x525F3CE>
> While executing: CCL::%READ-CHAR-NO-EOF
> Type :POP to abort.
Type :? for other options.
1 > :pop
? (load "diff.lisp")
;Compiler warnings :
; Unused lexical variable RESULT, in DIFF-M.
> Error: While compiling SUB :
> Can't RETURN-FROM block : NIL.
> Type :POP to abort.
Type :? for other options.
1 > :pop
? (load "diff.lisp")
;Compiler warnings :
; Unused lexical variable RESULT, in DIFF-M.
#P"/Users/chrisg/Lisp/diff.lisp"
? (diff-m '(1 2 4 5 8 9))
(1 4 8)
? (diff-m '(1 2 4 5 8 7))
(1 4 8)
? (load "diff.lisp")
#P"/Users/chrisg/Lisp/diff.lisp"
? (diff-m '(1 2 4 5 8 9))
(1 4 8)
? (diff-m '(1 2 4 5 8 9))
(1 4 8)
? (sub 1 2)
NIL
`(defun diff-r (lst)
(if (null lst)
t
(let ((dif (- (second lst) (first lst))))
(and (= dif 1) (diff-r (rest (rest lst)))))))
(defun diff-i (lst)
(let ((len (1- (length lst))))
(do ((i 0 (+ i 2)))
((>= i len) t)
(when (not (= (- (nth (1+ i) lst) (nth i lst)) 1))
(return nil)))))
(defun split-list (lst)
(lst1)
(lst2))
(do ((i 0 (+ 2 i))
(j 1 (+ 2 j)))
((> i len))
(setf lst1 (append lst1 (list (nth i lst))))
(setf lst2 (append lst2 (list (nth j lst)))))
(values lst1 lst2)))
(defun diff-m (lst)
(multiple-value-bind (lst1 lst2) (split-list lst)
(mapc #'sub lst1 lst2)))
(defun sub (x y)
(block zap
(when (not (= (- y x) 1))
(return-from zap nil))
t))
--1-:---F1 diff.lisp (Lisp:COMMON-LISP-USER
:ready)--L29--Bot-----------------------------------------------------------
-----------
? (load "diff.lisP")
#P"/Users/chrisg/Lisp/diff.lisP"
? (sub 1 2)
T
? (sub 2 2)
NIL
? (load "diff.lisp")
#P"/Users/chrisg/Lisp/diff.lisp"
? (sub 1 2)
T
? (sub 6 5)
NIL
?
--11:**-F1 *openmcl* (ILISP
:ready)--L112--Bot----------------------------------------------------------
---------------------------
(j 1 (+ 2 j)))
((> i len))
(setf lst1 (append lst1 (list (nth i lst))))
(setf lst2 (append lst2 (list (nth j lst)))))
(values lst1 lst2)))
(defun diff-m (lst)
(multiple-value-bind (lst1 lst2) (split-list lst)
(mapc #'sub lst1 lst2)))
(defun sub (x y)
(block zap
(when (not (= (- y x) 1))
(return-from zap nil))
t))
--1-:---F1 diff.lisp (Lisp:COMMON-LISP-USER
:ready)--L19--Bot-----------------------------------------------------------
-----------
? (load "diff.lisP")
#P"/Users/chrisg/Lisp/diff.lisP"
? (sub 1 2)
T
? (sub 2 2)
NIL
? (load "diff.lisp")
#P"/Users/chrisg/Lisp/diff.lisp"
? (sub 1 2)
T
? (sub 6 5)
NIL
?
--11:**-F1 *openmcl* (ILISP
:ready)--L112--Bot----------------------------------------------------------
---------------------------
(let ((len (1- (length lst))))
(do ((i 0 (+ i 2)))
((>= i len) t)
(when (not (= (- (nth (1+ i) lst) (nth i lst)) 1))
(return nil)))))
(defun split-list (lst)
(let ((len (- (length lst) 1))
(lst1)
(lst2))
(do ((i 0 (+ 2 i))
(j 1 (+ 2 j)))
? (load "diff.lisP")
#P"/Users/chrisg/Lisp/diff.lisP"
? (sub 1 2)
T
? (sub 2 2)
NIL
? (load "diff.lisp")
#P"/Users/chrisg/Lisp/diff.lisp"
? (sub 1 2)
T
? (sub 6 5)
NIL
? (load "diff.lisp")
;Compiler warnings :
; Unused lexical variable L1, in an anonymous lambda form inside DIFF-M.
; Unused lexical variable L2, in an anonymous lambda form inside DIFF-M.
; Undeclared free variable ZAP, in an anonymous lambda form inside DIFF-M.
; Undeclared free variable RETURN-FROM, in an anonymous lambda form inside
DIFF-M.
; Undeclared free variable X, in an anonymous lambda form inside DIFF-M.
; Undeclared free variable Y, in an anonymous lambda form inside DIFF-M.
#P"/Users/chrisg/Lisp/diff.lisp"
? (load "diff.lisp")
;Compiler warnings :
; Undeclared free variable ZAP, in an anonymous lambda form inside DIFF-M.
; Undeclared free variable RETURN-FROM, in an anonymous lambda form inside
DIFF-M.
#P"/Users/chrisg/Lisp/diff.lisp"
? (diff-m '(1 2 4 5 8 9))
(1 4 8)
? (diff-m '(1 2 4 6 8 9))
(1 4 8)
? (load "diff.lisp")
#P"/Users/chrisg/Lisp/diff.lisp"
? (diff-m '(1 2 4 5 8 9))
(1 4 8)
? (diff-m '(1 2 4 8 8 9))
NIL
? (load "diff.lisp")
#P"/Users/chrisg/Lisp/diff.lisp"
;; versions should be provided.
; recursive version doesn't seem to suck
(defun diff-r (lst)
(if (null lst)
t
(let ((dif (- (second lst) (first lst))))
(and (= dif 1) (diff-r (rest (rest lst)))))))
; iteritave version looks a little brute
; forcy but all my iterators look like that
(defun diff-i (lst)
(let ((len (1- (length lst))))
(do ((i 0 (+ i 2)))
((>= i len) t)
(when (not (= (- (nth (1+ i) lst) (nth i lst)) 1))
(return nil)))))
; The wart on the butt
; Seems like there ought to be a
; one-pass version using cons
(defun split-list (lst)
(let ((len (- (length lst) 1))
;; and determine whether each successive pair
;; differs by 1. Recursive, iterative and mapc
;; versions should be provided.
; recursive version doesn't seem to suck
(defun diff-r (lst)
(if (null lst)
t
(let ((dif (- (second lst) (first lst))))
(and (= dif 1) (diff-r (rest (rest lst)))))))
; iteritave version looks a little brute
; forcy but all my iterators look like that
(defun diff-i (lst)
(let ((len (1- (length lst))))
(do ((i 0 (+ i 2)))
((>= i len) t)
(when (not (= (- (nth (1+ i) lst) (nth i lst)) 1))
(return nil)))))
;;; The problem here is to scan a list of numbers
;; and determine whether each successive pair
;; differs by 1. Recursive, iterative and a
;; version using mapc and return should be
;; provided.
;; recursive version doesn't seem to suck
(defun diff-r (lst)
"Tests whether difference between pairs is 1."
(if (null lst)
t
(let ((dif (- (second lst) (first lst))))
(and (= dif 1) (diff-r (rest (rest lst)))))))
;; iteritave version looks a little brute
;; forcy but all my iterators look like that
(defun diff-i (lst)
"Tests whether difference between pairs is 1."
(let ((len (1- (length lst))))
(do ((i 0 (+ i 2)))
((>= i len) t)
(when (not (= (- (nth (1+ i) lst) (nth i lst)) 1))
--1-:---F1 diff.lisp
(Lisp)--L5--Top-------------------------------------------------------------
----------------------------------
;; and determine whether each successive pair
;; differs by 1. Recursive, iterative and a
;; version using mapc and return should be
;; provided.
;; recursive version doesn't seem to suck
(defun diff-r (lst)
"Tests whether difference between pairs is 1."
(if (null lst)
t
(let ((dif (- (second lst) (first lst))))
(and (= dif 1) (diff-r (rest (rest lst)))))))
;; iteritave version looks a little brute
;; forcy but all my iterators look like that
(defun diff-i (lst)
"Tests whether difference between pairs is 1."
(let ((len (1- (length lst))))
(do ((i 0 (+ i 2)))
((>= i len) t)
(when (not (= (- (nth (1+ i) lst) (nth i lst)) 1))
(return nil)))))
;;; The problem here is to scan a list of numbers
;; and determine whether each successive pair
;; differs by 1. Recursive, iterative and a
;; version using mapc and return should be
;; provided.
;; recursive version doesn't seem to suck
(defun diff-r (lst)
"Tests whether difference between pairs is 1."
(if (null lst)
t
(let ((dif (- (second lst) (first lst))))
(and (= dif 1) (diff-r (rest (rest lst)))))))
;; iteritave version looks a little brute
;; forcy but all my iterators look like that
(defun diff-i (lst)
(let ((len (1- (length lst))))
(do ((i 0 (+ i 2)))
((>= i len) t)
(when (not (= (- (nth (1+ i) lst) (nth i lst)) 1))
(return nil)))))
;; The wart on the butt
;; Seems like there ought to be a
;; one-pass version using cons
(defun split-list (lst)
(let ((len (- (length lst) 1))
(lst1)
(lst2))
(do ((i 0 (+ 2 i))
(j 1 (+ 2 j)))
((> i len))
(setf lst1 (append lst1 (list (nth i lst))))
(setf lst2 (append lst2 (list (nth j lst)))))
(values lst1 lst2)))
;; I guess this really isn't so ugly ounce the
;; list has been seperated. I don't know whether
;; it is good style to use annother if so that
;; it returns T instead of lst1 on the true case.
(defun diff-m (lst)
(multiple-value-bind (lst1 lst2) (split-list lst)
(block nil ; must be nil because of requirement to use return
(mapc #'(lambda (x y)
(when (not (= (- y x) 1))
(return nil)))
lst1 lst2))))
-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----== Over 80,000 Newsgroups - 16 Different Servers! =-----
On 12/6/02 1:22 PM, in article ······················@fastq.com, "Chris
Gehlker" <·······@fastq.com> wrote:
WARNING! UGLY CODE AHEAD
I'm trying to work through the 1st Graham Book and I've come across an
exercise where he asks you to write a simple routine to walk a list of
numbers pair-wise and test that every pair matches (n, n + 1). The kicker is
that you are supposed to do this recursively, iteratively and using mapc and
return. I was pretty happy with my recursive solution and I thought the
iterative version was OK but the version with mapc and return is a mess.
It's not that it doesn't run and produce an answer, it's just that it's butt
ugly and I can't seem to fix that. I've got that feeling that there is
something obvious that will come to me in a second, but I've f***** around
with it for an hour and no joy. I keep producing variations on the same ugly
theme.
At this point I've got my head wedged so badly on one approach that I'm
probably incapable of ever seeing what's right in front of me. So if you can
stand the pain of looking at this crap, please help:
;;; The problem here is to scan a list of numbers
;; and determine whether each successive pair
;; differs by 1. Recursive, iterative and a
;; version using mapc and return should be
;; provided.
;; recursive version doesn't seem to suck
(defun diff-r (lst)
"Tests whether difference between pairs is 1."
(if (null lst)
t
(let ((dif (- (second lst) (first lst))))
(and (= dif 1) (diff-r (rest (rest lst)))))))
;; iteritave version looks a little brute
;; forcy but all my iterators look like that
(defun diff-i (lst)
"Tests whether difference between pairs is 1."
(let ((len (1- (length lst))))
(do ((i 0 (+ i 2)))
((>= i len) t)
(when (not (= (- (nth (1+ i) lst) (nth i lst)) 1))
(return nil)))))
;; The wart on the butt
;; Seems like there ought to be a
;; one-pass version using cons
(defun split-list (lst)
(let ((len (- (length lst) 1))
(lst1)
(lst2))
(do ((i 0 (+ 2 i))
(j 1 (+ 2 j)))
((> i len))
(setf lst1 (append lst1 (list (nth i lst))))
(setf lst2 (append lst2 (list (nth j lst)))))
(values lst1 lst2)))
;; I guess this really isn't so ugly ounce the
;; list has been separated. I don't know whether
;; it is good style to use another if so that
;; it returns T instead of lst1 in the true case.
(defun diff-m (lst)
(multiple-value-bind (lst1 lst2) (split-list lst)
(block nil ; must be nil because of requirement to use return
(mapc #'(lambda (x y)
(when (not (= (- y x) 1))
(return nil)))
lst1 lst2))))
-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----== Over 80,000 Newsgroups - 16 Different Servers! =-----
From: Joe Marshall
Subject: Re: Not for the squeamish (corrected)
Date:
Message-ID: <k7imoogq.fsf@ccs.neu.edu>
Chris Gehlker <·······@fastq.com> writes:
> On 12/6/02 1:22 PM, in article ······················@fastq.com, "Chris
> Gehlker" <·······@fastq.com> wrote:
>
> WARNING! UGLY CODE AHEAD
>
> I'm trying to work through the 1st Graham Book and I've come across an
> exercise where he asks you to write a simple routine to walk a list of
> numbers pair-wise and test that every pair matches (n, n + 1).
I would interpret this as meaning than *any* two adjacent elements
must satisfy the requirement.
On 12/6/02 1:57 PM, in article ············@ccs.neu.edu, "Joe Marshall"
<···@ccs.neu.edu> wrote:
> Chris Gehlker <·······@fastq.com> writes:
>
>> On 12/6/02 1:22 PM, in article ······················@fastq.com, "Chris
>> Gehlker" <·······@fastq.com> wrote:
>>
>> WARNING! UGLY CODE AHEAD
>>
>> I'm trying to work through the 1st Graham Book and I've come across an
>> exercise where he asks you to write a simple routine to walk a list of
>> numbers pair-wise and test that every pair matches (n, n + 1).
>
> I would interpret this as meaning than *any* two adjacent elements
> must satisfy the requirement.
Well that's just my bad writing where I thought "pair-wise" made it clear.
What Graham said was"
"Define a function that takes a list of numbers and returns true iff the
difference between each successive pair of them is 1, using
(a) recursion
(b) do
� mapc and return"
Except that now that I look at that "each successive pair" is subject to the
same ambiguity as "pair-wise."
Does the quote make it any clearer for you. I can't tell without trying it
if the mapc portion gets harder or easier.
-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----== Over 80,000 Newsgroups - 16 Different Servers! =-----
From: Joe Marshall
Subject: Re: Not for the squeamish (corrected)
Date:
Message-ID: <el8uol7k.fsf@ccs.neu.edu>
Chris Gehlker <·······@fastq.com> writes:
> On 12/6/02 1:57 PM, in article ············@ccs.neu.edu, "Joe Marshall"
> <···@ccs.neu.edu> wrote:
>
> > I would interpret this as meaning than *any* two adjacent elements
> > must satisfy the requirement.
>
> "Define a function that takes a list of numbers and returns true iff the
> difference between each successive pair of them is 1, using
>
> Does the quote make it any clearer for you. I can't tell without trying it
> if the mapc portion gets harder or easier.
I can tell you that the problem becomes *much* easier (and the
solution more elegant) if you assume that he meant *any* two adjacent
elements rather than only the even and odd elements.
Chris Gehlker wrote:
> Except that now that I look at that "each successive pair" is subject to the
> same ambiguity as "pair-wise."
Yeah, still ambiguous, but if you think about it, he said "each" pair so
in (1 2 3 4) I see three pairs, (1 2)(2 3)(3 4). I would see more, but
he also said "successive".
You know, we had this exercise here on Google a few
months ago, and a fun little thread it was. The mapc-return
version was indeed a hoot, IIRC.
--
kenny tilton
clinisys, inc
---------------------------------------------------------------
""Well, I've wrestled with reality for thirty-five years, Doctor,
and I'm happy to state I finally won out over it.""
Elwood P. Dowd
In article <············@ccs.neu.edu>, Joe Marshall <···@ccs.neu.edu>
wrote:
> Chris Gehlker <·······@fastq.com> writes:
>
> > On 12/6/02 1:22 PM, in article ······················@fastq.com, "Chris
> > Gehlker" <·······@fastq.com> wrote:
> >
> > WARNING! UGLY CODE AHEAD
> >
> > I'm trying to work through the 1st Graham Book and I've come across an
> > exercise where he asks you to write a simple routine to walk a list of
> > numbers pair-wise and test that every pair matches (n, n + 1).
>
> I would interpret this as meaning than *any* two adjacent elements
> must satisfy the requirement.
I don't know. Graham is a big fan of his "group" macro, which spilts up
a list into pairs, triples, etc
-- Bruce
On 12/6/02 3:20 PM, in article
···························@copper.ipg.tsnz.net, "Bruce Hoult"
<·····@hoult.org> wrote:
> In article <············@ccs.neu.edu>, Joe Marshall <···@ccs.neu.edu>
> wrote:
>
>> Chris Gehlker <·······@fastq.com> writes:
>>
>>> On 12/6/02 1:22 PM, in article ······················@fastq.com, "Chris
>>> Gehlker" <·······@fastq.com> wrote:
>>>
>>> WARNING! UGLY CODE AHEAD
>>>
>>> I'm trying to work through the 1st Graham Book and I've come across an
>>> exercise where he asks you to write a simple routine to walk a list of
>>> numbers pair-wise and test that every pair matches (n, n + 1).
>>
>> I would interpret this as meaning than *any* two adjacent elements
>> must satisfy the requirement.
>
> I don't know. Graham is a big fan of his "group" macro, which spilts up
> a list into pairs, triples, etc
Bruce, Wade, Joe, Kenny, Kalle et. al. I have to agree that if you interpret
the problem as "any two adjoining elements" the problem gets much easier. I
also noticed that in the second part, Graham does not say "Don't use
recursion" he merely says "use do." So the second part can be implemented as
a trivial variation of the first part.
I'm really glad, though, that Drew came through with such an elegant
solution to the problem as I misunderstood it. I would hate to have settled
for the solution to an easier problem.
-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----== Over 80,000 Newsgroups - 16 Different Servers! =-----
In article <······················@fastq.com>, Chris Gehlker
<·······@fastq.com> wrote:
>(defun diff-r (lst)
> "Tests whether difference between pairs is 1."
> (if (null lst)
> t
> (let ((dif (- (second lst) (first lst))))
> (and (= dif 1) (diff-r (rest (rest lst)))))))
Except for the odd case where it makes things unclear, I almost
always rewrite:
(if (null ...)
then-part
else-part)
as:
(if lst
else-part
then-part)
This may be one of those cases (because the NULL makes it clear
that LST is a list), or it may not. You decide.
>;; iteritave version looks a little brute
>;; forcy but all my iterators look like that
>(defun diff-i (lst)
> "Tests whether difference between pairs is 1."
> (let ((len (1- (length lst))))
> (do ((i 0 (+ i 2)))
> ((>= i len) t)
> (when (not (= (- (nth (1+ i) lst) (nth i lst)) 1))
> (return nil)))))
Once again, I almost always rewrite:
(when (not test-part)
body-part)
as:
(unless test-part
body-part)
This looks to be one of those cases.
>;; The wart on the butt
>;; Seems like there ought to be a
>;; one-pass version using cons
>(defun split-list (lst)
> (let ((len (- (length lst) 1))
> (lst1)
> (lst2))
> (do ((i 0 (+ 2 i))
> (j 1 (+ 2 j)))
> ((> i len))
> (setf lst1 (append lst1 (list (nth i lst))))
> (setf lst2 (append lst2 (list (nth j lst)))))
> (values lst1 lst2)))
Note that DO has a place to specify a return value (which
defaults to NIL), in the same list that contains the test-part.
Sometimes I make use of it, e.g., when the value of the DO
is bound in a let form. Your DO loop would then become:
(do ((i 0 (+ 2 i))
(j 1 (+ 2 j)))
((> i len) (values lst1 lst2))
(setf lst1 (append lst1 (list (nth i lst))))
(setf lst2 (append lst2 (list (nth j lst)))))
However, you may feel that this rewrite unnecessarily buries
the value returned by the function. I actually agree. Just
wanted to give you some Common Lisp "folklore", as I think
you called it.
On 12/6/02 6:27 PM, in article ·····················@129.59.212.53, "sv0f"
<····@vanderbilt.edu> wrote:
> In article <······················@fastq.com>, Chris Gehlker
> <·······@fastq.com> wrote:
>
>> (defun diff-r (lst)
>> "Tests whether difference between pairs is 1."
>> (if (null lst)
>> t
>> (let ((dif (- (second lst) (first lst))))
>> (and (= dif 1) (diff-r (rest (rest lst)))))))
>
> Except for the odd case where it makes things unclear, I almost
> always rewrite:
> (if (null ...)
> then-part
> else-part)
> as:
> (if lst
> else-part
> then-part)
> This may be one of those cases (because the NULL makes it clear
> that LST is a list), or it may not. You decide.
I've been slavishly following the book here. Your version is better
>> ;; iteritave version looks a little brute
>> ;; forcy but all my iterators look like that
>> (defun diff-i (lst)
>> "Tests whether difference between pairs is 1."
>> (let ((len (1- (length lst))))
>> (do ((i 0 (+ i 2)))
>> ((>= i len) t)
>> (when (not (= (- (nth (1+ i) lst) (nth i lst)) 1))
>> (return nil)))))
>
> Once again, I almost always rewrite:
> (when (not test-part)
> body-part)
> as:
> (unless test-part
> body-part)
> This looks to be one of those cases.
Well Doh <slaps head> of course.
>
>> ;; The wart on the butt
>> ;; Seems like there ought to be a
>> ;; one-pass version using cons
>> (defun split-list (lst)
>> (let ((len (- (length lst) 1))
>> (lst1)
>> (lst2))
>> (do ((i 0 (+ 2 i))
>> (j 1 (+ 2 j)))
>> ((> i len))
>> (setf lst1 (append lst1 (list (nth i lst))))
>> (setf lst2 (append lst2 (list (nth j lst)))))
>> (values lst1 lst2)))
>
> Note that DO has a place to specify a return value (which
> defaults to NIL), in the same list that contains the test-part.
> Sometimes I make use of it, e.g., when the value of the DO
> is bound in a let form. Your DO loop would then become:
> (do ((i 0 (+ 2 i))
> (j 1 (+ 2 j)))
> ((> i len) (values lst1 lst2))
> (setf lst1 (append lst1 (list (nth i lst))))
> (setf lst2 (append lst2 (list (nth j lst)))))
> However, you may feel that this rewrite unnecessarily buries
> the value returned by the function. I actually agree. Just
> wanted to give you some Common Lisp "folklore", as I think
> you called it.
Somehow, in this case I actually think it's a little clearer with the values
at the bottom. The other suggestions were great. Thanks.
-----= Posted via Newsfeeds.Com, Uncensored Usenet News =-----
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
-----== Over 80,000 Newsgroups - 16 Different Servers! =-----
Chris Gehlker wrote:
> WARNING! UGLY CODE AHEAD
>
> ;; The wart on the butt
> ;; Seems like there ought to be a
> ;; one-pass version using cons
> (defun split-list (lst)
> (let ((len (- (length lst) 1))
> (lst1)
> (lst2))
> (do ((i 0 (+ 2 i))
> (j 1 (+ 2 j)))
> ((> i len))
> (setf lst1 (append lst1 (list (nth i lst))))
> (setf lst2 (append lst2 (list (nth j lst)))))
> (values lst1 lst2)))
Well, I wouldn't use mapc under any circumstances, because why suggest a
mapping operation when you're really just executing a 'loop'?
But the function above is occasionally useful; it's a subroutine in an
elegant version of 'merge-sort', for instance. A better way of writing
it is this:
(defun split-list (lst)
(cond ((null lst) (values '() '()))
(t
(multiple-value-bind (evens odds)
(split-list (cdr lst))
(values (cons (car lst) odds) evens)))))
-- Drew McDermott
Chris Gehlker wrote:
> ;; The wart on the butt
> ;; Seems like there ought to be a
> ;; one-pass version using cons
> (defun split-list (lst)
> (let ((len (- (length lst) 1))
> (lst1)
> (lst2))
> (do ((i 0 (+ 2 i))
> (j 1 (+ 2 j)))
> ((> i len))
> (setf lst1 (append lst1 (list (nth i lst))))
> (setf lst2 (append lst2 (list (nth j lst)))))
> (values lst1 lst2)))
>
> ;; I guess this really isn't so ugly ounce the
> ;; list has been separated. I don't know whether
> ;; it is good style to use another if so that
> ;; it returns T instead of lst1 in the true case.
>
> (defun diff-m (lst)
> (multiple-value-bind (lst1 lst2) (split-list lst)
> (block nil ; must be nil because of requirement to use return
> (mapc #'(lambda (x y)
> (when (not (= (- y x) 1))
> (return nil)))
> lst1 lst2))))
(defun diff-m (list)
(let ((prev nil))
(block nil
(mapc (lambda (x)
(unless (or (null prev) (= x (1+ prev)))
(return nil))
(setf prev x))
list)
t)))
might be nearer to what he had in mind. It's still ugly.
Are you sure he intended to forbid using RETURN-FROM instead
of RETURN, by the way?
--
Gareth McCaughan ················@pobox.com
.sig under construc
Chris Gehlker <·······@fastq.com> writes:
> ;; iteritave version looks a little brute
> ;; forcy but all my iterators look like that
> (defun diff-i (lst)
> "Tests whether difference between pairs is 1."
> (let ((len (1- (length lst))))
> (do ((i 0 (+ i 2)))
> ((>= i len) t)
> (when (not (= (- (nth (1+ i) lst) (nth i lst)) 1))
> (return nil)))))
You really shouldn't use NTH like that. It gets slower as the
index gets larger. You then get O(n^2) complexity where you
could have O(n).
You should refer to successively shorter tails of the list
instead. Here is a pretty straight transformation:
(defun diff-i (lst)
"Tests whether difference between pairs is 1."
(do ((rest lst (cddr rest)))
((null (cdr rest)) t)
(when (not (= (- (cadr rest) (car rest)) 1))
(return nil))))
I'd prefer LOOP, though:
(defun diff-i (list)
"Tests whether difference between pairs is 1."
(loop for (first second) on list by #'cddr
always (= (- second first) 1)))
This version is no longer equivalent to the first one, however:
if the list has an odd number of elements, it tries to compare
the last one to NIL, whereas your original function would have
ignored the last element.
Chris Gehlker <·······@fastq.com> writes:
> WARNING! UGLY CODE AHEAD
>
> I'm trying to work through the 1st Graham Book and I've come across an
> exercise where he asks you to write a simple routine to walk a list of
> numbers pair-wise and test that every pair matches (n, n + 1). The kicker is
> that you are supposed to do this recursively, iteratively and using mapc and
> return. I was pretty happy with my recursive solution and I thought the
> iterative version was OK but the version with mapc and return is a mess.
> It's not that it doesn't run and produce an answer, it's just that it's butt
> ugly and I can't seem to fix that. I've got that feeling that there is
> something obvious that will come to me in a second, but I've f***** around
> with it for an hour and no joy. I keep producing variations on the same ugly
> theme.
Well, one thing to exploit is that the mapping functions can take
lists of different length, and stop when they exhaust the smallest list.
I also get away without the (block nil ...) by using return-from, but
that may be cheating :)
That would let you write:
(defun diff-m (lst)
(mapc #'(lambda (x y)
(unless (= (- y x) 1)
(return-from diff-m nil)))
lst (cdr lst))
t)
--
Thomas A. Russ, USC/Information Sciences Institute ···@isi.edu