地图功能的输出？

Question

您好，我正在尝试理解以下代码的输出

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

当我使用

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

结果是

(1 16 81)

答案不应该是

(1 4 9) ?

Answer 1

提供两个函数：

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

q 是一个函数，它接受一个数字并将其平方。 p 是一个接受函数 x 和 returns 的函数，其中 x 两次应用于 y。请注意，在 p 中，x 位于窗体的功能位置，并已在清单中突出显示。

不幸的是，在这两个表达式中使用 x 令人困惑。您可以将 lambda 表达式中的任何变量替换为任何其他变量，例如 function - 这称为 alpha 转换 - https://en.wikipedia.org/wiki/Lambda_calculus - 您可以将任何命名函数的名称更改为更合理的名称。因此，我已将平方函数 q 重命名为 square，并将 p 重命名为 do-twice。

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

当你评估 do-twice square.

时发生的事情就变得很明显了

Answer 2

您正在 (p q) 映射列表，因此请先弄清楚那是什么。

使用替换法，你得到

    (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)))

所以 (p q) 是一个函数，它接受一个数字并对其平方进行平方。

Answer 3

Francis King 的很清楚，这只是受其启发的扩展脚注。

将标识符替换为助记符（将q重写为square）可以更容易理解代码[1]

Procedures as [first-class] values in Scheme [2] 经常通过例子介绍 lambda:

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

正如上面代码中的字符12是一个数字的表示，字符 (lambda (x) (* x x)) 是过程的表示：
(number? 12) => #t, (procedure? (lambda (x) (* x x))) => #t

另外两次代码重写可能会有帮助：使用“短格式”define 作为过程，并注释定义带有类型签名（参数和结果类型）：

> (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)
>

注意这个do-twice还没有对应问题的p：这两次 map 的第一个参数需要：
(map do-twice (make-list 3 square) '(1 2 3))

映射一个列表需要一个参数的函数，所以必须产生两次 (define (do-twice x) (f (f x))) 作为其值：

> (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)
>

所以do-twice-with就是问题中的函数p。

do-twice-with 需要函数参数 (X -> X)，但 X 可以是任何类型，因此：

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

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

和 do-twice-with 本身具有类型 (X' -> X')（X' 代表 (X -> X)），所以可以应用于自身：

> (((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) 留作 reader...

练习

[1]“Naming is perhaps the most powerful abstracting notion we have”[盖伊·斯蒂尔]

[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

地图功能的输出？

output of map function?

scheme

brackets

racket