Introduction to newLISP/Apply and map

From Wikibooks, open books for an open world
Jump to: navigation, search

Apply and map: applying functions to lists[edit]

Making functions and data work together[edit]

Often, you'll find that you've got some data stored in a list and you want to apply a function to it. For example, suppose that you've acquired some temperature readings from a space probe, and they're stored in a list called data:

(println data)
(0.1 3.2 -1.2 1.2 -2.3 0.1 1.4 2.5 0.3)


How are you going to add these numbers up, and then divide by the total, to find the average? Perhaps you think you could use add, which totals a list of floating-point numbers, but you're not working interactively, so you can't edit the code to read like this:

(add 0.1 3.2 -1.2 1.2 -2.3 0.1 1.4 2.5 0.3)

Since we're holding the data in a symbol called data, we might try this:

(add data)
value expected in function add : data


but no, this doesn't work, because add wants numbers to add, not a list. You could of course do it the hard way and write a loop that works through each item in the list and increases a running total each time:

(set 'total 0)
(dolist (i data)
 (inc total i))
 
(println total)
5.3


This works fine. But newLISP has a much more powerful solution, for this and many other problems: you can treat functions as data and data as functions, so you can manipulate functions as easily as you can manipulate your data. You can just 'introduce' add and the data list to each other, and then stand back and let them get on with it.

There are two important functions for doing this: apply and map.

apply[edit]

apply takes a function and a list, and makes them work together:

(apply add data)
;-> 5.3
(div (apply add data) (length data))
;-> 0.5888888889

and this produces the required result. Here we've treated the add function like any other newLISP list, string, or number, using it as an argument to another function. You don't need to quote it (although you can), because apply is already expecting the name of a function.

map[edit]

The other function that can make functions and lists work together is map, which applies a function to each item of a list, one by one. For example, if you wanted to apply the floor function to each element of the data list (to round them down to the nearest integer) you could combine map, floor, and the data as follows:

(map floor data)
;-> (0 3 -2 1 -3 0 1 2 0)

and the floor function is applied to each element of the data. The results are combined and returned in a new list.

apply and map in more detail[edit]

Both apply and map let you treat functions as data. They have the same basic form:

(apply f l)
(map f l)

where f is the name of a function and l is a list. The idea is that you tell newLISP to process a list using the function you specify.

apply and map use functions on list elements

The apply function uses all the elements in the list as arguments to the function, and evaluates the result.

(apply reverse '("this is a string"))
;-> "gnirts a si siht"

Here, apply looks at the list, which in this case consists of a single string, and feeds the elements to the function as arguments. The string gets reversed. Notice that you don't have to quote the function but you do have to quote the list, because you don't want newLISP to evaluate it before the designated function gets a chance to consume it.

The map function, on the other hand, works through the list, element by element, like a sergeant major inspecting a row of soldiers, and applies the function to each element in turn, using the element as the argument. However, map remembers the result of each evaluation as it goes, collects them up, and returns them in a new list.

So map looks like a control-flow word, a bit like dolist, whereas apply is a way of controlling the newLISP list evaluation process from within your program, calling a function when and where you want it called, not just as part of the normal evaluation process.

If we adapt the previous example for map, it gives a similar result, although the result is a list, not a string:

(map reverse '("this is a string"))
;-> ("gnirts a si siht")

Because we've used a list with only one element, the result is almost identical to the apply example, although notice that map returns a list whereas, in this example, apply returns a string:

(apply reverse '("this is a string"))
;-> "gnirts a si siht"

The string has been extracted from the list, reversed, and then stored in another list created by map.

In the next example:

(map reverse '("this" "is" "a" "list" "of" "strings"))
;-> ("siht" "si" "a" "tsil" "fo" "sgnirts")

you can clearly see that map has applied reverse to each element of the list in turn, and returned a list of the resulting reversed strings.

Write one in terms of the other?[edit]

To illustrate the relationship between these two functions, here is an attempt at defining map in terms of apply:

(define (my-map f l , r) 
 ; declare a local variable r to hold the results
 (dolist (e l)
   (push (apply f (list e)) r -1)))

We're pushing the result of applying a function f to each list item to the end of a temporary list, and then relying on push returning the list at the end, just as map would do. This works, at least for simple expressions:

(my-map explode '("this is a string"))
;-> ("t" "h" "i" "s" " " "i" "s" " " "a" " " "s" "t" "r" "i" "n" "g")
 
(map explode '("this is a string"))
;-> (("t" "h" "i" "s" " " "i" "s" " " "a" " " "s" "t" "r" "i" "n" "g"))

This example illustrates why map is so useful. It's an easy way to transform all the elements of a list without the hassle of working through them element by element using a dolist expression.

More tricks[edit]

Both map and apply have more tricks up their sleeves. map can traverse more than one list at the same time. If you supply two or more lists, newLISP interleaves the elements of each list together, starting with the first elements of each list, and passes them as arguments to the function:

(map append '("cats " "dogs " "birds ") '("miaow" "bark" "tweet"))
;-> ("cats miaow" "dogs bark" "birds tweet")

Here the first element of each list is passed as a pair to append, followed by the second element of each list, and so on.

This weaving together of strands is a bit like knitting with lists. Or like doing up a zip.

apply has a trick too. A third argument indicates how many of the preceding list's arguments the function should use. So if a function takes two arguments, and you supply three or more, apply comes back and makes another attempt, using the result of the first application and another argument. It continues eating its way through the list until all the arguments are used up.

To see this in action, let's first define a function that takes two arguments and compares their lengths:

(define (longest s1 s2)
 (println s1 " is longest so far, is " s2 " longer?") ; feedback
 (if (>= (length s1) (length s2))                     ; compare 
     s1
     s2))

Now you can apply this function to a list of strings, using the third argument to tell apply to use up the arguments two strings at a time:

(apply longest '("green" "purple" "violet" "yellow" "orange"
"black" "white" "pink" "red" "turquoise" "cerise" "scarlet"
"lilac" "grey" "blue") 2)
green is longest so far, is purple longer?
purple is longest so far, is violet longer?
purple is longest so far, is yellow longer?
purple is longest so far, is orange longer?
purple is longest so far, is black longer?
purple is longest so far, is white longer?
purple is longest so far, is pink longer?
purple is longest so far, is red longer?
purple is longest so far, is turquoise longer?
turquoise is longest so far, is cerise longer?
turquoise is longest so far, is scarlet longer?
turquoise is longest so far, is lilac longer?
turquoise is longest so far, is grey longer?
turquoise is longest so far, is blue longer?
turquoise


It's like walking along the beach and finding a pebble, and holding on to it until an even better one turns up.

apply also gives you a way of working through a list and applying a function to each pair of items:

(apply (fn (x y)
    (println {x is } x {, y is } y)) (sequence 0 10) 2)
x is 0, y is 1
x is 1, y is 2
x is 2, y is 3
x is 3, y is 4
x is 4, y is 5
x is 5, y is 6
x is 6, y is 7
x is 7, y is 8
x is 8, y is 9
x is 9, y is 10


What's happening here is that the value returned by the println function is the second member of the pair, and this becomes the value of the first element of the next pair.

Lispiness[edit]

This thing about passing around the names of functions as if they were bits of data is very characteristic of newLISP, and it's very useful. You will find many uses for it, sometimes using functions that you don't think will be useful with map. Here, for example, is set working hard under the control of map:

(map set '(a b) '(1 2))
;-> a is 1, b is 2
 
(map set '(a b) (list b a))
;-> a is 2, b is 1

This construction gives you another way to assign values to symbols in parallel, rather than sequentially. (You can use swap as well.)

Some uses of map are simple:

(map char (explode "hi there"))
;-> (104 105 32 116 104 101 114 101)
 
(map (fn (h) (format "%02x" h)) (sequence 0 15))
;-> ("00" "01" "02" "03" "04" "05" "06" "07" "08" "09" "0a" "0b" "0c" "0d" "0e" "0f")

Others can become quite complex. For example, given a string of data in this form, stored in a symbol image-data:

("/Users/me/graphics/file1.jpg" "  pixelHeight: 978" "  pixelWidth: 1181")

the two numbers can be extracted with:

(map set '(height width) (map int (map last (map parse (rest image-data)))))

currying[edit]

Some of the built-in newLISP functions do things with other functions. An example is curry, which creates a copy of a two-argument function and creates a single-argument version with a pre-determined first argument. So if a function f1 was often called like this:

(f1 arg1 arg2)

you can use curry to make a new function f2 that has a ready-to-use built-in arg1:

(set 'f2 (curry f1 arg1))

now you can forget about that first argument, and just supply the second one to f2:

(f2 arg2)

Why is this useful? Consider the dup function, which often gets used to insert multiple blank spaces:

(dup { } 10)

Using curry, you can create a new function called, say, blank, that's a special version of dup that always gets called with a blank space as the string:

(set 'blank (curry dup { }))

Now you can use (blank n):

(blank 10)
;->           ; 10 spaces

curry can be useful for creating temporary or anonymous functions with map:

(map (curry pow 2) (sequence 1 10))
;-> (2 4 8 16 32 64 128 256 512 1024)
 
(map (fn (x) (pow 2 x)) (sequence 1 10)) ; equivalent
;-> (2 4 8 16 32 64 128 256 512 1024)

But avoid using curry on destructive functions like inc, for example:

(setq a-list-of-pairs (sequence 2 10 2))
;-> (2 4 6 8 10)
(map (curry inc 3) a-list-of-pairs) ;-> you would expect (5 7 9 11 13), instead you get
;-> (5 9 15 23 33)
; one proper way to get every number incremented by 3 would be
(map (curry + 3) a-list-of-pairs)
;-> (5 7 9 11 13)
; or if you insist in using inc, then provide a copy of the increment so the reference inc gets doesn't mess up things
(map (curry inc (copy 3)) a-list-of-pairs)
;-> (5 7 9 11 13)