我想我发现了你的问题。坦白说,你还没有完全做到这一点。作业明确指出您必须在从递归返回时建立结果。这是因为你不想reverse
在你的程序结束时,或者做一个append
在进行尾递归时。
以下是解释每种方法的几个示例:
;; Using an accumulator
(define (double ls acc)
(if (empty? ls)
acc
(double (rest ls) (cons (* 2 (first ls)) acc))))
(double '(1 2 3) '())
;; = '(6 4 2)
;; So you could reverse the result: (reverse '(1 2 3) '()))
;; but this requires looping over the list again!
;; Using append
(define (double2 ls acc)
(if (empty? ls)
acc
(double2 (rest ls) (append acc (list (* 2 (first ls)))))))
(double2 '(1 2 3) '())
;; = '(2 4 6)
;; But the append operation is very expensive and you don't want that!
(define (double3 ls)
(if (empty? ls)
'()
(cons (* 2 (first ls)) (double3 (rest ls)))))
(double3 '(1 2 3))
;; Cons *after* the recursive call.
;; Requires more memory though, becuase you can not do tail call optimisation!
;; Info: http://c2.com/cgi/wiki?TailRecursion
所以对于函数的不同输入slide-row-left/help
:
情况 1:前两个数字相等
Input: '(2 2 4 -)
结果:'(4 4 '- '-)
您在这里想要做的是对两个第一个元素求和 (4)。然后你想要计算列表的其余部分。列表的其余部分现在还应该包含一个额外的空白,因为对两个元素求和会使列表缩短一个元素。所以你将一个新的空白传递给acc
递归调用中的值。因此,您首先要做的是计算列表的其余部分。因此,递归调用(drop ls 2)
and (cons '- acc)
。这会删除列表中的前 2 个元素。一旦你得到结果(结果将是'(4 '- '-)
, 你刚才cons
你前面的总和。这导致总结果为'(4 4 '- '-)
.
情况 2:前两个数字不同
Input: '(4 2 2 2)
结果:'(4 4 2 '-)
如果前两个数字不同,我们就无能为力。我们从列表中取出第一个数字(4
),这给你留下了'(2 2 2)
。您不能删除前两个元素,因为第二个和第三个元素可能可以求和。您记住第一个元素并递归调用该函数来计算结果的其余部分。该函数返回并给你'(4 2 '-)
。现在你需要做的就是cons
第一个元素回到它前面,产生'(4 4 2 '-)
.
情况3:第一个元素是空白
Input: '(- 2 2 4)
结果:'(4 4 '- '-)
如果第一个数字是空白,您将无法对其执行任何操作。你可能会认为在这种情况下case 2适用但不适用。应将空白放在解决方案的背面。但你怎么能这么做呢?简单,将空白放入蓄能器中。正如您很快看到的那样,累加器基本上是列表的末尾。因此,将空白从列表中移开,这使您感到'(2 2 4)
. Put '-
在累加器前面,这使得累加器等于'('- <rest of acc>)
并进行递归调用。所以你用列表来称呼它'(2 2 4)
和累加器'('- <rest of acc>)
。你的递归调用将产生'(4 4 '- '-)
。因此,你不必cons
它前面的任何东西都不再存在,这只是你的结果。
情况 4:第二个元素为空白
Input: '(2 - 2 4)
结果:'(4 4 '- '-)
如果第二个数字是空白,情况就有点棘手了。您必须从列表中删除空白。所以你会想要(2 2 4)
。要做到这一点,你可以这样做(cons (first ls) (rest (rest ls)))
。空白再次不能被丢弃。您需要将其放在列表的末尾。列表的末尾在哪里?确实,累加器。那么你cons
您想要在解决方案后面(空白)的元素acc
像这样:(cons (second ls) acc)
。同样,您已将空白放在末尾并进行递归调用。无需将任何元素放在递归调用的解决方案前面,以便调用可以给出完整的答案。
情况 5:输入为空
Input: '()
结果:acc
如果您的输入为空,则需要返回acc
价值。由于您的输入为空,因此您需要返回列表的末尾,我们知道这是acc
value.
情况6:输入长度为1
Input: '(4)
结果:(cons 4 acc)
如果输入只有一个元素,则无法对其应用任何总和或其他内容。你只有一个元素。所以,结果是该元素,cons
d 在前面acc
.
Source
#lang racket
;; A shorthand for (first (rest ls))
(define (second ls) (first (rest ls)))
(define (blank? item) (equal? item '-))
(define (slide-row-left b)
(blank-help (slide-row-left/help b '()) '()))
(define (slide-row-left/help ls acc)
(cond [(empty? ls) acc]
[(= (length ls) 1) (cons (first ls) acc)]
;; When the first element is blank (e.g., '(- 2 4))
;; -> Discard the blank
;; -> call the function on the rest of the list.
[(blank? (first ls))
(slide-row-left/help (rest ls) (cons (first ls) acc))]
;; When the second element is blank (e.g., '(2 - 2 4))
;; -> Discard the second element
;; -> Run the function again with the entire list (without the blank)
[(blank? (second ls))
(slide-row-left/help (cons (first ls) (drop ls 2)) (cons (second ls) acc))]
;; If the first two elements are not equal:
;; -> drop 1 element from the list
;; -> cons this element to the result of the recursive call
[(not (equal? (first ls) (second ls)))
(let ([fst (first ls)]
[snd (second ls)]
[rst (rest ls)])
(cons fst (slide-row-left/help rst acc)))]
;; If the first two elements are the same:
;; -> drop 2 elements from the list
;; -> Sum them
;; -> cons the sum in front of the recursive call
[else
(let ([fst (first ls)]
[snd (second ls)]
[rst (drop ls 2)])
(cons (* 2 snd) (slide-row-left/help rst (cons '- acc))))]))
(define (blank-help ls acc)
(cond [(empty? ls) acc]
[(blank? (first ls)) (blank-help (rest ls) (cons (first ls) acc))]
[else (cons (first ls) (blank-help (rest ls) acc))]))
(define (check-expect x y)
(display x)
(display y)
(equal? x y))
(check-expect (slide-row-left '(2 2 4 -))(list 4 4 '- '-))
(check-expect (slide-row-left '(2 2 - 4))(list 4 4 '- '-))
(check-expect (slide-row-left '(2 - 2 4))(list 4 4 '- '-))
(check-expect (slide-row-left '(- 2 2 4))(list 4 4 '- '-))
(check-expect (slide-row-left '(2 2 2 2))(list 4 4 '- '-))
(check-expect (slide-row-left '(4 2 2 2))(list 4 4 2 '-))
(check-expect (slide-row-left '(2 4 2 2))(list 2 4 4 '-))
(check-expect (slide-row-left '(2 2 4 2))(list 4 4 2 '-))
(check-expect (slide-row-left '(2 2 4 4))(list 4 8 '- '-))
Edit
The drop
函数用于删除n
列表的第一个元素。可以如下图实现。但是,您也可以使用(rest (rest ls))
反而。为了简洁起见,我使用了它。
drop
(define (drop ls n)
(cond [(empty? ls)
ls]
[(>= 0 n)
ls]
[else
(drop (rest ls) (- n 1))]))