CODEWITHSUNDEEP
functionschemerackethigher-order-functions
TheAmateur
TheAmateur

Reputation: 45

Higher-order functions

given, 

(define (reduce f id lis)
    (if (null? lis) id
      (f (car lis) (reduce f id (cdr lis)))))

The length of a list can be defined in terms of reduce (as opposed to using a recursive definition from scratch) as

(define (mylength lis) (reduce  (lambda (x n) (+ 1 n)) 0 lis)).

Define the list function mymap (similar to map) that takes a unary function uf and a list lis in terms of reduce, that is, by determining the corresponding f and id in

(mymap uf lis) = (reduce f id lis),

Recall that mymap returns a list resulting from calling the function on every element in the input list such as (mymap (lambda(x) (* 2 x)) '(1 2 3)) = (2 4 6).

A little Explanation to how this has been done would be helpful, rather than a blatant answer. Thank You.

Upvotes: 0

Views: 281

Answers (1)

Will Ness
Will Ness

Reputation: 71075

we have

(mymap uf lis) = (reduce f id lis) = 
 = (if (null? lis) id
     (f (car lis) (reduce f id (cdr lis))))

which must be equal to 

 = (if null? lis) '()
     (cons (uf (car lis)) (mymap uf (cdr lis))))

matching the corresponding entities, we get

id == '()

and, since (mymap uf lis) = (reduce f id lis), it is also (mymap uf (cdr lis)) = (reduce f id (cdr lis)), so we have

(f x y) = (cons (uf x) y)

Thus, we define

(define (mymap uf xs)   ; multiple `x`-es :)
  (reduce (lambda (x r)
             (cons .... r))
          '()
          xs ))

your reduce is a right fold: its combining function receives an element x of the argument list xs, and the recursive result of working on the rest of list, as r.

r has all the elements of the rest of xs, which were already mapped through uf. All that's left to do to combine the given element x with this recursive result r, is to cons the (uf x) onto r.

It should pose no problem now to complete the definition by writing the actual code in place of the dots .... there.

Upvotes: 1

Related Questions