cirfu

(define (range start end)
(if (<= start end)
(cons start (range (+ start 1) end))
'()))

i want to do (filter (condition) (list))

i started trying and u sed:
(define (replace x)
(if (< x 100)
x
'()))

so i can do:
(map replace (range 95 105))
(95 96 97 98 99 () () () () () ())

(define (replace x)
(cond
((< x 100) x)))

(91 92 93 94 95 96 97 98 99 #<void> #<void> #<void> #<void> #<void>)

but how do i return nothing if at all if x >= 100 ?

btw when implementing filter, should i use map?

michele.simionato

filter is a builtin in R6RS Scheme and it is provided
as a library in other Schemes, so no point in reiventing
it, except for pedagogical reasons.

Somebody with a Python background will like Phil Bewig's
list-of macro for list comprehensions (http://
schemephil.googlepages.com/list-of.html).
In terms of it you can write

(list-of x (x range 95 105) (< x 100))


You cannot implement filter in terms of map, but you can
in terms of fold. See
http://www.r6rs.org/final/html/r6rs-...l#node_idx_212

Michele Simionato

pjb

cirfu <circularfunc@yahoo.se> writes:


Do you want to _filter_ or do you want to _replace_?
Don't you think there's a fundamental difference between the two?


Just don't accumulate nothing. That means, don't use map, since map
always accumulate one-for-one element.


No.

(define (filter predicate list)
(cond
((null? list) '())
((predicate (car list)) ; we keep it
(cons (car list) (filter predicate (cdr list))))
(else ; we lose it
(filter predicate (cdr list)))))

Now, since the first one is not a terminal recusive call, transform it
to have only terminal recursive calls.

--
__Pascal Bourguignon__ http://www.informatimago.com/

NEW GRAND UNIFIED THEORY DISCLAIMER: The manufacturer may
technically be entitled to claim that this product is
ten-dimensional. However, the consumer is reminded that this
confers no legal rights above and beyond those applicable to
three-dimensional objects, since the seven new dimensions are
"rolled up" into such a small "area" that they cannot be
detected.

leppie

In your opinion (and anyone else wanting to comment), would a simple
call to reverse be acceptable, or would it be better to go the set-
cdr! route given a definition as the following:

(define (filter proc l)
(let f ((l l)(a '()))
(if (null? l)
(reverse a)
(let ((e (car l)))
(if (proc e)
(f (cdr l) (cons e a))
(f (cdr l) a))))))

Cheers

leppie

phil bewig

Thanks for the mention.

Derrick Eddington pointed out that the macro evaluates some of the
parameters twice, which is a problem if they involve side effects.
Here is the current version of list-of, which is not yet on the page
the Michele pointed to:

(define-syntax list-of
(syntax-rules (range in is)
((_ "aux" expr base)
(cons expr base))
((_ "aux" expr base
(x range first past step) clauses ...)
(let ((f first) (p past) (s step))
(let ((more? (if (positive? step) < >)))
(let loop ((z f))
(if (more? z p)
(let ((x z))
(list-of "aux" expr
(loop (+ z s))
clauses ...))
base)))))
((_ "aux" expr base
(x range first past) clauses ...)
(let ((f first) (p past))
(let ((s (if (< first past) 1 -1)))
(list-of "aux" expr base
(x range f p s) clauses ...))))
((_ "aux" expr base (x in xs) clauses ...)
(let loop ((z xs))
(if (null? z)
base
(let ((x (car z)))
(list-of "aux" expr
(loop (cdr z))
clauses ...)))))
((_ "aux" expr base (x is y) clauses ...)
(let ((x y))
(list-of "aux" expr base clauses ...)))
((_ "aux" expr base pred? clauses ...)
(if pred?
(list-of "aux" expr base clauses ...)
base))
((_ expr clauses ...)
(list-of "aux" expr '() clauses ...))))

pascal costanza

There is a (very old) paper about this question, see
http://doi.acm.org/10.1145/181889.181892

Executive summary:

* You should use reverse!, not reverse.

* If you do so, it doesn't really matter which approach to choose.
set-cdr! is theoretically better, but in practice, reverse! turns out to
be better. (This is in the context of Common Lisp implementations, where
rplacd and nreverse are compared, which correspond to set-cdr! and
reverse! Whether the result is still valid for Scheme implementations on
modern architectures is hard to tell, but at least this paper is a good
hint.)

From the conclusions of that paper:

"The rplacd approach to creating an output list has a theoretical speed
advantage, but as a practical matter this to be overwhelmed by the fact
that nreverse is a system function that can be hand coded by the system
implementors. As a result, the nreverse approach is probably fastest in
most Lisp implementations. Even if the rplacd approach is faster in a
given Lisp, it is unlikely to be much faster. Therefore, since the
nreverse approach is simpler and clearer, it is the best approach to use
in almost every situation."

And later:

"In closing, I would like to note that the very best thing to do is to
avoid writing code that conses lists. Whenever possible, you should use
standard parts of Common Lisp that do the consing for you. In
particular, you should use functions like replace, map, reduce, remove,
union, etc. whenever they are appropriate. Beyond this, you should take
advantage of looping macro packages such as loop and Series."

Common Lisp's reduce corresponds to fold-left and fold-right in Scheme,
and there are probably corresponding procedures in Scheme for the other
mentioned functions.

For the sake of completeness, a Common Lisp loop solution would look
like this:

(defun filter (predicate list)
(loop for element in list
when (funcall predicate element)
collect element))


I don't know what a Series version would look like, since I don't enough
experience with that.

Pascal

--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/

leppie

Thanks

leppie

vend

Do you redefine 'list'? I know that the standards allow it, but it
looks like the equivalent of writing i+++++i in C.

pjb

Vend <vend82@virgilio.it> writes:

I'm a Common Lisper.

--
__Pascal_Bourguignon__ _ Software patents are endangering
() ASCII ribbon against html email (o_ the computer industry all around
/\ 1962O20I=1.100 //\ the world http://lpf.ai.mit.edu/
2001:my($f)=`fortune`; V_/ http://petition.eurolinux.org/