(archive 'newLISPer)

January 8, 2006

Apply and map confusion

Filed under: newLISP — newlisper @ 20:30
Tags:

>

Beginners get confused in ways that experts don’t understand. Like anyone learning a language, I’ve met various things in newLISP that confused me for a while. Looking back, I can’t remember exactly what I found difficult about the apply and map functions, because they look a bit easier now than they did. But you’ll probably notice my confusion in what follows.

Both apply and map let you use other 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 the list using the function you specify.

The apply function uses 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 elements of the list, which in this case consists of a single string, and feeds these elements to the function as arguments. The string gets reversed. Notice that we don’t have to quote the function in newLISP to prevent it getting evaluated immediately (although we could do), but we do have to quote the list, because we don’t want newLISP to evaluate it before the designated function gets to 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. (Perhaps I confused myself by using the word ‘apply’ there?) However, map remembers the results of each evaluation as it goes, and returns all the results in a new list.

So map looks like a control-flow word, a bit like dolist, whereas apply seems to be way of controlling the newLISP list evaluation process from within a program.

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

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

Here I’ve confused myself by using a list with only one element, which is why the result is almost identical to the apply example. The string has been extracted from the list, reversed, and then stored in another list created by map. (I think.)

Here’s a better, or at least a simpler, example:

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

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

Write one in terms of the other?

I suspect that either map or apply could be written in terms of the other. For example, this is a first attempt at a version of map defined 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))
    r)

which seems to work, at least for simple expressions:

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

This example illustrates to me why map is so useful, too. It’s an easy way to transform all the elements of a list without the hassle of working through them element by element.

For a while, I didn’t understand why this didn’t work:

(apply reverse '(1 2 3))
;-> list or string expected in function reverse : '1

when this did:

(apply reverse '((1 2 3)))
;-> (3 2 1)

The answer, I think, is that apply sort of ‘de-lists’ the elements of the list before applying the function, so you can’t apply reverse to the first element of the list (1 2 3), because you can’t reverse the number 1. In the correct example, the first element of the list ((123)) is the list (1 2 3), which can be reversed.

More tricks

Both map and apply have more tricks up their sleeves.

map can traverse more than one list. It interleaves the elements of each list together, starting with the first element of each list, and then passes them in order as arguments to the function:

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

I like this weaving together of strands – like knitting with lists.

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 lengths
        s1
        s2))

Now we 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 )

This is the output:

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

“purple” did quite well, until “turquoise” arrived.

(In my experiments running this on a short novel, though, I found that newLISP ran out of call stack space quickly, so I don’t recommend this approach just yet. It’s easier and quicker to scan large lists using dolist.)

Lispiness

This thing about passing around the names of Lisp functions as if they were bits of data is very Lisp-y, and I’m just starting to appreciate how useful it is. You can find it all over the place in newLISP. Here’s a useful function called filter:

(filter integer? '(1 2 3 4.1 5 6.21 7 8 9.12))
;-> (1 2 3 5 7 8)

It strips out any elements that don’t satisfy the integer? predicate.

Advertisements

2 Comments »

  1. >Thanks for this wonderful explanation of map and apply. These two functions go right to the core of what LISP really is and why so many people love it.

    Comment by Anonymous — January 9, 2006 @ 14:31 | Reply

  2. >The stack limit for apply is eliminated in the next version of newLISP 8.7.8.

    Comment by Lutz — January 9, 2006 @ 19:03 | Reply


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: