[plt-scheme] evaluation order for fold
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