[plt-scheme] evaluation order for fold

From: Matthias Felleisen (matthias at ccs.neu.edu)
Date: Mon Feb 9 08:53:17 EST 2009

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



Posted on the users mailing list.