将函数更改为 CPS 样式 [英] Changing a function into CPS style

问题描述

我们被要求编写一个程序，当给定一个列表时，它将替换给定元素的第一次出现，并且只替换第一个，但问题是用 CPS 风格编写.我们无法将其转换为 CPS 风格的书面程序，该程序给出了成功连续和失败连续..

We were asked to write a procedure that when given a list it will replace the first occurrence of a given element and only the first, but the catch is to write in CPS style. We are unable to turn it to CPS style written procedure that is given a success-cont and fail-cont..

如果有人愿意尝试，我们将不胜感激:]

If anyone is willing to give it a try we will really appreciate it :]

我们拥有的程序(由 此处的答案慷慨提供):

The procedure we have (graciously provided by answers here):

(define (replace-one list old new)
  (cond ((pair? list)
         (let ((next (replace-one (car list) old new)))
           (cons next 
                 (if (equal? next (car list))            ; changed?
                     (replace-one (cdr list) old new)    ;   no,  recurse on rest
                     (cdr list)))))                      ;   yes, done
         ((eq? list old) new)
         (else list)))

推荐答案

已编辑

非常感谢@WillNess 指出并修复了潜伏在原始代码中的错误.这是基于他的 代码(逐步推导) 的更正实现，评论并为 Racket 制作了惯用语:

A big thanks to @WillNess for pointing out and fixing a bug, lurking in the original code. Here's a corrected implementation based on his code (with stepwise derivation), commented and made idiomatic for Racket:

(define (replace-one lst a b)
  (let loop ([lst lst]                ; input list
             [f #f]                   ; have we made the first replacement?
             [k (lambda (ls f) ls)])  ; continue with results: list and flag
    (cond 
      (f                              ; replaced already: 
        (k lst f))                    ; continue without changing anything
      ((empty? lst)                   ; empty list case
        (k lst f))                    ; go on with empty lst and flag as is
      ((not (pair? lst))              ; - none replaced yet - is this an atom?
        (if (eq? lst a)               ; is this the atom being searched?
            (k b #t)                  ; replace, continue with updated flag
            (k lst f)))               ; no match, continue
      (else                           ; is this a list?
        (loop (first lst)             ; process the `car` of `lst`
          f                           ; according to flag's value, and then
          (lambda (x f)               ; accept resulting list and flag, and
            (loop (rest lst)          ; process the `cdr` of `lst`
              f                       ; according to new value of flag, 
              (lambda (y f)           ; getting the results from that, and then
                (if f                 ; - if replacement was made -
                  (k                  ; continuing with new list, built from
                    (cons x y)        ; results of processing the two branches,
                    f)                ; and with new flag, or with 
                  (k lst f))))))))))  ; the old list if nothing was changed

请注意，使用了单个成功延续(在上面的代码中称为 k)，它接受 两个 结果值:列表和标志.初始延续只返回最终结果列表，并丢弃最终标志值.我们还可以返回标志，以指示是否已经进行了替换.它在内部使用以尽可能多地保留原始列表结构，像往常一样使用持久数据类型(如在此答案中所见).

Notice that a single success continuation is used (called k in the code above) which accepts two resulting values: the list and the flag. The initial continuation just returns the final resulting list, and discards the final flag value. We could also return the flag, as indication of whether the replacement have been made at all or not. It is used internally to preserve as much of original list structure as possible, as usual with persistent data types (as seen in this answer).

最后，始终测试您的代码:

Finally, always test your code:

; fixed, this wasn't working correctly
(replace-one '((((1 2) 3 4) a) 6) 'a 'b)
=> '((((1 2) 3 4) b) 6)

(replace-one '(((-))) '- '+)
=> '(((+)))

(replace-one '((-) - b) '- '+)
=> '((+) - b)

(replace-one '(+ 1 2) '+ '-)
=> '(- 1 2)

(replace-one '((+) 1 2) '+ '-)
=> '((-) 1 2)

(replace-one '(1 2 ((+)) 3 4) '+ '-)
=> '(1 2 ((-)) 3 4)

(replace-one '() '+ '-)
=> '()

(replace-one '(1 2 ((((((+ 3 (+ 4 5)))))))) '+ '-)
=> '(1 2 ((((((- 3 (+ 4 5))))))))

这篇关于将函数更改为 CPS 样式的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！