关于累加器样式递归的球拍问题

Question

使用累加器样式递归，编写一个函数 一个长字符串，它使用字符串列表并生成 列表中字符串按它们在列表中出现的顺序进行串联。 也就是说，(一长串(列出"爱丽丝"鲍勃"夏娃") 返回"爱丽丝鲍勃夏娃">

Answer 1

注释(稍后添加)：

• 原始问题(引用如下)没有指定特定的Racket语言，也没有提供 尝试的解决方案，或指示提示问题的问题类型。
• 这个答案将使用球拍的初学者 语言(BSL)，并开发(详尽的)一个简单的"自然递归"解决方案，然后 转换为请求的"累加器样式"。BSL用于将注意力集中在如何使用设计方法上 支持解决方案开发，而无需"直觉飞跃"或熟悉高级语言。
• 读者可能想知道它实际上需要多长时间，一丝不苟地遵循设计配方。 签名、检查期望测试、模板复制和编辑等，以生成完成的功能。 对我来说，答案是大约 10 分钟;为了进行比较，只需"编写一个函数"(带有签名和目的) 和 repl 检查示例，大约需要一半。

使用累加器样式递归，编写一个函数一长字符串，该函数使用 ListOfString 并按照字符串在列表中出现的顺序生成列表中的字符串串联。也就是说，(一长串(列表"Alice"Bob"Eve")返回"AliceBobEve">

开始使用

使用编写函数的设计方法，从函数签名和目的开始;这些可以从上面的问题中复制并粘贴到DrRacket定义区域中的Racket函数定义存根中：

(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的语言设置为初学者)，运行：

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))) ]))       ;

(有一个"累加器式递归"的模板，但这个答案将从最简单的开始 模板列表。稍后将修改为累加器样式。

编辑模板，将通用名称替换为此问题的相应名称，以获取：

(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;我们没有这样的 函数，但检查初级学生中的字符串 对于合适的功能，会产生以下可能性：

; 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")
RunAgain，并且(非累加器)函数完成：

#;
(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!
> 

蓄能器样式

如前所述，有一个"累加器式递归"模板，它使用 进阶学生的特点 语言。为什么要使用包含累加器的函数版本？ 一个常见的原因是将递归调用放在尾部位置。

要探索此样式，请首先尝试将模板编辑为尾递归：

(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)               ; ?
]))

部分填充模板中的递归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对于.....
one-long-string-with-arg中arg的 rôle 是累积一个"到目前为止的结果"值， 所以它被重命名为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!
> 

(待续)