CODEWITHSUNDEEP
schemeracketbrackets
user23232512
user23232512

Reputation: 33

output of map function?

Hi I am trying to understand the output of the following code

(define p (lambda (x) (lambda (y) (x (x y)))))
(define q (lambda (x) (* x x)))

when I use

(map (p q) (list 1 2 3))

the result is

(1 16 81)

shouldn't the answer be

(1 4 9) ?

Upvotes: 0

Views: 165

Answers (3)

mnemenaut
mnemenaut

Reputation: 820

Francis King's answer is very clear, this is just an extended footnote inspired by it.

Replacing identifiers with mnemonic ones (rewriting q as square) can make it easier to understand code [1]

Procedures as [first-class] values in Scheme [2] are often introduced with examples using lambda:

> (define twelve 12)
> (define square (lambda (x) (* x x)))
> (square twelve)
144
>

just as the characters 12 in the code above are the representation of a Number, the characters (lambda (x) (* x x)) are the representation of a Procedure:
(number? 12) => #t, (procedure? (lambda (x) (* x x))) => #t

Two further code rewritings may be helpful: using the "short-form" define for procedures, and annotating the definition with a type signature (argument and result types):

> (define (square x) (* x x))  ;; Number -> Number
> (square 3)
9

> (define (do-twice f x)       ;; (X -> X) X -> X
    (f (f x)))
> (do-twice square 3)
81

> (map (lambda (x) (do-twice square x))
    '(1 2 3))
(1 16 81)
>

Note that this do-twice does not yet correspond to the p of the question: making this do-twice the first argument of map would require:
(map do-twice (make-list 3 square) '(1 2 3))

Mapping one list needs a function of one argument, so something has to produce the do-twice of (define (do-twice x) (f (f x))) as its value:

> (define (do-twice-with f)    ;; (X -> X) -> (X -> X)
    (define (do-twice x)       ;; X -> X
      (f (f x)))
    do-twice)

> ((do-twice-with square) 3)
81
> (map (do-twice-with square)
    '(1 2 3))
(1 16 81)
>

So do-twice-with is the function p in the question.

do-twice-with requires a function argument (X -> X), but X can be any type, so:

> (define (repeat s)           ;; String -> String
    (string-append s " " s))

> ((do-twice-with repeat) "buffalo")
"buffalo buffalo buffalo buffalo"

and do-twice-with itself has type (X' -> X') (with X' standing for (X -> X)), so can be applied to itself:

> (((do-twice-with do-twice-with) square) 3)
43046721
  
> (((do-twice-with do-twice-with) repeat) "buffalo")   [3]
"buffalo buffalo buffalo buffalo buffalo buffalo buffalo buffalo buffalo buffalo buffalo buffalo buffalo buffalo buffalo buffalo"

((((do-twice-with do-twice-with) do-twice-with) square) 3) is left as an exercise for the reader...

[1] "Naming is perhaps the most powerful abstracting notion we have" [Guy L Steele]

[2] https://walker.cs.grinnell.edu/courses/151.sp04/readings/procedures-as-values.xhtml

[3] https://en.wikipedia.org/wiki/Buffalo_buffalo_Buffalo_buffalo_buffalo_buffalo_Buffalo_buffalo

Upvotes: 0

molbdnilo
molbdnilo

Reputation: 66371

You're mapping (p q) over the list, so start with figuring out what that is.

Using the subsitution method, you get

    (p q)
==> ((lambda (x) (lambda (y) (x (x y)))) q)
==> (lambda (y) (q (q y)))
==> (lambda (y) (q ((lambda (x) (* x x)) y)))
==> (lambda (y) (q (* y y)))
==> (lambda (y) ((lambda (x) (* x x)) (* y y)))
==> (lambda (y) (* (* y y) (* y y)))

so (p q) is a function that takes a number and squares its square.

Upvotes: 1

Francis King
Francis King

Reputation: 1732

Two functions are provided:

(define p (lambda (x) (lambda (y) (x (x y)))))
(define q (lambda (x) (* x x)))

q is a function which takes a number and squares it. p is a function which takes a function x, and returns another function where x is applied twice to y. Please note that in p, that x is in the function location of the forms, and has been highlighted in the listing to show this.

The use of x in both expressions is unfortunately confusing. You can replace any variable in a lambda expression with any other variable, for example function - this is called alpha-conversion - https://en.wikipedia.org/wiki/Lambda_calculus - and you can change the name of any named function to something more sensible. So, I've renamed q to square, the squaring function, and I've renamed p to do-twice.

(define do-twice (lambda (function) (lambda (y) (function (function y)))))
(define square (lambda (x) (* x x)))

It then becomes obvious what is happening when you evaluate do-twice square.

Upvotes: 0

Related Questions