Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
problem with lat? (TLS 4ed)
308 views
Skip to first unread message
colin howarth
May 29, 2012, 6:12:34 AM5/29/12
to
Hi, I'm just starting out with Scheme (and Lisp) and am going through The Little Schemer.
I'm confused, right at the beginning and wanted to ask, since this seems important (cf. The First Commandment)...
lat? is defined in the book as
(define lat?
(lambda (l)
(cond
((null? l) #t)
((atom? (car l)) (lat? (cdr l)))
(else #f))))
This terminates with #t when l has become the empty list (and all its elements were atoms).
However, it also evaluates to #t if given the empty list to start with.
But atom? is defined as
(define atom?
(lambda (x)
(and
(not (pair? x))
(not (null? x)))))
which says that x must not be null.
My attempt at lat? was
(define lat?
(lambda (l)
(and
((atom? (car l))
(or
(null? (cdr l))
(lat? (cdr l))))))
which reads as "the first element is an atom and the rest is null, or a list of atoms". That works, except when given the empty list, where (car l) batfs. Which isn't much better than returning #t :-)
[I've done a couple of days of Lisp where (car ()) => nil. In Scheme I don't even know how to *type* an empty list yet, so I'm using (cdr '(a)) or (lambda () ())]
So. If you've got this far, I suppose the question is should lat? return #t for an empty list?
I'm confused, right at the beginning and wanted to ask, since this seems important (cf. The First Commandment)...
lat? is defined in the book as
(define lat?
(lambda (l)
(cond
((null? l) #t)
((atom? (car l)) (lat? (cdr l)))
(else #f))))
This terminates with #t when l has become the empty list (and all its elements were atoms).
However, it also evaluates to #t if given the empty list to start with.
But atom? is defined as
(define atom?
(lambda (x)
(and
(not (pair? x))
(not (null? x)))))
which says that x must not be null.
My attempt at lat? was
(define lat?
(lambda (l)
(and
((atom? (car l))
(or
(null? (cdr l))
(lat? (cdr l))))))
which reads as "the first element is an atom and the rest is null, or a list of atoms". That works, except when given the empty list, where (car l) batfs. Which isn't much better than returning #t :-)
[I've done a couple of days of Lisp where (car ()) => nil. In Scheme I don't even know how to *type* an empty list yet, so I'm using (cdr '(a)) or (lambda () ())]
So. If you've got this far, I suppose the question is should lat? return #t for an empty list?
colin howarth
May 29, 2012, 6:34:31 AM5/29/12
to
I should perhaps have mentioned that I'm using Racket (#!r6rs) under Mac OS X.
Message has been deleted
Barry Margolin
May 29, 2012, 9:30:07 AM5/29/12
to
In article <100b32e5-3a4e-42c6...@googlegroups.com>,
In a recursive algorithm, you have to handle the case where the
recursion bottoms out *before* doing the non-terminal processes. You're
doing them in the wrong order.
> [I've done a couple of days of Lisp where (car ()) => nil. In Scheme I don't
> even know how to *type* an empty list yet, so I'm using (cdr '(a)) or (lambda
> () ())]
You can type it as '().
> So. If you've got this far, I suppose the question is should lat? return #t
> for an empty list?
The following should be true for any l1 and l2:
(eqv? (lat? (append l1 l2))
(and (lat? l1) (lat? l2)))
What if l1 or l2 is the empty list, how can you ensure the tautology?
This type of equation is how you generally figure out how to handle
limiting cases like this.
--
Barry Margolin, bar...@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
recursion bottoms out *before* doing the non-terminal processes. You're
doing them in the wrong order.
> [I've done a couple of days of Lisp where (car ()) => nil. In Scheme I don't
> even know how to *type* an empty list yet, so I'm using (cdr '(a)) or (lambda
> () ())]
> So. If you've got this far, I suppose the question is should lat? return #t
> for an empty list?
(eqv? (lat? (append l1 l2))
(and (lat? l1) (lat? l2)))
What if l1 or l2 is the empty list, how can you ensure the tautology?
This type of equation is how you generally figure out how to handle
limiting cases like this.
--
Barry Margolin, bar...@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
colin howarth
May 29, 2012, 4:48:51 PM5/29/12
to
On Tuesday, May 29, 2012 3:30:07 PM UTC+2, Barry Margolin wrote:
> The following should be true for any l1 and l2:
>
> (eqv? (lat? (append l1 l2))
> (and (lat? l1) (lat? l2)))
>
> What if l1 or l2 is the empty list, how can you ensure the tautology?
OK, thanks. I can see that that's nice. But is the "should be true" axiomatic?
> The following should be true for any l1 and l2:
>
> (eqv? (lat? (append l1 l2))
> (and (lat? l1) (lat? l2)))
>
> What if l1 or l2 is the empty list, how can you ensure the tautology?
Say we write a similar function lol?, which says #t if passed a list of lists. And say we have list? corresponding to atom? such that
(list? L) == (not (atom? L) (1)
which is true even for L = '(). Then you might expect
(lol? M) == (not (lat? M)) (2)
But by the logic given above (lol? '()) should also be #t, so that
(lol? (append l1 l2)) == (and (lol? l1) (lol? l2))) (3)
and equation (2) would be false.
WJ
May 29, 2012, 8:10:15 PM5/29/12
to
colin howarth wrote:
> In Scheme I don't even know how to type an empty list yet,
If '(a) is a list with a length of 1, then '() is a list with
a length of 0, i.e., an empty list.
> In Scheme I don't even know how to type an empty list yet,
> so I'm using (cdr '(a))
You have got to be kidding.
If '(a) is a list with a length of 1, then '() is a list with
a length of 0, i.e., an empty list.
Barry Margolin
May 30, 2012, 10:34:02 AM5/30/12
to
In article <c18b20cd-f9a4-41b2...@googlegroups.com>,
defined. For example, 0 is the identity of + so that (+ (+) x y) == (+
(+ x) y), and 1 is the identity of * so that (* (*) x y) == (* (* x) y).
>
> Say we write a similar function lol?, which says #t if passed a list of
> lists. And say we have list? corresponding to atom? such that
>
> (list? L) == (not (atom? L) (1)
>
> which is true even for L = '(). Then you might expect
>
> (lol? M) == (not (lat? M)) (2)
>
> But by the logic given above (lol? '()) should also be #t, so that
>
> (lol? (append l1 l2)) == (and (lol? l1) (lol? l2))) (3)
>
> and equation (2) would be false.
Equation (2) is wrong, because both lat? and lol? should return #f for
the list '(1 (2)), i.e. any list containing both atoms and lists.
colin howarth <co...@howarth.de> wrote:
> On Tuesday, May 29, 2012 3:30:07 PM UTC+2, Barry Margolin wrote:
>
> > The following should be true for any l1 and l2:
> >
> > (eqv? (lat? (append l1 l2))
> > (and (lat? l1) (lat? l2)))
> >
> > What if l1 or l2 is the empty list, how can you ensure the tautology?
>
> OK, thanks. I can see that that's nice. But is the "should be true"
> axiomatic?
This is how the "identity" value of an associative function is typically
> On Tuesday, May 29, 2012 3:30:07 PM UTC+2, Barry Margolin wrote:
>
> > The following should be true for any l1 and l2:
> >
> > (eqv? (lat? (append l1 l2))
> > (and (lat? l1) (lat? l2)))
> >
> > What if l1 or l2 is the empty list, how can you ensure the tautology?
>
> OK, thanks. I can see that that's nice. But is the "should be true"
> axiomatic?
defined. For example, 0 is the identity of + so that (+ (+) x y) == (+
(+ x) y), and 1 is the identity of * so that (* (*) x y) == (* (* x) y).
>
> Say we write a similar function lol?, which says #t if passed a list of
> lists. And say we have list? corresponding to atom? such that
>
> (list? L) == (not (atom? L) (1)
>
> which is true even for L = '(). Then you might expect
>
> (lol? M) == (not (lat? M)) (2)
>
> But by the logic given above (lol? '()) should also be #t, so that
>
> (lol? (append l1 l2)) == (and (lol? l1) (lol? l2))) (3)
>
> and equation (2) would be false.
the list '(1 (2)), i.e. any list containing both atoms and lists.
colin howarth
May 31, 2012, 4:49:51 AM5/31/12
to
On Wednesday, May 30, 2012 4:34:02 PM UTC+2, Barry Margolin wrote:
> In article <c18b20cd-f9a4-41b2...@googlegroups.com>,
> colin howarth <co...@howarth.de> wrote:
>
> > On Tuesday, May 29, 2012 3:30:07 PM UTC+2, Barry Margolin wrote:
> >
> > > The following should be true for any l1 and l2:
> > >
> > > (eqv? (lat? (append l1 l2))
> > > (and (lat? l1) (lat? l2)))
> > >
> > > What if l1 or l2 is the empty list, how can you ensure the tautology?
> >
> > OK, thanks. I can see that that's nice. But is the "should be true"
> > axiomatic?
>
> This is how the "identity" value of an associative function is typically
> defined. For example, 0 is the identity of + so that (+ (+) x y) == (+
> (+ x) y), and 1 is the identity of * so that (* (*) x y) == (* (* x) y).
Thanks, I was hoping it was something like that. TBH, I knew that stuff 25 yrs ago...
> In article <c18b20cd-f9a4-41b2...@googlegroups.com>,
> colin howarth <co...@howarth.de> wrote:
>
> > On Tuesday, May 29, 2012 3:30:07 PM UTC+2, Barry Margolin wrote:
> >
> > > The following should be true for any l1 and l2:
> > >
> > > (eqv? (lat? (append l1 l2))
> > > (and (lat? l1) (lat? l2)))
> > >
> > > What if l1 or l2 is the empty list, how can you ensure the tautology?
> >
> > OK, thanks. I can see that that's nice. But is the "should be true"
> > axiomatic?
>
> This is how the "identity" value of an associative function is typically
> defined. For example, 0 is the identity of + so that (+ (+) x y) == (+
> (+ x) y), and 1 is the identity of * so that (* (*) x y) == (* (* x) y).
(sigh)
> > [...] Then you might [foolishly] expect
> >
> > (lol? M) == (not (lat? M)) (2)
> >
>
> > (lol? M) == (not (lat? M)) (2)
> >
>
> Equation (2) is wrong, because both lat? and lol? should return #f for
> the list '(1 (2)), i.e. any list containing both atoms and lists.
ouch. Ok, I am shamed into accepting that '() can be considered an empty list of anything. Ie. an empty list of atoms as well as an empty list of lists, or whatever. But I'm pleased because now I'm happy with lat? and can carry on with TLS, along with its First Commandment :-)
> the list '(1 (2)), i.e. any list containing both atoms and lists.
0 new messages