"map" 是否一定会产生额外的嵌套级别？
Does "map" necessarily produce an additional level of nesting?
使用嵌套 map 是否会自动创建另一层嵌套？这是我使用的一个基本示例：
; One level
(map (lambda (x1)
"Hi")
'(1))
; Two levels
(map (lambda (x1)
(map (lambda (x2)
"Hi")
'(1)))
'(1))
; Three levels
(map (lambda (x1)
(map (lambda (x2)
(map (lambda (x3)
"Hi")
'(1)))
'(1)))
'(1))
; Four levels
(map (lambda (x1)
(map (lambda (x2)
(map (lambda (x3)
(map (lambda (x4)
"Hi")
'(1)))
'(1)))
'(1)))
'(1))
("Hi")
(("Hi"))
((("Hi")))
(((("Hi"))))
或者，是否有任何反例，其中添加另一个 map 不会产生额外的嵌套？我遇到了 'getting' 如何 map 添加另一个级别的问题。例如，对于第一级：
(map (lambda (x1)
"Hi")
'(1))
我知道列表中有一个元素，列表中 'for each element' -- 我们将 return 元素 "Hi" 放在列表中的那个位置，所以第一关我们得到 ("Hi").
但是，例如，如何从列表 ("Hi") 中获得第二级的嵌套列表？我知道我已经问了很多与 map 和嵌套相关的问题，但希望如果我能理解从 1 级别到 2 的过程，我就能弄清楚其余的...... .
map 收集所有函数调用的 return 值，并将它们包装在另一个列表中。
如果函数 return 是一个列表，您将得到一个列表列表。
因此，如果您有嵌套地图，您总是会得到嵌套列表作为最终结果。并且每一层映射都会增加另一层嵌套。
请注意，只有当您实际 return 计算每个级别的 map 值时，这才是正确的。你可以用它做其他事情，例如
;; Two levels
(map (lambda (x1)
(length (map (lambda (x2)
"Hi")
'(1))))
'(1))
这将 return (1)
map 将为该列表中的每个元素return 一个列表。让我们通过一个多地图示例来展示嵌套是如何发挥作用的。
首先，让我们对数字序列做一个 map，然后对它们“什么都不做”。也就是说，只是 return 来自输入的元素：
(map (lambda (x) x)
'(1 2 3))
; (1 2 3)
在这一点上，可能很容易认为如果我们添加另一个 map 就不会出现另一层嵌套，因为这里我们没有 'nested' 输入列表。它只是 'stayed' 在 (1 2 3).
但是如果我们添加一个外层，我们可以看到这是如何发生的：
(map (lambda (ignore-me)
(map (lambda (x) x)
'(1 2 3)))
'(1))
; (( 1 2 3 ))
只有一个 'outer-element' 很难看到这一点，但是，让我们添加 5 个外部元素并使其更容易发现：
(map (lambda (ignore-me)
(map (lambda (x) x)
'(1 2 3)))
'(5 5 5 5 5))
;(
; (1 2 3)
; (1 2 3)
; (1 2 3)
; (1 2 3)
; (1 2 3)
;)
这里我们可以看到每个 外部元素——它们有五个——我们正在return“内部结果”——它在上面的例子中是(1 2 3)。如果我们再次做同样的事情，这次产生两个额外的外部循环，我们可以看到类似的结果：
(map (lambda (ignore-me1)
(map (lambda (ignore-me2)
(map (lambda (x) x)
'(1 2 3)))
'(5 5 5 5 5)))
'(2 2))
; (
; ((1 2 3) (1 2 3) (1 2 3) (1 2 3) (1 2 3))
; ((1 2 3) (1 2 3) (1 2 3) (1 2 3) (1 2 3))
; )
一对一
您的示例包括 (map (lambda (x) x) ...)
(map (lambda (ignore-me)
(map (lambda (x) x) ; <- no-op
'(1 2 3)))
'(1))
((1 2 3))
它“很难看到”，因为内部 map 本质上是空操作。 map 在输入和输出之间创建 1:1 关系，对映射过程的作用没有任何意见。如果映射过程 return 是单个元素、列表或非常嵌套的列表，则没有关系 -
(map (lambda (ignore-me)
'(1 2 3))
'(foo))
((1 2 3))
(map (lambda (_)
'(((((really nested))))))
'(1 2 3))
((((((really nested)))))
(((((really nested)))))
(((((really nested))))))
或者使用一些 ascii 可视化 -
(define (fn x) (+ x x))
(map fn '(1 2 3))
; \ \ \
; \ \ (fn 3)
; \ \ \
; \ (fn 2) \
; \ \ \
; (fn 1) \ \
; \ \ \
; output: '(2 4 6)
你是否应该选择 map 映射程序内部到另一个 map 调用 -
(map (lambda (...)
(map ...)) ; <- nested map
...)
适用相同的规则。每个 map 输出与其输入列表具有 1:1 关系。我们可以想象 map 的类型以获得更多见解 -
map : ('a -> 'b, 'a list) -> 'b list
-------- ------- -------
\ \ \_ returns a list of type 'b
\ \
\ \__ input list of type 'a
\
\__ mapping procedure, maps
one element of type 'a
to one element of type 'b
正在执行映射
作为学习练习，实施 map 以深入了解其工作原理非常有用 -
(define (map fn lst)
(if (null? lst)
'()
(cons (fn (car lst))
(map fn (cdr lst)))))
(map (lambda (x)
(list x x x x x))
'(1 2 3))
((1 1 1 1 1)
(2 2 2 2 2)
(3 3 3 3 3))
如您所见，map 对 lst 中的元素类型或 fn 的 return 值是什么没有意见。 map 直接将列表的 car 传递给 fn 并将其 cons 放入列表的 cdr 的递归结果中。
附加映射
我们应该查看的另一个相关程序是 append-map -
append-map : ('a -> 'b list, 'a list) -> 'b list
-------------- ------ ------
\ \ _ returns 类型为 'b 的列表
\ \_ 类型为 'a 的输入列表
\
\_ 映射函数，地图
'a 类型的一个元素
到 <b>LIST</b> 类型为 'b
的元素
这里唯一的区别是映射过程预期 return 一个 list 元素，而不仅仅是单个元素。这样，append-map在输入列表和输出列表之间创建了1:many关系。
(append-map (lambda (x)
(list x x x x x))
'(1 2 3))
(1 1 1 1 1 2 2 2 2 2 3 3 3 3 3)
append-map 的这个特性就是它有时被称为 flatmap 的原因，因为它“扁平化”了一层嵌套 -
(append-map (lambda (x)
(map (lambda (y)
(list x y))
'(spade heart club diamond)))
'(J Q K A))
((J spade)
(J heart)
(J club)
(J diamond)
(Q spade)
(Q heart)
(Q club)
(Q diamond)
(K spade)
(K heart)
(K club)
(K diamond)
(A spade)
(A heart)
(A club)
(A diamond))
reader的后续练习：
- 如果我们在上面的例子中用
append-map 换取 map，输出会是什么？
- 用另一种或两种方式定义
map。验证正确的行为
- 根据
map 定义 append-map。不使用 map. 重新定义
松散打字
Scheme 是一种无类型语言，因此列表的内容不需要是同质的。尽管如此，以这种方式考虑 map 和 append-map 还是很有用的，因为类型有助于传达函数的行为方式。以下是 Racket 提供的更准确的类型定义 -
(map proc lst ...+) → list?
proc : procedure?
lst : list?
(append-map proc lst ...+) → list?
proc : procedure?
lst : list?
这些要宽松得多，确实反映了您实际可以编写的松散程序。例如-
(append-map (lambda (x)
(list 'a-symbol "hello" 'float (* x 1.5) 'bool (> x 1)))
'(1 2 3))
(a-symbol "hello" float 1.5 bool #f a-symbol "hello" float 3.0 bool #t a-symbol "hello" float 4.5 bool #t)
可变映射和追加映射
你在上面的类型中看到那些...+了吗？为了简单起见，我一直隐藏了一个重要的细节，直到现在为止。 map 的可变参数接口意味着它可以接受 1 个 或更多 个输入列表 -
(map (lambda (x y z)
(list x y z))
'(1 2 3)
'(4 5 6)
'(7 8 9))
((1 4 7) (2 5 8) (3 6 9))
(append-map (lambda (x y z)
(list x y z))
'(1 2 3)
'(4 5 6)
'(7 8 9))
(1 4 7 2 5 8 3 6 9)
reader的后续练习：
- 定义可变参数
map
- 定义可变参数
append-map
一点 lambda 演算
您了解 lambda 演算。您知道 (lambda (x y z) (list x y z) 与 list 相同吗？这被称为 Eta reduction -
(map list '(1 2 3) '(4 5 6) '(7 8 9))
((1 4 7) (2 5 8) (3 6 9))
(append-map list '(1 2 3) '(4 5 6) '(7 8 9))
(1 4 7 2 5 8 3 6 9)
定界延续
we talked about delimited continuations and operators shift and reset? After learning about append-map, let's see amb, the ambiguous choice operator-
(define (amb . lst)
(shift k (append-map k lst)))
我们可以这样使用amb-
(reset (list (amb 'J 'Q 'K 'A) (amb '♡ '♢ '♤ '♧)))
(J ♡ J ♢ J ♤ J ♧ Q ♡ Q ♢ Q ♤ Q ♧ K ♡ K ♢ K ♤ K ♧ A ♡ A ♢ A ♤ A ♧)
(reset (list (list (amb 'J 'Q 'K 'A) (amb '♡ '♢ '♤ '♧))))
((J ♡) (J ♢) (J ♤) (J ♧) (Q ♡) (Q ♢) (Q ♤) (Q ♧) (K ♡) (K ♢) (K ♤) (K ♧) (A ♡) (A ♢) (A ♤) (A ♧))
在一个更有用的例子中，我们使用pythagorean定理来find-right-triangles-
(define (pythag a b c)
(= (+ (* a a) (* b b)) (* c c))) ; a² + b² = c²
(define (find-right-triangles . side-lengths)
(filter ((curry apply) pythag)
(reset (list
(list (apply amb side-lengths)
(apply amb side-lengths)
(apply amb side-lengths))))))
(find-right-triangles 1 2 3 4 5 6 7 8 9 10 11 12)
((3 4 5) (4 3 5) (6 8 10) (8 6 10))
带分隔符的延续有效地把你的程序从里到外翻转过来，让你专注于声明式结构 -
(define (bit)
(amb #[=44=] #))
(define (4-bit)
(reset (list (string (bit) (bit) (bit) (bit)))))
(4-bit)
("0000" "0001" "0010" "0011" "0100" "0101" "0110" "0111" "1000" "1001" "1010" "1011" "1100" "1101" "1110" "1111")
amb 可以在任何表达式中的任何位置使用，以对每个提供的值计算一次表达式。这种无限的使用可以产生非凡的结果 -
(reset
(list
(if (> 5 (amb 6 3))
(string-append "you have "
(amb "dark" "long" "flowing")
" "
(amb "hair" "sentences"))
(string-append "please do not "
(amb "steal" "hurt")
" "
(amb "any" "other")
" "
(amb "people" "animals")))))
("please do not steal any people"
"please do not steal any animals"
"please do not steal other people"
"please do not steal other animals"
"please do not hurt any people"
"please do not hurt any animals"
"please do not hurt other people"
"please do not hurt other animals"
"you have dark hair"
"you have dark sentences"
"you have long hair"
"you have long sentences"
"you have flowing hair"
"you have flowing sentences")
使用嵌套 map 是否会自动创建另一层嵌套？这是我使用的一个基本示例：
; One level
(map (lambda (x1)
"Hi")
'(1))
; Two levels
(map (lambda (x1)
(map (lambda (x2)
"Hi")
'(1)))
'(1))
; Three levels
(map (lambda (x1)
(map (lambda (x2)
(map (lambda (x3)
"Hi")
'(1)))
'(1)))
'(1))
; Four levels
(map (lambda (x1)
(map (lambda (x2)
(map (lambda (x3)
(map (lambda (x4)
"Hi")
'(1)))
'(1)))
'(1)))
'(1))
("Hi")
(("Hi"))
((("Hi")))
(((("Hi"))))
或者，是否有任何反例，其中添加另一个 map 不会产生额外的嵌套？我遇到了 'getting' 如何 map 添加另一个级别的问题。例如，对于第一级：
(map (lambda (x1)
"Hi")
'(1))
我知道列表中有一个元素，列表中 'for each element' -- 我们将 return 元素 "Hi" 放在列表中的那个位置，所以第一关我们得到 ("Hi").
但是，例如，如何从列表 ("Hi") 中获得第二级的嵌套列表？我知道我已经问了很多与 map 和嵌套相关的问题，但希望如果我能理解从 1 级别到 2 的过程，我就能弄清楚其余的...... .
map 收集所有函数调用的 return 值，并将它们包装在另一个列表中。
如果函数 return 是一个列表，您将得到一个列表列表。
因此，如果您有嵌套地图，您总是会得到嵌套列表作为最终结果。并且每一层映射都会增加另一层嵌套。
请注意，只有当您实际 return 计算每个级别的 map 值时，这才是正确的。你可以用它做其他事情，例如
;; Two levels
(map (lambda (x1)
(length (map (lambda (x2)
"Hi")
'(1))))
'(1))
这将 return (1)
map 将为该列表中的每个元素return 一个列表。让我们通过一个多地图示例来展示嵌套是如何发挥作用的。
首先，让我们对数字序列做一个 map，然后对它们“什么都不做”。也就是说，只是 return 来自输入的元素：
(map (lambda (x) x)
'(1 2 3))
; (1 2 3)
在这一点上，可能很容易认为如果我们添加另一个 map 就不会出现另一层嵌套，因为这里我们没有 'nested' 输入列表。它只是 'stayed' 在 (1 2 3).
但是如果我们添加一个外层，我们可以看到这是如何发生的：
(map (lambda (ignore-me)
(map (lambda (x) x)
'(1 2 3)))
'(1))
; (( 1 2 3 ))
只有一个 'outer-element' 很难看到这一点，但是，让我们添加 5 个外部元素并使其更容易发现：
(map (lambda (ignore-me)
(map (lambda (x) x)
'(1 2 3)))
'(5 5 5 5 5))
;(
; (1 2 3)
; (1 2 3)
; (1 2 3)
; (1 2 3)
; (1 2 3)
;)
这里我们可以看到每个 外部元素——它们有五个——我们正在return“内部结果”——它在上面的例子中是(1 2 3)。如果我们再次做同样的事情，这次产生两个额外的外部循环，我们可以看到类似的结果：
(map (lambda (ignore-me1)
(map (lambda (ignore-me2)
(map (lambda (x) x)
'(1 2 3)))
'(5 5 5 5 5)))
'(2 2))
; (
; ((1 2 3) (1 2 3) (1 2 3) (1 2 3) (1 2 3))
; ((1 2 3) (1 2 3) (1 2 3) (1 2 3) (1 2 3))
; )
一对一
您的示例包括 (map (lambda (x) x) ...)
(map (lambda (ignore-me)
(map (lambda (x) x) ; <- no-op
'(1 2 3)))
'(1))
((1 2 3))
它“很难看到”，因为内部 map 本质上是空操作。 map 在输入和输出之间创建 1:1 关系，对映射过程的作用没有任何意见。如果映射过程 return 是单个元素、列表或非常嵌套的列表，则没有关系 -
(map (lambda (ignore-me)
'(1 2 3))
'(foo))
((1 2 3))
(map (lambda (_)
'(((((really nested))))))
'(1 2 3))
((((((really nested)))))
(((((really nested)))))
(((((really nested))))))
或者使用一些 ascii 可视化 -
(define (fn x) (+ x x))
(map fn '(1 2 3))
; \ \ \
; \ \ (fn 3)
; \ \ \
; \ (fn 2) \
; \ \ \
; (fn 1) \ \
; \ \ \
; output: '(2 4 6)
你是否应该选择 map 映射程序内部到另一个 map 调用 -
(map (lambda (...)
(map ...)) ; <- nested map
...)
适用相同的规则。每个 map 输出与其输入列表具有 1:1 关系。我们可以想象 map 的类型以获得更多见解 -
map : ('a -> 'b, 'a list) -> 'b list
-------- ------- -------
\ \ \_ returns a list of type 'b
\ \
\ \__ input list of type 'a
\
\__ mapping procedure, maps
one element of type 'a
to one element of type 'b
正在执行映射
作为学习练习，实施 map 以深入了解其工作原理非常有用 -
(define (map fn lst)
(if (null? lst)
'()
(cons (fn (car lst))
(map fn (cdr lst)))))
(map (lambda (x)
(list x x x x x))
'(1 2 3))
((1 1 1 1 1)
(2 2 2 2 2)
(3 3 3 3 3))
如您所见，map 对 lst 中的元素类型或 fn 的 return 值是什么没有意见。 map 直接将列表的 car 传递给 fn 并将其 cons 放入列表的 cdr 的递归结果中。
附加映射
我们应该查看的另一个相关程序是 append-map -
append-map : ('a -> 'b list, 'a list) -> 'b list
-------------- ------ ------
\ \ _ returns 类型为 'b 的列表
\ \_ 类型为 'a 的输入列表
\
\_ 映射函数，地图
'a 类型的一个元素
到 <b>LIST</b> 类型为 'b
这里唯一的区别是映射过程预期 return 一个 list 元素，而不仅仅是单个元素。这样，append-map在输入列表和输出列表之间创建了1:many关系。
(append-map (lambda (x)
(list x x x x x))
'(1 2 3))
(1 1 1 1 1 2 2 2 2 2 3 3 3 3 3)
append-map 的这个特性就是它有时被称为 flatmap 的原因，因为它“扁平化”了一层嵌套 -
(append-map (lambda (x)
(map (lambda (y)
(list x y))
'(spade heart club diamond)))
'(J Q K A))
((J spade)
(J heart)
(J club)
(J diamond)
(Q spade)
(Q heart)
(Q club)
(Q diamond)
(K spade)
(K heart)
(K club)
(K diamond)
(A spade)
(A heart)
(A club)
(A diamond))
reader的后续练习：
- 如果我们在上面的例子中用
append-map换取map，输出会是什么？ - 用另一种或两种方式定义
map。验证正确的行为 - 根据
map定义append-map。不使用map. 重新定义
松散打字
Scheme 是一种无类型语言，因此列表的内容不需要是同质的。尽管如此，以这种方式考虑 map 和 append-map 还是很有用的，因为类型有助于传达函数的行为方式。以下是 Racket 提供的更准确的类型定义 -
(map proc lst ...+) → list?
proc : procedure?
lst : list?
(append-map proc lst ...+) → list?
proc : procedure?
lst : list?
这些要宽松得多，确实反映了您实际可以编写的松散程序。例如-
(append-map (lambda (x)
(list 'a-symbol "hello" 'float (* x 1.5) 'bool (> x 1)))
'(1 2 3))
(a-symbol "hello" float 1.5 bool #f a-symbol "hello" float 3.0 bool #t a-symbol "hello" float 4.5 bool #t)
可变映射和追加映射
你在上面的类型中看到那些...+了吗？为了简单起见，我一直隐藏了一个重要的细节，直到现在为止。 map 的可变参数接口意味着它可以接受 1 个 或更多 个输入列表 -
(map (lambda (x y z)
(list x y z))
'(1 2 3)
'(4 5 6)
'(7 8 9))
((1 4 7) (2 5 8) (3 6 9))
(append-map (lambda (x y z)
(list x y z))
'(1 2 3)
'(4 5 6)
'(7 8 9))
(1 4 7 2 5 8 3 6 9)
reader的后续练习：
- 定义可变参数
map - 定义可变参数
append-map
一点 lambda 演算
您了解 lambda 演算。您知道 (lambda (x y z) (list x y z) 与 list 相同吗？这被称为 Eta reduction -
(map list '(1 2 3) '(4 5 6) '(7 8 9))
((1 4 7) (2 5 8) (3 6 9))
(append-map list '(1 2 3) '(4 5 6) '(7 8 9))
(1 4 7 2 5 8 3 6 9)
定界延续
shift and reset? After learning about append-map, let's see amb, the ambiguous choice operator-
(define (amb . lst)
(shift k (append-map k lst)))
我们可以这样使用amb-
(reset (list (amb 'J 'Q 'K 'A) (amb '♡ '♢ '♤ '♧)))
(J ♡ J ♢ J ♤ J ♧ Q ♡ Q ♢ Q ♤ Q ♧ K ♡ K ♢ K ♤ K ♧ A ♡ A ♢ A ♤ A ♧)
(reset (list (list (amb 'J 'Q 'K 'A) (amb '♡ '♢ '♤ '♧))))
((J ♡) (J ♢) (J ♤) (J ♧) (Q ♡) (Q ♢) (Q ♤) (Q ♧) (K ♡) (K ♢) (K ♤) (K ♧) (A ♡) (A ♢) (A ♤) (A ♧))
在一个更有用的例子中，我们使用pythagorean定理来find-right-triangles-
(define (pythag a b c)
(= (+ (* a a) (* b b)) (* c c))) ; a² + b² = c²
(define (find-right-triangles . side-lengths)
(filter ((curry apply) pythag)
(reset (list
(list (apply amb side-lengths)
(apply amb side-lengths)
(apply amb side-lengths))))))
(find-right-triangles 1 2 3 4 5 6 7 8 9 10 11 12)
((3 4 5) (4 3 5) (6 8 10) (8 6 10))
带分隔符的延续有效地把你的程序从里到外翻转过来，让你专注于声明式结构 -
(define (bit)
(amb #[=44=] #))
(define (4-bit)
(reset (list (string (bit) (bit) (bit) (bit)))))
(4-bit)
("0000" "0001" "0010" "0011" "0100" "0101" "0110" "0111" "1000" "1001" "1010" "1011" "1100" "1101" "1110" "1111")
amb 可以在任何表达式中的任何位置使用，以对每个提供的值计算一次表达式。这种无限的使用可以产生非凡的结果 -
(reset
(list
(if (> 5 (amb 6 3))
(string-append "you have "
(amb "dark" "long" "flowing")
" "
(amb "hair" "sentences"))
(string-append "please do not "
(amb "steal" "hurt")
" "
(amb "any" "other")
" "
(amb "people" "animals")))))
("please do not steal any people"
"please do not steal any animals"
"please do not steal other people"
"please do not steal other animals"
"please do not hurt any people"
"please do not hurt any animals"
"please do not hurt other people"
"please do not hurt other animals"
"you have dark hair"
"you have dark sentences"
"you have long hair"
"you have long sentences"
"you have flowing hair"
"you have flowing sentences")