On Thu, Sep 09, 2004 at 08:23:01AM +0200, Joost van Baal wrote:
> Tot nog toe snap ik 1 ding niet.
> (define (accumulate op initial sequence)
> (if (null? sequence)
> initial
> (op (car sequence)
> (accumulate op initial (cdr sequence)))))
This operation is also called "fold" traditionally (_right_ fold more
precisely). In OCaml:
# List.fold_right (fun x b -> x::b) [] [1; 2; 3; 4];;
- : int list = [1; 2; 3; 4]
(One should prefer the left fold if one has the choice (for example
when op is commutative), because it is tail-recursive.)
One can think of the right fold as the act of "replacing cons by op
and nil by initial".
> (accumulate cons nil (list 1 2 3 4 5))
> geeft
> (1 2 3 4 5)
> (define (even-fibs n)
> (accumulate cons
> nil
> (filter even?
> (map fib
> (enumerate-interval 0 n)))))
>
> hetzelfde als
>
> (define (even-fibs n)
> (filter even?
> (map fib
> (enumerate-interval 0 n))))
>
> ?
Yes, these two functions are extensionally equal (they produce equal
results given equal inputs). The first constructs the list two times
instead of one, though (less efficient in time, more memory usage,
more work for the GC, ...).
As your example shows, (accumulate cons nil) is the identity on
lists [1], i.e. the same as (lambda (x) x) [2]. Exercise left to the
reader: Prove it formally.
[1] I lapsed into MLy notation here. In Lispy languages, you have to
write (lambda (x) (accumulate cons nil x)) . This
non-curryfication is IMHO one of the most irritating "features" of
Lispy languages.
[2] To be painfully precise, it is the same as:
(lambda (x)
(if (list? x)
x
(car #f)))
(If one considers all exceptions as equivalent.)
<<inline: signature.asc>>