在球拍中将列表重新排列为左正常形式

Question

我本来打算 post 把这个提交给 codereview stackexchange，但我看到你应该只 post 工作代码。我之前问过这个问题：

如果您不检查 link，基本上我想重新排列一个符号列表，这样：

'((a + b) + c) -> '(a + (b + c))

或者这个：

'((a + b) + (c + d)) -> '(a + (b + (c + d)))

这是我到目前为止编写的代码：

(define (check? expr)
  (display expr)
  (newline)
  (cond ((null? expr) -1)
        ((and (atom? (car expr)) (atom? (cadr expr))) 0) ;case 0
        ((and (atom? (car expr)) (list? (cadr expr))) 1) ;case 1
        ((and (list? (car expr)) (null? (cdr expr))) (check? (car expr))) ;nested expression for example '((a b))
        ((and (list? (car expr)) (atom? (cadr expr))) 2) ;case 2
        ((and (list? (car expr)) (list? (cadr expr))) 3) ;case 3
        (else -1)))


(define (rewrite x)
  (display (check? x))
  (newline)
  (cond ((null? x))
        ((atom? x) x)
        ((= 0 (check? x))   x) ;case 0 is '(a + b)
        ((= 1 (check? x)) (cons (car x) (rewrite (cdr x)))) ;case 1 is '(a +  (b + c))
        ((= 2 (check? x)) (rewrite (list (caar x) (cons (cadar x) (cdr x))))) ;case 2 is ((b + c) + a)
        ((= 3 (check? x)) (rewrite ((list (caar x) (cons (cadar x) (cdr x))))))));case 3 is ((a + b) + (c + d))


;(rewrite '(((d c) b) a))
(rewrite '(a b))
(rewrite '(a (b c)))
(rewrite '((a b) (c d)))

我走在正确的轨道上吗？如果没有，有人有任何指示吗？我创建的列表有误吗？如果您需要更多信息，请告诉我，或者如果我应该更好地评论代码，也请告诉我。

如果你不检查之前的问题，这是我得到的答案（非常有帮助）：

var                               -> var
(var + var)                       -> (var + var)
(var + (fip1 + fpip2))            -> (var + (REWRITE (fip1 + fpip2))
((fip1 + fpip2) + var)            -> (REWRITE (fip1 + (fip2 + var))
((fip1 + fpip2) + (fip3 + fpip4)) -> (REWRITE (fip1 + (fip2 + (fip3 + fip4))))

Answer 1

以下是您为语法定义的语法：

var  ::=  a | b | c | d | e | f | g
fpip ::=  var | (fpip + fpip)

因此，我们可以从定义谓词开始，使用上面设置的规则来测试给定表达式是否有效：

(define (var? e)
  (member e '(a b c d e f g)))

(define (fpip? e)
  (cond
    ((var? e) #t)
    ((or (not (pair? e))
         (null? e)
         (null? (cdr e))
         (null? (cddr e))
         (not (null? (cdddr e))))
     #f)
    (else (and (fpip? (car e))
               (equal? (cadr e) '+)
               (fpip? (caddr e))))))

现在我们可以说，例如：

> (fpip? 'a)
#t
> (fpip? '((a + b) + c))
#t
> (fpip? '((+(d + e) + f) + (a + (a + c))))
#f

有了这个，如果表达式是有效的 fpip，rewrite 可以写成表达式的右结合形式，否则 #f：

(define (rewrite e)
  (if (not (fpip? e))
      #f
      (rewrite-fpip e)))

接下来，我们将rewrite-fpip定义为接受和转换任何有效 fpip的过程，如下：

(define (rewrite-fpip e)
  (cond
    ((not (pair? e)) e)                                         ;; var
    ((not (pair? (car e)))
     (list (car e) '+ (rewrite-fpip (caddr e))))                ;; (var + fpip)
    (else
     (rewrite-fpip                                              ;; (fpip + fpip)
      (list (caar e) '+ (list (caddar e) '+ (caddr e)))))))

因此我们可以有：

> (rewrite 'a)
'a
> (rewrite '((a + b) + c))
'(a + (b + c))
> (rewrite '((a + b) + (c + d)))
'(a + (b + (c + d)))
> (rewrite '(((d + e) + f) + (a + (a + c))))
'(d + (e + (f + (a + (a + c)))))

Answer 2

他们告诉你不要在你的解决方案中使用 flattening 并不意味着你不能在 derivation 中使用扁平化] 你的解决方案。

编写虚构的模式匹配等式伪代码（因为它更短且视觉上明显，即更容易理解），

flatten a         = flatten2 a []               ; [] is "an empty list"
flatten2 (a+b) z  = flatten2 a (flatten2 b z)   ; if it matches (a+b)
flatten2 a     [] = a                           ; if it doesn't, and the 2nd is []
flatten2 a     b  = a + b                       ; same, and the 2nd arg is not []

哦，等等，我不是在这里展平它，我是在这里构建归一化求和表达式！

这种方法的唯一问题是在我们知道时一遍又一遍地重复检查[]它只会是真的一次 -- 毕竟是我们写了这段代码

融合这些知识，我们得到

normalize  a   = down a             ; turn EXPR ::= ATOM | EXPR + EXPR
down (a + b)   = up a (down b)
down a         = a                  ; into NormExpr ::= ATOM | ATOM + NormExpr
up   (a + b) z = up a (up b z)
up   a       b = a + b

现在剩下的就是在常规 Scheme 中对此进行编码。 Scheme 还有一个好处就是测试可以简化到 just

(define (is-sum? a+b) (pair? a+b))

编辑： 同一伪代码中另一个答案的最终函数是：

rewrite ((a + b) + c) = rewrite (a + (b + c))     ; rotate right!
rewrite (a + b)       = a + rewrite b             ; go in, if the first rule didn't match
rewrite a             = a                         ; stop, if the first two didn't match

它重新排列 + 节点的树结构 before 开始工作¹，而此答案中的解决方案如下输入结构而对其进行转换。结果，由于嵌套递归，运行时间堆栈将仅与输入结构一样深，而对于 rewrite，它将始终是 n 层在最深处，当列表在堆栈上完全线性化时（在第二条规则中），就在总和在返回的路上组装之前。

但是rewrite中第一个规则是尾递归，第二个规则是tail recursive modulo cons，所以rewrite整体可以改写成尾递归的风格，很少标准修改。这绝对是一个加号。

另一方面，这个新代码将不得不手术修改（即变异）+ 节点（有关详细信息，请参阅上面链接的维基百科文章），因此您必须选择您的实现此数据类型相应。如果你使用列表，这意味着使用 set-car! and/or set-cdr!;否则你可以将它们实现为 Racket's #:mutable structures。构建结果后，如果需要，您可以通过额外的 O(n) 遍历将其转换为常规列表。

¹ 让人想起 John McCarthy 的 the old gopher trick，深入到输入结构中，具体化延续。

在球拍中将列表重新排列为左正常形式

Rearranging list into left-normal form in Racket

scheme

list

normalization

recursive-descent

racket