关于累加器式递归的 Racket 问题
a Racket problem about the accumulator-style recursion
使用累加器式递归，编写一个函数
使用 ListOfString 并生成
按照它们在列表中出现的顺序连接列表中的字符串。
也就是说，（一个长字符串（列出“Alice”“Bob”“Eve”）
returns“爱丽丝鲍勃夏娃”
注释（稍后添加）：
- 原始问题（在下面引用）没有指定特定的 Racket 语言，也没有提供
尝试的解决方案，或指出问题的类型。
- 这个答案将使用 Racket 的 Beginning Student
语言（BSL），并开发（详尽地）一个简单的“自然递归”解决方案，然后是
转换为请求的“accumulator-style”。 BSL用于关注如何使用设计方法
无需“直觉跳跃”或熟悉高级语言即可实现解决方案开发。
- 读者可能想知道实际需要多长时间，仔细遵循设计配方
签名、check-expect 测试、模板复制和编辑等，以生成完成的功能。
对我来说，答案是大约 10 分钟；为了比较，只是“写一个函数”（带有签名和目的）
和 repl 检查示例，大约需要一半。
Using accumulator-style recursion, write a function one-long-string that consumes a ListOfString and produces the concatenation of strings in the list in the order they appear in the list. That is, (one-long-string (list "Alice" "Bob" "Eve") returns "AliceBobEve"
开始
使用design recipe for writing functions，以函数signature和purpose开始；这些可以从上面的问题中复制并粘贴到 DrRacket 定义区域中的 Racket 函数定义 stub：
(define (one-long-string los) ;; ListOfString -> String ; *stub* ;; *signature*
;; produce the concatenation of los strings in order ; *purpose statement*
"") ; *stub body* (valid result)
下一步是以 check-expect:
的形式添加一个最小的 example
(check-expect (one-long-string empty) "") ; *minimal example*
然后（DrRacket 的语言设置为 Beginning Student），运行:
The test passed!
>
遵循食谱
根据参数类型 ListOfString 选择 模板 继续遵循设计方案 -
将其复制到定义区域：
(define (fn lox) ;; ListOfX -> Y ; *template*
;; produce a Y from lox using natural recursion ;
(cond ;
[(empty? lox) ... ] ; ... = "base case value" ;; Y
[else (.... ; .... = "inventory fn(s)" ;; X Y -> Y
(first lox) (fn (rest lox))) ])) ;
(有一个“accumulator-style递归”的模板，但是这个答案将从最简单的开始
模板列表。后面会修改解决方案为accumulator-style。）
编辑模板，将通用名称替换为适用于此问题的通用名称，以获得：
(define (one-long-string los) ;; ListOfString -> String
;; produce the concatenation of los strings in order
(cond
[(empty? los) "" ] ;; String
[else (.... ;; String String -> String
(first los) (one-long-string (rest los))) ]))
参考上面的第一个例子，占位符 ... 已被替换为 ""。
请注意，.... 的签名是从其参数和结果的签名中推导出来的。
注释掉存根（用#;作为前缀），然后运行再次确认The test passed!。
（总是 运行 在任何更改后确认一切仍然有效，并立即修复任何拼写错误。）
再添加一个例子：
(check-expect (one-long-string (list "Alice")) "Alice")
和运行：错误信息确认需要替换占位符....。
（这个测试 可以 通过添加 (define (arg1 x y) x) 并使用 arg1 作为 ....，
但可以看出可能需要更好的东西。）
.... 的替代品将具有签名 String String -> String；我们没有这样的
功能，但检查 Strings in Beginning Student
对于合适的功能产生以下可能性：
; format ;; String Any -> String ; *inventory* (all functions with
; string-append ;; String String -> String ; signature String String -> String)
考虑另一个例子：
(check-expect (one-long-string (list "Alice" "Bob")) "AliceBob")
给定“Alice”和“Bob”，可以用 string-append 生成“AliceBob”，即示例可以写成：
(check-expect (one-long-string (list "Alice" "Bob")) (string-append "Alice" "Bob"))
这表明 .... 应该是 string-append；现在可以添加最后一个示例：
(check-expect (one-long-string (list "Alice" "Bob" "Eve")) "AliceBobEve")
运行，(non-accumulator)函数完成：
#;
(define (one-long-string los) ;; ListOfString -> String ; *stub* ;; *signature*
;; produce the concatenation of los strings in order ; *purpose statement*
"") ; *stub body* (valid result)
(check-expect (one-long-string empty) "") ; *minimal example*
(define (one-long-string los) ;; ListOfString -> String
;; produce the concatenation of los strings in order
(cond
[(empty? los) "" ]
[else (string-append
(first los) (one-long-string (rest los))) ]))
(check-expect (one-long-string (list "Alice")) "Alice")
(check-expect (one-long-string (list "Alice" "Bob")) (string-append "Alice" "Bob"))
(check-expect (one-long-string (list "Alice" "Bob" "Eve")) "AliceBobEve")
All 4 tests passed!
>
累加器样式
如前所述，“accumulator-style递归”有一个模板，它使用
Advanced Student 的功能
语。为什么要使用包含累加器的函数版本？
一个常见的原因是将递归调用放在尾部位置。
要探索这种风格，首先尝试将模板编辑为 tail-recursive:
(define (fn lox) ;; ListOfX -> Y ; *template*
;; produce a Y from lox (tail recursive) ;
(cond ;
[(empty? lox) ... ] ; result ;; Y
[else (fn (rest lox)) ; tail recursion
.... (first lox) ; (where do these go?)
])) ;
这不对（占位符 .... 和 (first lox) 不适合）但继续
替换通用名称：
(define (one-long-string los) ;; ListOfString -> String
;; produce the concatenation of los strings in order
(cond
[(empty? los) ... ] ;; String
[else (one-long-string (rest los))
.... (first los) ; ?
]))
部分 filled-in 模板中的递归 one-long-string 调用现在位于尾部位置，
使用参数 (rest los) 以便它可以处理 los 的所有元素，
但是为了在产生结果方面取得进展，函数必须用 (first los).
做一些事情
这个可以装在哪里？
解决这个问题的一种方法是引入一个论证：通过附加论证，
one-long-string（现在更名为one-long-string-with-arg）在递归中占有一席之地
呼叫等待 (first los):
(define (one-long-string-with-arg los arg) ;; ListOfString X -> String
;; produce the concatenation of los strings in order, using extra arg
(cond
[(empty? los) (... arg) ] ;; String
[else (one-long-string-with-arg (rest los) (.... arg (first los)))
]))
(define (one-long-string los) ;; ListOfString -> String
;; produce the concatenation of los strings in order
(one-long-string-with-arg los .....))
one-long-string 现在只需调用 one-long-string-with-arg，为 arg 提供 .....。
回顾前两个例子：
(check-expect (one-long-string empty) "")
(check-expect (one-long-string (list "Alice")) "Alice")
可以看出 ..... 的简单替换是 ""，(... arg)
只是 arg。和以前一样，其他示例建议 string-append for .....
one-long-string-with-arg中arg的作用是累积一个“到目前为止的结果”值，
所以重命名为rsf，完整的累加器样式解为：
#;
(define (one-long-string los) ;; ListOfString -> String ; *stub* ;; *signature*
;; produce the concatenation of los strings in order ; *purpose statement*
"") ; *stub body* (valid result)
(check-expect (one-long-string empty) "") ; *minimal example*
(define (one-long-string-acc los rsf) ;; ListOfString String -> String
;; produce the concatenation of los strings in order using rsf accumulator
(cond
[(empty? los) rsf ]
[else (one-long-string-acc (rest los)
(string-append rsf (first los))) ]))
(define (one-long-string los) ;; ListOfString -> String
;; produce the concatenation of los strings in order, using accumulator
(one-long-string-acc los ""))
(check-expect (one-long-string (list "Alice")) "Alice")
(check-expect (one-long-string (list "Alice" "Bob")) (string-append "Alice" "Bob"))
(check-expect (one-long-string (list "Alice" "Bob" "Eve")) "AliceBobEve")
All 4 tests passed!
>
（待续）
使用累加器式递归，编写一个函数 使用 ListOfString 并生成 按照它们在列表中出现的顺序连接列表中的字符串。 也就是说，（一个长字符串（列出“Alice”“Bob”“Eve”） returns“爱丽丝鲍勃夏娃”
注释（稍后添加）：
- 原始问题（在下面引用）没有指定特定的 Racket 语言，也没有提供 尝试的解决方案，或指出问题的类型。
- 这个答案将使用 Racket 的 Beginning Student 语言（BSL），并开发（详尽地）一个简单的“自然递归”解决方案，然后是 转换为请求的“accumulator-style”。 BSL用于关注如何使用设计方法 无需“直觉跳跃”或熟悉高级语言即可实现解决方案开发。
- 读者可能想知道实际需要多长时间，仔细遵循设计配方 签名、check-expect 测试、模板复制和编辑等，以生成完成的功能。 对我来说，答案是大约 10 分钟；为了比较，只是“写一个函数”（带有签名和目的） 和 repl 检查示例，大约需要一半。
Using accumulator-style recursion, write a function one-long-string that consumes a ListOfString and produces the concatenation of strings in the list in the order they appear in the list. That is, (one-long-string (list "Alice" "Bob" "Eve") returns "AliceBobEve"
开始
使用design recipe for writing functions，以函数signature和purpose开始；这些可以从上面的问题中复制并粘贴到 DrRacket 定义区域中的 Racket 函数定义 stub：
(define (one-long-string los) ;; ListOfString -> String ; *stub* ;; *signature*
;; produce the concatenation of los strings in order ; *purpose statement*
"") ; *stub body* (valid result)
下一步是以 check-expect:
(check-expect (one-long-string empty) "") ; *minimal example*
然后（DrRacket 的语言设置为 Beginning Student），运行:
The test passed!
>
遵循食谱
根据参数类型 ListOfString 选择 模板 继续遵循设计方案 -
将其复制到定义区域：
(define (fn lox) ;; ListOfX -> Y ; *template*
;; produce a Y from lox using natural recursion ;
(cond ;
[(empty? lox) ... ] ; ... = "base case value" ;; Y
[else (.... ; .... = "inventory fn(s)" ;; X Y -> Y
(first lox) (fn (rest lox))) ])) ;
(有一个“accumulator-style递归”的模板，但是这个答案将从最简单的开始 模板列表。后面会修改解决方案为accumulator-style。）
编辑模板，将通用名称替换为适用于此问题的通用名称，以获得：
(define (one-long-string los) ;; ListOfString -> String
;; produce the concatenation of los strings in order
(cond
[(empty? los) "" ] ;; String
[else (.... ;; String String -> String
(first los) (one-long-string (rest los))) ]))
参考上面的第一个例子，占位符 ... 已被替换为 ""。
请注意，.... 的签名是从其参数和结果的签名中推导出来的。
注释掉存根（用#;作为前缀），然后运行再次确认The test passed!。
（总是 运行 在任何更改后确认一切仍然有效，并立即修复任何拼写错误。）
再添加一个例子：
(check-expect (one-long-string (list "Alice")) "Alice")
和运行：错误信息确认需要替换占位符....。
（这个测试 可以 通过添加 (define (arg1 x y) x) 并使用 arg1 作为 ....，
但可以看出可能需要更好的东西。）
.... 的替代品将具有签名 String String -> String；我们没有这样的
功能，但检查 Strings in Beginning Student
对于合适的功能产生以下可能性：
; format ;; String Any -> String ; *inventory* (all functions with
; string-append ;; String String -> String ; signature String String -> String)
考虑另一个例子：
(check-expect (one-long-string (list "Alice" "Bob")) "AliceBob")
给定“Alice”和“Bob”，可以用 string-append 生成“AliceBob”，即示例可以写成：
(check-expect (one-long-string (list "Alice" "Bob")) (string-append "Alice" "Bob"))
这表明 .... 应该是 string-append；现在可以添加最后一个示例：
(check-expect (one-long-string (list "Alice" "Bob" "Eve")) "AliceBobEve")
运行，(non-accumulator)函数完成：
#;
(define (one-long-string los) ;; ListOfString -> String ; *stub* ;; *signature*
;; produce the concatenation of los strings in order ; *purpose statement*
"") ; *stub body* (valid result)
(check-expect (one-long-string empty) "") ; *minimal example*
(define (one-long-string los) ;; ListOfString -> String
;; produce the concatenation of los strings in order
(cond
[(empty? los) "" ]
[else (string-append
(first los) (one-long-string (rest los))) ]))
(check-expect (one-long-string (list "Alice")) "Alice")
(check-expect (one-long-string (list "Alice" "Bob")) (string-append "Alice" "Bob"))
(check-expect (one-long-string (list "Alice" "Bob" "Eve")) "AliceBobEve")
All 4 tests passed!
>
累加器样式
如前所述，“accumulator-style递归”有一个模板，它使用 Advanced Student 的功能 语。为什么要使用包含累加器的函数版本？ 一个常见的原因是将递归调用放在尾部位置。
要探索这种风格，首先尝试将模板编辑为 tail-recursive:
(define (fn lox) ;; ListOfX -> Y ; *template*
;; produce a Y from lox (tail recursive) ;
(cond ;
[(empty? lox) ... ] ; result ;; Y
[else (fn (rest lox)) ; tail recursion
.... (first lox) ; (where do these go?)
])) ;
这不对（占位符 .... 和 (first lox) 不适合）但继续
替换通用名称：
(define (one-long-string los) ;; ListOfString -> String
;; produce the concatenation of los strings in order
(cond
[(empty? los) ... ] ;; String
[else (one-long-string (rest los))
.... (first los) ; ?
]))
部分 filled-in 模板中的递归 one-long-string 调用现在位于尾部位置，
使用参数 (rest los) 以便它可以处理 los 的所有元素，
但是为了在产生结果方面取得进展，函数必须用 (first los).
做一些事情
这个可以装在哪里？
解决这个问题的一种方法是引入一个论证：通过附加论证，
one-long-string（现在更名为one-long-string-with-arg）在递归中占有一席之地
呼叫等待 (first los):
(define (one-long-string-with-arg los arg) ;; ListOfString X -> String
;; produce the concatenation of los strings in order, using extra arg
(cond
[(empty? los) (... arg) ] ;; String
[else (one-long-string-with-arg (rest los) (.... arg (first los)))
]))
(define (one-long-string los) ;; ListOfString -> String
;; produce the concatenation of los strings in order
(one-long-string-with-arg los .....))
one-long-string 现在只需调用 one-long-string-with-arg，为 arg 提供 .....。
回顾前两个例子：
(check-expect (one-long-string empty) "")
(check-expect (one-long-string (list "Alice")) "Alice")
可以看出 ..... 的简单替换是 ""，(... arg)
只是 arg。和以前一样，其他示例建议 string-append for .....
one-long-string-with-arg中arg的作用是累积一个“到目前为止的结果”值，
所以重命名为rsf，完整的累加器样式解为：
#;
(define (one-long-string los) ;; ListOfString -> String ; *stub* ;; *signature*
;; produce the concatenation of los strings in order ; *purpose statement*
"") ; *stub body* (valid result)
(check-expect (one-long-string empty) "") ; *minimal example*
(define (one-long-string-acc los rsf) ;; ListOfString String -> String
;; produce the concatenation of los strings in order using rsf accumulator
(cond
[(empty? los) rsf ]
[else (one-long-string-acc (rest los)
(string-append rsf (first los))) ]))
(define (one-long-string los) ;; ListOfString -> String
;; produce the concatenation of los strings in order, using accumulator
(one-long-string-acc los ""))
(check-expect (one-long-string (list "Alice")) "Alice")
(check-expect (one-long-string (list "Alice" "Bob")) (string-append "Alice" "Bob"))
(check-expect (one-long-string (list "Alice" "Bob" "Eve")) "AliceBobEve")
All 4 tests passed!
>
（待续）