[plt-scheme] evaluation order for fold
Thanks! , i guess i have been doing too much of casual programming.
In (lambda (s r) ....) i was thinking that r will be evaluated inside
the function which
of course is false.
Just to confirm if am still sane , here is the implementation of foldl
and foldr .
(define (foldll f base lst)
(define (fold res lst)
(cond
[(empty? lst) res]
[else (fold (f (first lst) res) (rest lst))]))
(fold base lst))
(define (foldrr f base lst)
(cond
[(empty? lst) base]
[else (f (first lst) (foldrr f base (rest lst)))]))
I was thinking that in foldr , (first lst) to be equivalent to
(search-tree (first lst))
and was expecting it to be evaluated first before the right hand :) .
Sorry for the trouble.
On Mon, Feb 9, 2009 at 7:23 PM, Matthias Felleisen <matthias at ccs.neu.edu> wrote:
>
> Veer, make sure you reset the visited variable for each search. Then play
> with foldl and foldr. But also contrast with map and why you may not like
> it. -- Matthias
>
>
> ;; list of visited trees
> (define visited '())
>
> ;; Tree -> Boolean
> (define (search-tree t)
> (begin (set! visited (cons t visited))
> (printf "~s\n" (first t))
> true))
>
> ;; [Listof Tree] -> [Listof Boolean]
> (define (search-each los )
> (cond
> [(empty? los) empty]
> [(member (first los) visited) (search-each (rest los))]
> [else (cons (search-tree (first los)) (search-each (rest los)))]))
>
> ;; [Listof Tree] -> [Listof Boolean]
> (define (search-each-fold los)
> (foldl (lambda (s r) (if (member s visited) r (cons (search-tree s) r)))
> empty
> los))
>
> ;; [Listof Tree] -> [Listof Boolean]
> (define (search-each-map los) (map search-tree los))
>
> ;; --- run program run
> (define t1 (cons 0 empty))
> (define t2 (cons 1 empty))
> (define t3 (cons 2 empty))
>
> (define l (list t1 t2 t1 t3 t1))
>
> (set! visited '())
> '--plain--
> (search-each l)
>
> (set! visited '())
> '--fold--
> (search-each-fold l)
>
> (set! visited '())
> '--map--
> (search-each-map l)
>
>
>
>
> On Feb 9, 2009, at 2:33 AM, Veer wrote:
>
>> Hello ,
>>
>> Consider following functions :
>>
>> (define (search-each los )
>> (cond
>> [(empty? los) empty]
>> [(member (first los) visited) (search-each (rest los))]
>> [else (cons (search-tree (first los)) (search-each (rest los)))]))
>>
>>
>> and the same above function using foldr :
>>
>> (define (search-each-fold los)
>> (foldr (lambda (s r)
>> (if (member s visited)
>> r
>> (cons (search-tree s) r))) empty los))
>>
>>
>> Also variable 'visited' is global and updated by search-tree function .
>>
>> When given the same input both function produces the result which though
>> correct but are in different order.
>>
>> My question is are these two function equivalent?
>>
>> I see that in the line [else (cons (search-tree (first los))
>> (search-each (rest los)))]))
>> (search-tree (first los)) is evaluated first
>>
>> But the fold example does not seem to follow this.
>>
>> Thanks
>> Veer
>> _________________________________________________
>> For list-related administrative tasks:
>> http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>
>