[racket] member et al.

On Thu, Nov 11, 2010 at 11:56 AM, Mark Engelberg
<mark.engelberg at gmail.com> wrote:
> On Thu, Nov 11, 2010 at 9:56 AM, Jay McCarthy <jay.mccarthy at gmail.com> wrote:
>> (define (andmap f l)
>>  (if (empty? l)
>>     #t
>>     (and (f (first l)) (andmap f (rest l)))))
>>
>> If and has to return a boolean, then it leaves space on the stack to
>> check if andmap returns a bool or to convert "truth" to #t. Thus this
>> program goes from constant stack space to linear stack space.
>
> I don't understand this point.
>
> (define (andmap f l)
>  (cond
>   [(empty? l) #t]
>   [(f (first l)) (andmap f (rest l))]
>   [else #f]))
>
> definitely returns a Boolean, while working with both "true
> predicates" and "pseudo predicates", and works in constant stack
> space.
>
> If you really wanted and/or to definitely return booleans, there's no
> reason they couldn't be implemented similarly, like this for a two arg
> version:
> (define-syntax-rule (and x y)
>  (cond
>    [x (if y #t #f)]

This 'if' introduces a stack frame that is not otherwise needed.

Jay

>    [else #f]))
>
> or more like andmap for the multiarg version.  Basically, you end up
> doing one more test (against the final arg) than you would in the
> existing scheme.
>
> With such an implementation of and, you could implement andmap
> directly using and, while getting a guaranteed Boolean.
>
> So I don't see why there's any connection between making things return
> Booleans and tail-call behavior.
>
> Regardless of this point, I think that at least a case has been made
> that there would be value to having member? alongside member, because
> sometimes (especially in Typed Racket) it is useful to express
> predicate intent.
>



-- 
Jay McCarthy <jay at cs.byu.edu>
Assistant Professor / Brigham Young University
http://faculty.cs.byu.edu/~jay

"The glory of God is Intelligence" - D&C 93