将功能更改为CPS样式

作者: 流浪海。
发布时间: 2024-02-20 02:32:34 (5月前)
转自：

3 条回复

0#
回复此人
v-star*위위 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> 的 EDITED </强> 非常感谢@WillNess指出并修复了一个错误，潜伏在原始代码中。这是基于他的修正实施 <a href="http://ideone.com/AbWKxS" rel="nofollow noreferrer"> 代码（逐步推导） </A> ，评论并为Racket做了惯用法： <pre> <code> (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 </code> </pre> 请注意，使用单个成功延续（称为 <code> k </code> 在上面的代码中）接受 二 结果值：列表和标志。初始延续只返回最终结果列表，并丢弃最终标志值。我们也可以返回标志，作为是否完全替换的指示。内部使用它来保留尽可能多的原始列表结构，就像常见的持久数据类型一样（如图所示） <a href="https://stackoverflow.com/a/18859156/849891"> 在这个答案 </A> ）。 最后，始终测试您的代码： <pre> <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)))))))) </code> </pre> </DIV>

编辑
1#
回复此人
甲基蓝 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> OP要求进行两次延续的转变 - 成功和失败。这很容易做到：我们从CPS版本的深拷贝开始（ car-cdr递归 ），像往常一样，然后我们想象我们有两种方法来返回一个值：当我们刚刚找到旧值时，我们将返回新值，而不再继续查看;如果我们还没有找到它 - 在这种情况下我们会返回我们拥有的并将继续寻找它。 <pre> <code> ;; replace first occurence of a inside xs with b, ;; using two continuations - success and failure (define (rplac1_2 xs a b) (let g ((xs xs) (s (lambda (x) x)) ; s is "what to do on success" (f (lambda () xs))) ; f is "what to do on failure" (cond ((null? xs) (f)) ; nowhere to look for `a` anymore ((not (pair? xs)) (if (eq? xs a) (s b) ; success: `a` found: "return" `b` instead (f))) ; nowhere to look for `a` anymore (else (g (car xs) (lambda (x) ; if succeded on (car xs), with `x` the result (s (cons x (cdr xs)))) (lambda () ; if failed (nothing replaced yet, keep trying) (g (cdr xs) (lambda (y) ; if succeeded on (cdr xs), with `y` the result (s (cons (car xs) y))) f))))))) ; if none replaced </code> </pre> 这样我们实际上被迫尽可能地保留原始列表结构。 <a href="http://ideone.com/E7fxGz" rel="nofollow"> 测试它 </A> 同 <pre> <code> (display (rplac1_2 '((((a 2) 3 4) a) 6) 'a 'b)) (display (rplac1_2 '((((c 2) 3 4) a) 6) 'a 'b)) (display (rplac1_2 '((((c 2) 3 a) a) 6) 'a 'b)) </code> </pre> 正确地产生 <BLOCKQUOTE> （（（（b 2）3 4）a）6） （（（（c 2）3 4）b）6） （（（（c 2）3 b）a）6） </BLOCKQUOTE> </DIV>

编辑

登录后才能参与评论