"reduction on infixes" 在球拍中？

Question

我正在处理一个编译器通道并希望删除多余的 movq 指令。例如，这个列表：

((movq a b)
 (movq b c)
 (movq c d)
 (movq d e))

应该变成((movq a e)).

同样，列表

((movq a b)
 (movq b c)
 (addq 20 c)
 (movq a b)
 (movq c d)
 (movq d e))

应该减少到这个：

((movq a c)
 (addq 20 c)
 (movq a b)
 (movq c e))

如果当前的目标与下一个的源匹配，我当前的（工作）方法会融合当前和下一个 movq 指令：

(define (fuse-movq lst) ;; ((movq x y) (movq y z)) => ((movq x z))
  (match lst
    [`(,x) `(,x)]
    [else
     (define-values (x z) (values (car lst) (cddr lst)))
     (match* (x (cadr lst))
       [(`(movq ,a ,b) `(movq ,b ,c)) (fuse-movq (cons `(movq ,a ,c) z))]
       [(_ _) (append (list x) (fuse-movq (cdr lst)))])]))

这很好，但我更希望将逻辑与列表遍历分开，更像这样：

;; core logic
(define (fuse-movq x y)
  (match* (x y)
    [(`(movq ,a ,b) `(movq ,b ,c)) `(movq ,a ,c)]
    [(_ _) (x y)]))

;; list traversal handled by `foldl`
(foldl fuse-movq '() '((movq a b) (movq b c) (movq c d)))

可惜foldl好像不太对，map不行因为我要处理"this and the next element".

我用 APL 和 J 标记了它，因为将中缀函数 f 应用到 J 中列表 lst 的惯用方法是 f/\lst。其中f/大致翻译为apply f between the next 2 elements，\为prefix scan。它在那些语言中很常见，我希望在 Racket 中找到类似的成语。

在 Racket 中，有没有办法将这种 "infix" 函数行为与列表遍历分离？

Answer 1

您应该能够针对您的用例进行调整。

#lang racket

(define (transform xs)
  (for/fold ([prev (list (first xs))] #:result (reverse prev))
            ([item (in-list (rest xs))])
    (match* (prev item)
      [((list (list p q) xs ...) (list q r)) (cons (list p r) xs)]
      [(xs item) (cons item xs)])))

(transform '([a b] [c d] [d e] [e f] [s t] [g h] [h k] [x y] [y z]))
;=> '((a b) (c f) (s t) (g k) (x z))

"reduction on infixes" 在球拍中？

"reduction on infixes" in Racket?

functional-programming

scheme

racket

j

apl