scheme- 编写一个类似 foldl /fold-left 的函数，它适用于给定列表的前 3 个项目

Question

我想写一个函数来获取和中缀表达式并将其更改为前缀。首先假设我们只处理 + 运算符，所以我想将表达式 1+1+1 更改为： (+ (+ 1 1) 1)

我想用 foldl 或类似 foldl 的东西来做：将列表中的第二项（始终是操作数）附加到第一项和第三项（按该顺序）然后我希望我们刚刚附加的表达式成为列表中的第一项所以我会做递归地在列表的其余部分上相同。

我试过以下方法：

(lambda (lst)
       (fold-left (lambda (pmLst)
          `(,((cadr pmLst) ,(car pmLst) (caddr pmLst)) ,(cddr pmLst)))
                        '()
                        lst))

但后来我意识到左折叠的 lambda 必须有 2 个参数，但我想处理列表的前 3 个项目。

我希望我已经说清楚了，因为它有点棘手..

Answer 1

A fold 不会做你想做的事。如果您想象表达式 (5 + 3 + 2) 然后使用带有 proc 的折叠作为过程执行此操作：

(proc 2 (proc '+ (proc 3 (proc '+ (proc 5 '())))))

一种方法是创建一个函数，使 returns 奇数和偶数元素在它们自己的列表中，以便 '(+ 2 - 3) 变为 (+ -) and (2 3) 然后你可以这样做：

(define (infix->prefix expr)
  (if (pair? expr)
      (let-values ([(ops args) (split (cdr expr))])
        (fold (lambda (op arg acc)
                (list op acc (infix->prefix arg)))
              (car expr)
              ops
              args))
      expr))

但是两者的大小都比仅仅滚动你自己的递归要大得多：

(define (infix->prefix expr)
    (define (aux lst acc)
      (if (pair? lst)
          (aux (cddr lst)
               (list (car lst)
                     acc
                     (infix->prefix (cadr lst))))
          acc))

    (if (pair? expr)
        (aux (cdr expr) (infix->prefix (car expr)))
        expr))

(infix->prefix '(1 + 2 - 3))
; ==> (- (+ 1 2) 3)

这里没有运算符优先级。一切都严格从左到右。

scheme- 编写一个类似 foldl /fold-left 的函数，它适用于给定列表的前 3 个项目

scheme- writing a foldl /fold-left like function that works on first 3 items of the given list

scheme

fold

chez-scheme