球拍累加器列表函数
Racket accumulator list function
我正在研究创建您可能玩过的 2048 游戏的具体步骤。它在许多在线网站上。
基本上这个函数所做的就是：
1）所有空格移到后面
和 2) 如果前两个数字相等，则它加倍并检查每两个数字
这些是我卡住的步骤的说明：
Design a slide-left function so that it runs a single pass over the given row using an APS (accumulator passing style) helper. You will need to maintain two accumulators. The first accumulator remembers the last unmerged number. Initially, this value is false, meaning that we have not yet seen a number. The second accumulator is where we pile up the blanks as we come across them (a blank is '-) The easiest thing to do is to use a list for this purpose and, thus, its initial value is empty.
Do it in a single pass: You might think, at first, that it would be a good idea to use an accumulator for the solution. But then there is a problem with order. You could add new elements to the end of the current solution using something like (append solution (list number)), but that append operation is recursive and takes time proportional to the length of the solution list. We definitely want to avoid non-trivial operations during an APS recursion if we can. You could, instead, decide to add new numbers to the front of the current solution (using cons), with the intention of reversing the solution at the end. This is certainly better than the append approach. The drawback is that it requires a second pass over the data to do the reversal. We want to do this in one pass, and we can. So, the easiest and fastest thing to do is to just construct the solution, in the right order, as you back out of the recursion.
我在这里添加了一堆检查期望，这样你就可以看到它在做什么：
(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 '- '-))
好的，这就是我所拥有的：
(define (blank? item) (equal? item '-))
(define (slide-row-left b)
(blank-help (slide-row-left/help b false) '()))
(define (slide-row-left/help ls acc)
(cond [(empty? ls) acc]
[(not (equal? (first ls) (first (rest ls))))
(slide-row-left/help (rest (rest ls))
(cons (first (rest ls)) (cons (first ls) acc)))]
[else (slide-row-left/help (rest (rest ls)) 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))]))
第一个累加器 slide-row-left/help 创建一个不会合并的数字列表。它检查第一个数字和第二个数字是否不相等，并将它们添加到列表中。如果它们相等（这意味着它们合并为原始数量的两倍）那么它就会重复出现。第二个累加器 blank-help 将所有空格 '- 推到列表的末尾，因此所有数字都向左移动。
问题是我不知道如何使用这些合并各个部分，尤其是在一次传递中。
我今晚就要出发了，所以希望你们明天之前回复。任何帮助都会很棒。这也适用于 ISL+
我想我发现了你的问题。坦率地说，你还没有到那儿。作业明确指出您必须在递归返回时建立结果。这是因为您不想在程序结束时 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:
情况一：前两个数相等
输入：'(2 2 4 -)
结果：'(4 4 '- '-)
您想在这里做的是对两个第一个元素 (4) 求和。然后你想计算列表的其余部分。列表的其余部分现在也应该包含一个额外的空白，因为将两个元素相加会使列表中的一个元素更短。因此，您在递归调用中将一个新的空白传递给 acc 值。所以你首先要做的是计算列表的其余部分。因此，使用 (drop ls 2) 和 (cons '- acc) 递归调用。这将从列表中删除前 2 个元素。一旦你得到那个结果（结果将是'(4 '- '-)，你只需cons你的总和在它前面。这导致总结果'(4 4 '- '-)。
情况2：前两个数字不同
输入：'(4 2 2 2)
结果：'(4 4 2 '-)
如果前两个数字不同，我们将无能为力。我们从列表中删除第一个数字 (4)，剩下 '(2 2 2)。您不能删除前两个，因为第二个和第三个元素可能可以相加。您记住第一个元素并递归调用该函数以计算结果的其余部分。函数 returns 并给你 '(4 2 '-)。现在你需要做的就是 cons 它前面的第一个元素，产生 '(4 4 2 '-).
情况三：第一个元素为空白
输入：'(- 2 2 4)
结果：'(4 4 '- '-)
如果第一个数字是空白，您将无法对其进行任何操作。您可能认为在这种情况下 case 2 适用，但事实并非如此。应在您的解决方案后面放置一个空白。但是你怎么能那样做呢？很简单，你把空白放在你的累加器里。正如您很快就会看到的，累加器基本上是列表的末尾。所以，从列表中去掉空白，留下 '(2 2 4)。将 '- 放在累加器前面，这使得累加器等于 '('- <rest of acc>) 并进行递归调用。所以你用列表 '(2 2 4) 和累加器 '('- <rest of acc>) 来调用它。您的递归调用将产生 '(4 4 '- '-)。因此，您不再需要 cons 它前面的任何内容，它只是您的结果。
情况4：第二个元素为空白
输入：'(2 - 2 4)
结果：'(4 4 '- '-)
如果第二个数字是空白，情况就有点棘手了。您将不得不从列表中删除空白。所以你会想要 (2 2 4)。为此，您可以执行 (cons (first ls) (rest (rest ls)))。空白可以再次不被丢弃。您需要将其放在列表的末尾。列表的末尾在哪里？确实，蓄能器。所以你 cons 你想要的元素在解决方案的后面（空白）到 acc 这样：(cons (second ls) acc)。同样，您将空白放在最后并进行递归调用。没有元素必须放在递归调用的解决方案前面，以便调用为您提供完整的答案。
情况五：输入为空
输入：'()
结果：acc
如果您的输入为空，则需要 return acc 值。由于您的输入为空，因此您需要 return 列表的末尾，我们知道这是 acc 值。
情况六：输入为长度1
输入：'(4)
结果：(cons 4 acc)
如果输入只有一个元素，则不能对其应用任何总和或其他内容。你只有一个元素。因此，结果是 acc.
前面的元素 consd
来源
#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 '- '-))
编辑
drop 函数用于删除列表的第 n 个元素。它可以如下所示实现。但是，您也可以改用 (rest (rest ls))。为了简洁起见，我使用它。
掉落
(define (drop ls n)
(cond [(empty? ls)
ls]
[(>= 0 n)
ls]
[else
(drop (rest ls) (- n 1))]))
我正在研究创建您可能玩过的 2048 游戏的具体步骤。它在许多在线网站上。
基本上这个函数所做的就是： 1）所有空格移到后面 和 2) 如果前两个数字相等，则它加倍并检查每两个数字
这些是我卡住的步骤的说明：
Design a slide-left function so that it runs a single pass over the given row using an APS (accumulator passing style) helper. You will need to maintain two accumulators. The first accumulator remembers the last unmerged number. Initially, this value is false, meaning that we have not yet seen a number. The second accumulator is where we pile up the blanks as we come across them (a blank is '-) The easiest thing to do is to use a list for this purpose and, thus, its initial value is empty.
Do it in a single pass: You might think, at first, that it would be a good idea to use an accumulator for the solution. But then there is a problem with order. You could add new elements to the end of the current solution using something like (append solution (list number)), but that append operation is recursive and takes time proportional to the length of the solution list. We definitely want to avoid non-trivial operations during an APS recursion if we can. You could, instead, decide to add new numbers to the front of the current solution (using cons), with the intention of reversing the solution at the end. This is certainly better than the append approach. The drawback is that it requires a second pass over the data to do the reversal. We want to do this in one pass, and we can. So, the easiest and fastest thing to do is to just construct the solution, in the right order, as you back out of the recursion.
我在这里添加了一堆检查期望，这样你就可以看到它在做什么：
(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 '- '-))
好的，这就是我所拥有的：
(define (blank? item) (equal? item '-))
(define (slide-row-left b)
(blank-help (slide-row-left/help b false) '()))
(define (slide-row-left/help ls acc)
(cond [(empty? ls) acc]
[(not (equal? (first ls) (first (rest ls))))
(slide-row-left/help (rest (rest ls))
(cons (first (rest ls)) (cons (first ls) acc)))]
[else (slide-row-left/help (rest (rest ls)) 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))]))
第一个累加器 slide-row-left/help 创建一个不会合并的数字列表。它检查第一个数字和第二个数字是否不相等，并将它们添加到列表中。如果它们相等（这意味着它们合并为原始数量的两倍）那么它就会重复出现。第二个累加器 blank-help 将所有空格 '- 推到列表的末尾，因此所有数字都向左移动。
问题是我不知道如何使用这些合并各个部分，尤其是在一次传递中。
我今晚就要出发了，所以希望你们明天之前回复。任何帮助都会很棒。这也适用于 ISL+
我想我发现了你的问题。坦率地说，你还没有到那儿。作业明确指出您必须在递归返回时建立结果。这是因为您不想在程序结束时 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:
情况一：前两个数相等
输入：'(2 2 4 -)
结果：'(4 4 '- '-)
您想在这里做的是对两个第一个元素 (4) 求和。然后你想计算列表的其余部分。列表的其余部分现在也应该包含一个额外的空白，因为将两个元素相加会使列表中的一个元素更短。因此，您在递归调用中将一个新的空白传递给 acc 值。所以你首先要做的是计算列表的其余部分。因此，使用 (drop ls 2) 和 (cons '- acc) 递归调用。这将从列表中删除前 2 个元素。一旦你得到那个结果（结果将是'(4 '- '-)，你只需cons你的总和在它前面。这导致总结果'(4 4 '- '-)。
情况2：前两个数字不同
输入：'(4 2 2 2)
结果：'(4 4 2 '-)
如果前两个数字不同，我们将无能为力。我们从列表中删除第一个数字 (4)，剩下 '(2 2 2)。您不能删除前两个，因为第二个和第三个元素可能可以相加。您记住第一个元素并递归调用该函数以计算结果的其余部分。函数 returns 并给你 '(4 2 '-)。现在你需要做的就是 cons 它前面的第一个元素，产生 '(4 4 2 '-).
情况三：第一个元素为空白
输入：'(- 2 2 4)
结果：'(4 4 '- '-)
如果第一个数字是空白，您将无法对其进行任何操作。您可能认为在这种情况下 case 2 适用，但事实并非如此。应在您的解决方案后面放置一个空白。但是你怎么能那样做呢？很简单，你把空白放在你的累加器里。正如您很快就会看到的，累加器基本上是列表的末尾。所以，从列表中去掉空白，留下 '(2 2 4)。将 '- 放在累加器前面，这使得累加器等于 '('- <rest of acc>) 并进行递归调用。所以你用列表 '(2 2 4) 和累加器 '('- <rest of acc>) 来调用它。您的递归调用将产生 '(4 4 '- '-)。因此，您不再需要 cons 它前面的任何内容，它只是您的结果。
情况4：第二个元素为空白
输入：'(2 - 2 4)
结果：'(4 4 '- '-)
如果第二个数字是空白，情况就有点棘手了。您将不得不从列表中删除空白。所以你会想要 (2 2 4)。为此，您可以执行 (cons (first ls) (rest (rest ls)))。空白可以再次不被丢弃。您需要将其放在列表的末尾。列表的末尾在哪里？确实，蓄能器。所以你 cons 你想要的元素在解决方案的后面（空白）到 acc 这样：(cons (second ls) acc)。同样，您将空白放在最后并进行递归调用。没有元素必须放在递归调用的解决方案前面，以便调用为您提供完整的答案。
情况五：输入为空
输入：'()
结果：acc
如果您的输入为空，则需要 return acc 值。由于您的输入为空，因此您需要 return 列表的末尾，我们知道这是 acc 值。
情况六：输入为长度1
输入：'(4)
结果：(cons 4 acc)
如果输入只有一个元素，则不能对其应用任何总和或其他内容。你只有一个元素。因此，结果是 acc.
consd
来源
#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 '- '-))
编辑
drop 函数用于删除列表的第 n 个元素。它可以如下所示实现。但是，您也可以改用 (rest (rest ls))。为了简洁起见，我使用它。
掉落
(define (drop ls n)
(cond [(empty? ls)
ls]
[(>= 0 n)
ls]
[else
(drop (rest ls) (- n 1))]))