CODEWITHSUNDEEP
dictionaryfunctional-programmingscheme
David
David

Reputation: 753

Map application in scheme

I am trying to understand procedure application and computation order in scheme. I have the following code:

(map map (list map) (list (list list)) '(((a b c))))

I know that map should be applied in the following manner: 

(map procedure list list ...)

If more than one list is given, then they must all be the same length. The result of the above line is:

(map map (list map) (list (list list)) '(((a b c))))
=> ((((a) (b) (c))))

Why? What is the order of computation here? I tried to break the line, obviously I am missing something here: 

(list map)
=> (#<Function map>)     ;list1
(list (list list))
=> ((#<Function list>))  ;list2
'(((a b c)))
=> (((a b c)))           ;list3

Upvotes: 1

Views: 89

Answers (1)

Sylwester
Sylwester

Reputation: 48765

The correct use of map is:

(map proc-of-n-arity list1 ... listn)

Thus if you have one list your proc should take one argument. The evaluation order is not defined so the expression for listn can come before the evaluation of map (which evaluates to a procedure). You can test this by having arguments that does side effects and see that it usually is left to right or right to left.

Nested expression, as if proc-of-n-arity were a complex procedure call with its own expressions is evaluated before map is applied since it is needed to be evaluated before thus even if the order ir unknown we know it is a depth first evaluation.

So back to your strange expression:

(map map (list map) (list (list list)) '(((a b c))))

Here map evaluates to a procedure. It evaluates map as a procedure for it's first argument and it evaluates the rest of the expressions such that you get (#<map>) ((#<list>)) and of course (((a b c))), all one element lists. Thus you should expect a one element list back with the result of:

(map map (list list) '((a b c)))

This evaluates both map as a procedures and the lists as (#<list>) and ((a b c)). Since it is a one element list one would again expect a one element list back with the result of:

(map list '(a b c))

This evaluates map and list as procedures and the second argument as (a b c). You'l get a list with 3 elements with the result of list with one of each, ie. ((a) (b) (c))

Going back to the fact that this was one element in a map application we know map will make a list with it like (((a) (b) (c))) and it is the one element in the outer map which also gets to be in a list and thus ((((a) (b) (c)))) is the end result.

Know that this result can be done much easier with:

(list (list (map list (caar '(((a b c)))))))

List argument length

Note that the restriction on the same length list is true for map in R5RS and R6RS, but SRFI-1 will stop at the shortest list. eg:

#!r6rs

(import (except (rnrs base) map)
        (only (srfi :1) map circular-list))

(map + '(1 2 3) (circular-list 2)) ; ==> (3 4 5)

SRFI-1 will become a standard list library in R7RS Large.

Upvotes: 2

Related Questions