problem defining a function using built in filter function
Marvin D. Hernandez
I am working on a program from "How to Design Programs" (page 315 or
http://www.htdp.org/2001-11-21/Book/node114.htm ) let's call it selection,
that should input two lists, call them list-1 and list-2 that outputs a list
that contains those things on list-2 that are also on list-1 (repetitions
are allowed). The original program calls for the list to be list of names
(i.e. symbols, but I am making for a listof X, where X can be anything). I
wrote up the program already, but the original problem called for using the
built in scheme function filter. Here is the original one without using
filter:
;selection: (listof X) (listof X) --> (listof X)
;finds what is common between both lists; repetitions are allowed
(define (selection list-1 list-2)
(local ((define (on-list? element listB)
(cond
[(empty? listB) false]
[else (or (equal? element (first listB)) (on-list? element
(rest listB)))])))
(cond
[(empty? list-2) empty]
[(empty? list-1) empty]
[else
(cond
[(on-list? (first list-2) list-1)
(cons (first list-2) (selection list-1 (rest list-2)))]
[else (selection list-1 (rest list-2))])])))
(define list-A (list 1 2 3 4 5 6 0))
(define list-B (list 4 5 6 6 7 8 9 0))
;test cases
;(selection list-A list-B) = (list 4 5 6 6 0)
;(selection empty list-B) = empty
;(selection list-A empty) = empty
;(selection empty empty) = empty
;(selection list-A (list 33 44 55)) = empty
;(selection (list 33 44 55) list-A) = empty
The built in scheme function filter takes in a unary predicate and uses it
to filter the list. So my problem is how to design a *unary* predicate,
let's call it on-list?, that will essentially look at the first element of
list-2 and return true if it is found on list-1 and false otherwise. My
expectation is to be able to define the function intersection so that it
looks like this:
(define (selection list-1 list-2)
(filter on-list? list-1 list-2))
My problem is that my local definition of on-list? in the working version
above of selection is a binary, not a unary, predicate, so I can't use it.
Is my expectation of how I use filter to define selection unrealistic? For
what it is worth, I have defined a version of filter, called filter-1 that
does take in a binary predicate (it was a previously assigned problem), but
I don't think using this version of filter is what the authors had in mind.
Suggestions welcome!!
Artie Gold
Hell, I've been hacking ugly C++ code all day, so here goes...
(define (selection l1 l2)
(define (is-member? el els)
(if (null? els)
#f
(if (equal? el (car els))
#t
(is-member? el (cdr els)))))
(define (on-list? ls) ;; these lines
(lambda (el) ;; are the key
(is-member? el ls))) ;; to the problem
(filter (on-list? l1) l2))
What's going on here is that my procedure `on-list?' takes a list as an
argument, and returns an anonymous procedure (the lambda) that's closed
within an environment containing the original argument.
This is _important_ and one of the keys to any form of function
programming.
HTH,
--ag
--
Artie Gold -- Austin, TX
ag...@bga.com
"May you keep turning the pages. And may the book never end."
Hrvoje Blazevic
This solution is not in line with the rest of the book material, and is
unnecessary complicated (HtDP does not use local define).
Here's the solution that I used when working through the book (a year ago):
(define (selection l1 l2)
(filter (lambda (x)
(not (empty? (filter (lambda (y) (symbol=? x y)) l1))))
l2))
This works as requested in the book, but you can change the predicate to
equal?.
Further the book wants you to use filter: well -- filter IS the only thing
that is used here :-)
Marvin D. Hernandez
> unnecessary complicated (HtDP does not use local define).
It sure does! I can not recall how the order of topics was in the version
of HtDP that you used last year, but in the hard copy of the book (which
practically matches the online version of the book) local is introduced on
page 259 as "Intermezzo 3: Local Definition and Lexical Scope"
> Here's the solution that I used when working through the book (a year
ago):
>
> (define (selection l1 l2)
> (filter (lambda (x)
> (not (empty? (filter (lambda (y) (symbol=? x y)) l1))))
> l2))
>
> This works as requested in the book, but you can change the predicate to
> equal?.
> Further the book wants you to use filter: well -- filter IS the only thing
> that is used here :-)
Lambda is not introduced at this point in the book (not until page 350
"Intermezzo 4: Defining Functions on the Fly" !!
Thanks -- Marvin
Hrvoje Blazevic
>
> It sure does! I can not recall how the order of topics was in the version
> of HtDP that you used last year, but in the hard copy of the book (which
> practically matches the online version of the book) local is introduced on
> page 259 as "Intermezzo 3: Local Definition and Lexical Scope"
>
We have a misunderstanding here: HtDP uses LOCAL but does not use (or
introduce) local DEFINE as in:
(define xxx ...
(define yyy ...
The reason that HtDP uses LOCAL macro (as opposed to using standard Scheme
let, let*, and letrec) is something I did not understand even after completing
the book.
> > Here's the solution that I used when working through the book (a year
> ago):
> >
> > (define (selection l1 l2)
> > (filter (lambda (x)
> > (not (empty? (filter (lambda (y) (symbol=? x y)) l1))))
> > l2))
> >
> > This works as requested in the book, but you can change the predicate to
> > equal?.
> > Further the book wants you to use filter: well -- filter IS the only thing
> > that is used here :-)
>
> Lambda is not introduced at this point in the book (not until page 350
> "Intermezzo 4: Defining Functions on the Fly" !!
>
You are right about lambda. My standard practice when working through various
books is NOT to use constructs that were not introduced up to that point in
the book. I must have given in to the temptation at this particular exercise
However you can use this code even without lambda (to be fully compliant with
HtDP). Instead of using lambda within lambda, use local within local.
(define (selection l1 l2)
(local ((define (p1 x)
(local ((define (p2 y) (symbol=? x y)))
(not (empty? (filter p2 l1))))))
(filter p1 l2)))
This is exactly the same code as the one above, with the added trouble of
naming both functions.
Marvin D. Hernandez
"Hrvoje Blazevic" <hrvoje....@ri.tel.hr> wrote in message
news:3C9A02C7...@ri.tel.hr...
> "Marvin D. Hernandez" wrote:
> >
> > It sure does! I can not recall how the order of topics was in the
version
> > of HtDP that you used last year, but in the hard copy of the book (which
> > practically matches the online version of the book) local is introduced
on
> > page 259 as "Intermezzo 3: Local Definition and Lexical Scope"
> >
>
> We have a misunderstanding here: HtDP uses LOCAL but does not use (or
> introduce) local DEFINE as in:
>
> (define xxx ...
> (define yyy ...
>
> The reason that HtDP uses LOCAL macro (as opposed to using standard Scheme
> let, let*, and letrec) is something I did not understand even after
completing
> the book.
This is a good question. I recently asked this of Matthias Felleisen and
have not gotten back an answer. I assume it is to avoid some type of
common mistake that he has witnessed with let, let* and letrec; (that is why
the language levels were invented) but even so, the book never mentions let,
let* and letrec so I will have to wait for his answer!
Marvin.
David Rush
> "Hrvoje Blazevic" <hrvoje....@ri.tel.hr> wrote in message
> > let, let*, and letrec) is something I did not understand even after
> completing
> > the book.
>
> This is a good question. I recently asked this of Matthias Felleisen and
> have not gotten back an answer. I assume it is to avoid some type of
> common mistake that he has witnessed with let, let* and letrec; (that is why
> the language levels were invented) but even so, the book never mentions let,
> let* and letrec so I will have to wait for his answer!
This was discussed about a year ago here on cls. You should be able
find it on groups.google.com. IIRC, Shriram did most of the
explaining.
Actually I would appreciate a rehash of that discussion, as it delves
into the subtleties of the difference between top-level define and
letrec. I've started working on implementing a non-RnRS (no mutable
top-level) Scheme, and I'm trying to make sure I've got all the bases
covered.
david rush
--
And Visual Basic programmers should be paid minimum wage :)
-- Jeffrey Straszheim (on comp.lang.functional)
Marvin D. Hernandez
"David Rush" <ku...@bellsouth.net> wrote in message
news:okfwuw5...@bellsouth.net...
I think I found it:
http://groups.google.com/groups?hl=en&ie=ISO-8859-1&oe=ISO-8859-1&threadm=j7
v8zw3retu.fsf%40sun.cs.rice.edu&rnum=1&prev=/groups%3Fq%3Dshriram%2B%2Btop-l
evel%2Bdefine%2Bletrec%2Bgroup:comp.lang.scheme.*%26hl%3Den%26ie%3DISO-8859-
1%26oe%3DISO-8859-1%26selm%3Dj7v8zw3retu.fsf%2540sun.cs.rice.edu%26rnum%3D1
Marvin
Al Petrofsky
> > "Hrvoje Blazevic" <hrvoje....@ri.tel.hr> wrote in message
> > > The reason that HtDP uses LOCAL macro (as opposed to using
> > > standard Scheme let, let*, and letrec) is something I did not
> > > understand even after completing the book.
>
> find it on groups.google.com. IIRC, Shriram did most of the
> explaining.
>
> Actually I would appreciate a rehash of that discussion, as it
> delves into the subtleties of the difference between top-level
> define and letrec. I've started working on implementing a non-RnRS
> (no mutable top-level) Scheme, and I'm trying to make sure I've got
> all the bases covered.
That discussion included a couple flawed ways to implement local on
top of r5rs. Below I will show an interesting differently flawed
method. A previously discussed method is this:
(define-syntax local
(syntax-rules (define)
((_ ((define var init) ...) . body)
(let ((var 'undefined) ...)
(set! var init)
...
(let () . body)))))
The problem with this is the error reporting: if a variable's
initializer attempts to use a variable that does not precede it, no
error is signaled.
If you are coding functionally, i.e. if the body and initializers do
not use set! on the locally defined variables, and if you assume that
letrec does good error reporting, then I think the following version
of local would work, and would signal attempts to use variables
prematurely:
(define-syntax local
(syntax-rules (define)
((_ () . body)
(let () . body))
((_ ((define var1 init1) (define var init) ...) . body)
(letrec ((var1 init1) (var #f) ...)
(set!-values (var ...)
(local ((define var init) ...)
(values var ...)))
(let () . body)))))
This creates n-minus-one extra bindings for the nth variable, and sets
the values of all of them to the result of the variable's initializer.
With some tedious syntax-rules hacking, this could be made to first
convert any (define (f . args) . body) definitions into standard
(define f (lambda args . body)) form. Set!-values can be written like
so:
(define-syntax set!-values
(syntax-rules ()
((set!-values (var ...) exp)
(let* ((vals (call-with-values (lambda () exp) list))
(vals (begin (set! var (car vals))
(cdr vals)))
...)
'unspecified))))
-al
Shriram Krishnamurthi
> The reason that HtDP uses LOCAL macro (as opposed to using standard
> Scheme let, let*, and letrec) is something I did not understand even
> after completing the book.
We wanted a binding form that let a programmer move a group of
top-level definitions into a lexical context without changing their
meaning. Unfortunately (and ironically), internal DEFINE does not
have this property. That is, the scope of the definitions changes
when you move it into an internal context. (Convincing yourself of
this is left as an exercise to the programmer -- if you can't come up
with an example, you shouldn't be using internal DEFINE!)
In short, you can take a group of definitions such as
(define (f x) ...)
(define-struct g (a b c))
(define h ...)
and move them into a local definition:
(local
[(define (f x) ...)
(define-struct g (a b c))
(define h ...)]
...)
and they would preserve their meaning.
LOCAL is a kind of "sweet spot" definition construct. It does
definitions sequentially, mimicking LET*, but it also binds
recursively, mimicking LETREC. Therefore, the only time you would not
want to use LOCAL was when you were writing something like
(let ([x y]
[y x])
...)
where both X and Y are bound outside. I don't ever write that! Not
to mention, if you were developing code incrementally, you wouldn't be
able to write that at the top-level and get the desired semantics.
For more detail, you would do well to see the old thread on this,
featuring some geezer signing off as 'shriram. Thanks to Marvin for
dreging up a reference (quoting from his message):
http://groups.google.com/groups?hl=en&ie=ISO-8859-1&oe=ISO-8859-1&threadm=j7
v8zw3retu.fsf%40sun.cs.rice.edu&rnum=1&prev=/groups%3Fq%3Dshriram%2B%2Btop-l
evel%2Bdefine%2Bletrec%2Bgroup:comp.lang.scheme.*%26hl%3Den%26ie%3DISO-8859-
1%26oe%3DISO-8859-1%26selm%3Dj7v8zw3retu.fsf%2540sun.cs.rice.edu%26rnum%3D1
Shriram
--
Shriram Krishnamurthi
Assistant Professor of Computer Science
Brown University
Al Petrofsky
> LOCAL is a kind of "sweet spot" definition construct. It does
> definitions sequentially, mimicking LET*, but it also binds
> recursively, mimicking LETREC. Therefore, the only time you would not
> want to use LOCAL was when you were writing something like
>
> (let ([x y]
> [y x])
> ...)
>
> where both X and Y are bound outside. I don't ever write that!
What about (let ((x (+ x 1))) . <body>)? I suppose you never use that
either, but I think it's much more common than (let ((x y) (y x))
. <body>).
-al
Hrvoje Blazevic
Thanks!
However, you could probably avoid this kind of questions, if this text was
included in the book, maybe as appendix.
As it stands now, my only conclusion was that:
a) this construct serves some obscure didactic purpose that I was not able to
fathom
b) that the syntax is ugly (too verbose)
Hrvoje
Joe Marshall
"Shriram Krishnamurthi" <sk...@cs.brown.edu> wrote in message
news:w7d1yec1k...@cs.brown.edu...
> Hrvoje Blazevic <hrvoje....@ri.tel.hr> writes:
>
> > The reason that HtDP uses LOCAL macro (as opposed to using standard
> > Scheme let, let*, and letrec) is something I did not understand even
> > after completing the book.
>
> We wanted a binding form that let a programmer move a group of
> top-level definitions into a lexical context without changing their
> meaning. Unfortunately (and ironically), internal DEFINE does not
> have this property. That is, the scope of the definitions changes
> when you move it into an internal context.
I'd like a binding form that lets programmers move a group of
internal definitions out of a lexical context without changing
their meaning. Unfortunately (and ironically), top level DEFINE
does not have this property. That is, the scope of the definitions
changes when you place them at top level.
Shriram Krishnamurthi
> However, you could probably avoid this kind of questions, if this text was
> included in the book, maybe as appendix.
Actually, we almost never seem to get this question. I'm not sure
it's bothersome enough to try avoiding!
> As it stands now, my only conclusion was that:
> a) this construct serves some obscure didactic purpose that I was not able to
> fathom
> b) that the syntax is ugly (too verbose)
As you seem to have implicitly divined, this doesn't belong in the
main text of the book, because HtDP isn't trying to teach Scheme, nor
is it about Scheme. My sense of most students who use LOCAL is that
- none of them failed to understand its purpose
- none of them found the syntax particularly cumbersome
because of the context in which they saw it. Maybe these remarks
don't apply to the handful who had seen Scheme before.
Hrvoje Blazevic
>
> As you seem to have implicitly divined, this doesn't belong in the
> main text of the book, because HtDP isn't trying to teach Scheme, nor
> is it about Scheme. My sense of most students who use LOCAL is that
>
> - none of them failed to understand its purpose
> - none of them found the syntax particularly cumbersome
>
> because of the context in which they saw it. Maybe these remarks
> don't apply to the handful who had seen Scheme before.
>
Exactly, as it stands now, I was left hanging -- (sort of) waiting till the
end of the book, to be told why LOCAL.
Hrvoje
Alwyn
"Joe Marshall" <prunes...@attbi.com> wrote:
>
> I'd like a binding form that lets programmers move a group of
> internal definitions out of a lexical context without changing
> their meaning. Unfortunately (and ironically), top level DEFINE
> does not have this property. That is, the scope of the definitions
> changes when you place them at top level.
Pascal has a very similar problem. Perhaps it is not a good idea for a
procedure to contain other procedures.
Alwyn
Shriram Krishnamurthi
Thomas Bushnell, BSG
Edmund GRIMLEY EVANS
> http://groups.google.com/groups?hl=en&ie=ISO-8859-1&oe=ISO-8859-1&threadm=j7
> v8zw3retu.fsf%40sun.cs.rice.edu&rnum=1&prev=/groups%3Fq%3Dshriram%2B%2Btop-l
> evel%2Bdefine%2Bletrec%2Bgroup:comp.lang.scheme.*%26hl%3Den%26ie%3DISO-8859-
> 1%26oe%3DISO-8859-1%26selm%3Dj7v8zw3retu.fsf%2540sun.cs.rice.edu%26rnum%3D1
If the semantics of internal definitions (current definition:
http://www.swiss.ai.mit.edu/~jaffer/r5rs_7.html#SEC46 ) were to be
changed, making
(... (define var1 init1) ... exps ...)
equivalent to
(... (let ((var1 <undefined>) ...) (set! var1 init1) ... exps ...))
what would break, and would local definitions then be equivalent
to LOCAL?
(I'm using <undefined> as in
http://www.swiss.ai.mit.edu/~jaffer/r5rs_9.html#SEC80 .)
Edmund
Marvin D. Hernandez
After much thought, I came up with the version in line with what I
originally wanted:
(define (selection list-1 list-2)
(local ((define (on-list? element)
(local ((define (on-list?-helper a-list)
(cond
[(empty? a-list) false]
[else (or (eq? (first a-list) element) (on-list?-helper (rest
a-list)))])))
(on-list?-helper list-1))))
(filter on-list? list-2)))
Thanks for the original help -- Marv
Shriram Krishnamurthi
> If the semantics of internal definitions (current definition:
> http://www.swiss.ai.mit.edu/~jaffer/r5rs_7.html#SEC46 ) were to be
> changed [...]
Unless I'm missing something, all you're doing is using the R5RS
expansion of LETREC in terms of LET + SET!. But internal definitions
already turn into LETREC, so I don't see that you've changed anything
at all. (As to what's wrong with making internal definitions into
LETREC, pls see the old thread.)
Edmund GRIMLEY EVANS
> Unless I'm missing something, all you're doing is using the R5RS
> expansion of LETREC in terms of LET + SET!.
No, I don't think so. I'm saying make
(... (define var1 init1) ... exps ...)
equivalent to
(... (let ((var1 <undefined>) ...) (set! var1 init1) ... exps ...))
The R5RS expansion of LETREC makes
(... (define var1 init1) ... exps ...)
equivalent to
(... (let ((var1 <undefined>) ...)
(let ((temp1 init1) ...)
(set! var1 temp1)
...
exps ...)))
The R5RS expansion of LETREC is cunningly designed to prevent any
<init> from referring to the value of any <var>. That makes sense for
LETREC - we want the variables to be defined in parallel - but I don't
understand why internal definitions have to be restricted in this way,
particularly if the alternative definition is backwardly compatible
with the R5RS definition and usefully equivalent to LOCAL, which is
what I'm asking.
Edmund