Ask HN: How to compose two mapping functions into a third?

15 pointsby gruseomvor 18 Jahren16 comments

I'd like a good way to do the following, where "good" means some balance of simple and efficient.

I have a bunch of mapping functions. Each takes an integer interval [START,END] and a function FN to call once for each integer N in the interval, passing two arguments: N and some value computed from N.

For example, say MAP1 works this way, passing N and N+10 to the function provided:

  (defun map1 (fn start end)
    (loop for n from start to end do
       (funcall fn n (+ n 10))))

...so if you gave MAP1 a function that printed out its arguments, you'd get this:

  (map1 (lambda (n val) (format t "~a ~a~%" n val)) 1 3) =>
    1 11
    2 12
    3 13

Now say MAP2 does the same, only instead of N+10 it passes N^2:

  (defun map2 (fn start end)
    (loop for n from start to end do
       (funcall fn n (expt n 2))))

  (map2 (lambda (n val) (format t "~a ~a~%" n val)) 1 3) =>
    1 1
    2 4
    3 9

What I want is a way to make a new mapping function MAP3 that works the same way but composes the computations in MAP1 and MAP2. For simplicity, say I just want to add the values computed by MAP1 and MAP2. Then MAP3 should do this:

  (map3 (lambda (n val) (format t "~a ~a~%" n val)) 1 3) =>
    1 12
    2 16
    3 22

Any nice solutions? The rules are: (1) it's ok to modify the definition of "mapping function", as long as it's simple, and (2) I don't want to have to make a local copy of everything one of these functions does (because the intervals can be large).

Edit: A solution in Common Lisp would be nice, but I'm interested in good approaches to this in general. Perhaps coroutines?

16 comments

nostrademonsvor 18 Jahren

What you want is basically the compiler optimization called deforestation:

http://en.wikipedia.org/wiki/Deforestation_(computer_science)

It's only valid in a pure language, and in a strict language, it has the embarassing side-effect that it can sometimes make non-terminating programs terminate.

silentbicyclevor 18 Jahren

Just a note: you need to quote the parens in the link like so:

http://en.wikipedia.org/wiki/Deforestation_%28computer_scien...

And no, I don't know why this isn't mentioned in the FAQ or (better yet) the formatting options...

flashgordonvor 18 Jahren

actually thanks guys for the great link... going deeper found this paper by Walder (one of the big gurus behind monads).. certainly a great read... was wondering why non-terminating progs would terminate till I read this paper (though thinking about it common sense would explain why)...

http://homepages.inf.ed.ac.uk/wadler/papers/deforest/defores...

gruseomvor 18 Jahren

Thank you. This is interesting and I will have to make time to read Wadler's paper. This part of the program I'm working on is sort of compiler-like, so maybe a technique like that would work. (More likely, though, I'll end up sticking with the less elegant solution I already have, which involves defining two sets of functions rather than just the mapping ones.)

gruseomvor 18 Jahren

Thanks for the replies. Several have pointed out that the unique portions of map1 and map2 are simple functions that operate on scalars and are easily composable. However, this is not true of the actual problem I'm working on. I chose a toy example so I could describe it briefly. Unfortunately, it's misleadingly simple (rather obviously so, in retrospect).

I guess I'll just add that it's essential that all of these be mapping functions (i.e. they take a functional argument that they call back over some range, passing a value computed using that range).

paulgbvor 18 Jahren

You could use lazy lists like (I think) Haskell uses:

  (define (lazy-range start end) ; create a lazy list that returns the next number in the range [start end]
    (if (= start end) (cons start '())
    (cons start
      (delay (lazy-range (add1 start) end)))))

  (define (lazy-map fn lst) ; map a function to every element of a lazy list, returning a lazy list
    (if (empty? lst) '()
      (cons (fn (car lst))
        (delay (lazy-map fn (force (cdr lst)))))))

  (define map1 (curry lazy-map (curry + 10))) ; equivalent to map1 from your example
  (define map2 (curry lazy-map (lambda (x) (expt x 2)))) ; equivalent to map2 from your example

  (define (lazy-list->list lazy) ; convert a lazy list to a list (for printing, etc)
    (if (empty? lazy) '()
      (cons (car lazy) (lazy-list->list (force (cdr lazy))))))

  (lazy-list->list (map1 (map2 (lazy-range 1 10)))) ; example use

Because the lists are lazy, the maps will only be applied as each value is actually needed, like you described.

gruseomvor 18 Jahren

Yes, I'm beginning to think the simple solution to this boils down to some flavor of coroutines/continuations/laziness - basically, the stuff that Scheme has that CL does not.

The reason I find this interesting is that it's the first real problem I've run into where CL didn't have an easy way to do what I want. There are workarounds, of course. But it's interesting to run into a production (as opposed to academic) problem where the elegant solution isn't simply available.

simonbvor 18 Jahren

Have you tried (semi-standard) SERIES?

http://series.sourceforge.net

"A series is a data structure much like a sequence, with similar kinds of operations. The difference is that in many situations, operations on series may be composed functionally and yet execute iteratively, without the need to construct intermediate series values explicitly. In this manner, series provide both the clarity of a functional programming style and the efficiency of an iterative programming style."

gruseomvor 18 Jahren

No, I haven't tried it. In fact, I didn't know it was available open-source. Do you use it? If so, do you like it?

silverlakevor 18 Jahren

You can implement the local transformations for short cut deforestation with CL macros. Then you can easily reuse the technique everywhere. Look up Andy Gill's paper from 1993.

gruseomvor 18 Jahren

Google brings up a few papers from around that time. The closest match looks like "A short cut to deforestation" - is that the one you mean?

http://portal.acm.org/citation.cfm?id=165214

skenney26vor 18 Jahren

Perhaps it would be simpler to pass the interval modifiers as functional arguments:

  (def mapr (f x y . fs)
    (let r (range x y)
      (map f r
             (apply map + (map [map _ r] fs)))))

  arc> (mapr (fn (x y) (prn x " " y)) 1 3 [+ _ 10])
  1 11
  2 12
  3 13
  (1 2 3)

  arc> (mapr (fn (x y) (prn x " " y)) 1 3 [expt _ 2])
  1 1
  2 4
  3 9
  (1 2 3)

  arc> (mapr (fn (x y) (prn x " " y)) 1 3 [+ _ 10] [expt _ 2])
  1 12
  2 16
  3 22
 (1 2 3)

silentbicyclevor 18 Jahren

Abstract out the mapping itself, and then apply the composed transformation from map1 and map2 to it. map1 and map2 don't need to do any looping themselves, just work take an int and return an int.

Think of it in terms of doing all of your transformations in one pass, if that helps.

elijahbuckvor 18 Jahren

I might be missing something here, but what about this (I didn't even attempt to run this)? Basically, just call map1 and map2 with a single-number interval, and then apply the function from map3 to that result. This avoids making a local copy, but does require a lot of function calls.

(defun compmap (fn mapper1 mapper2 start end) (cond ((= start end) '()) (else (cons (fn start (+ (mapper1 start start) (mapper2 start start))) (compmap fn mapper1 mapper2 (+ start 1) end)))))

nadimvor 18 Jahren

www.stackoverflow.com

(no offense)

qqqvor 18 Jahren

map1 and map2 repeat code. abstract this part to a general mapper function:

(loop for n from start to end do

then you will write the content of the first mapping as a function foo and call the general mapper and pass it foo to accomplish the same thing map1 does.

same with map2, except baz instead of foo.

then map3 is easy. call the general mapper again and pass in something like this: (lambda (x) (baz (foo x)))

or actually it looks like you wanted to add the results, so (lambda (x) (+ (baz x) (foo x)))

basically if you define the interesting part of map1 as one individual thing, and ditto for map2, then you can write the combination easily.

i hope that's clear and didn't miss the point somehow.