defining map in terms of reduce

问题:

I have just picked up John Hughes' essay Why Functional Programming Matters, and i'm trying to follow along using Scheme.

The first higher order function he defines is reduce, which i've defined in Scheme as follows:

(define u-reduce
  (lambda (ff init lst)
    (if (null? lst)
      init
      (ff (car lst) (u-reduce ff init (cdr lst))))))

I can re-create some of the applications of reduce in the essay using this function, however things break apart in the move from reduce to map.

The motivating example is doubleall = reduce doubleandcons nil, where doubleandcons num list = cons (2*num) list.

I am not sure how to translate this into scheme. I can see that the target result can be made with:

(define doubleandcons
  (lambda (lst)
    (if (null? lst)
      '()
      (cons (* 2 (car lst)) (doubleandcons (cdr lst))))))

(doubleandcons '(1 2 3))
> (2 4 6)

However can not see what to pass to reduce to get it to double each element of a list - perhaps because i keep jumping to a version of map (see u-map below) as the solution to the problem.

I can see that init = '(), but not what function to pass in to the ff place to make u-reduce behave like u-map.

(define u-map
  (lambda (ff lst)
    (if (null? lst)
      '()
      (cons (ff (car lst)) (u-map ff (cdr lst))))))

(u-map (lambda (x) (* 2 x)) '(1 2 3))
> (2 4 6)

Is this possible? Or perhaps i'm missing the point?

回答1:

(define u-map
  (lambda (ff lst)
    (reduce (lambda (x y) (cons (ff x) y)) '() lst)))

Folding cons across a list gives you a copy of that list.

回答2:

Common Lisp reduce is a general fold. In Scheme you have fold-right that does elements in order. Your u-reduce works just like a right fold with it's arguments in the same order. Thus the following should work in R6RS/R7RS:

(define (my-map fun lst)
  (fold-right (lambda (x a) (cons (fun x) a)) '() lst))

As you can see I'm using the passed function in an anonymous function to fold-right to do the cons as well.

In other versions of Scheme and Racket you get the same behavior by using SRFI-1: List library, Many implementation has support for it so look in it's documentation how you import/require it.

回答3:

You should define your reduce as explicitly lazy, since the article is all about the importance and utility of laziness.

The usual reduce is a (right) fold, i.e. a catamorphism (cf. Haskell's foldr), but let's define a paramorphism for generality:

(define (para f z lst)
   (if (null? lst)
      z
      (f lst (car lst)      ;; usually, f (cdr lst) (car lst) ...
         (lambda () (para f z (cdr lst))))))

(see also this). We use it like this:

;; doubleall = reduce doubleandcons nil
;;   where  doubleandcons num rest = cons (2*num) rest

(define (doubleall lst) 
   (para doubleandcons '() lst))

(define (doubleandcons lst num rest)   ; ignore input lst
   (cons (* 2 num) (rest)))            ; force the lazy rest

(define (member elt lst)
   (para (lambda (xs x r) 
            (if (equal? x elt) xs (r)))  ; conditionally force, or
         '() lst))                       ;  ignore the rest

(define (mymap f lst)
   (para 
      (lambda (xs x r) 
         (cons (f x) (r)))    ; cons the result of calling f w/ x,
      '() lst))               ;   onto the rest

(define (all pred lst)
   (para
      (lambda (xs x r) 
         (and (pred x) (r)))  ; possibly short-circuit
      #t lst))

You cannot short-circuit with your version because it evaluates the rest before passing it as an argument to the combining function (ff).