在Scheme中位置合并两个列表 [英] merging two lists positionally in Scheme

问题描述

第一个列表:(1 2 3 4)

第二个列表:(* slot (- slot (/ slot slot)))

输出:(* 1 (- 2 (/ 3 4)))

第一个列表的元素将插入第二个列表.

The first list's elements will be inserted to the second list.

第二个列表中的符号slot表示插入位置.

The symbol slot in second list means the position for insertion.

我已经编写了一个代码段，适用于上面的示例.

I have written a code snippet and it works for the above example.

(define (insert-slot numbers slots)
  (cond
    [(null? slots)
     '()]
    ;; operate on the nested list and come back to the element after
    [(pair? (car slots))
     (cons 
           (insert-slot numbers (car slots))     ;; nested list
           (insert-slot numbers (cdr slots)))]   ;; element after
    ;; insert number to slot
    [(equal? (car slots) 'slot)
     (cons (car numbers)
           (insert-slot (cdr numbers) (cdr slots)))]
    ;; just take the original element in slots
    (else
     (cons (car slots)
           (insert-slot numbers (cdr slots))))))

问题

但是，cond的第二个子句(在嵌套列表中操作)有一些问题，嵌套列表中使用的numbers和后面的元素应该不同.后一个numbers是前一个numbers的结果.对于上面的示例，它可以正常工作，但是如果第二个列表喜欢此(* (+ slot slot) (- slot slot))，则会得到错误的答案.

Problem

However, the second clause(operate on the nested list) of the cond has some problems, the numbers used in the nested list and the element after should be different. The later numbers is the result of the previous numbers. It works correctly for the example above, but if the second list likes this (* (+ slot slot) (- slot slot)), it will get the wrong answer.

我发现可以将状态存储在numbers中，并根据调用的时间返回不同的值，但这与Scheme方法不同(没有多余的存储数据).有解决这个问题的简单方法吗?

I figured out that I can store states in the numbers and return different value based on the times it has called, but it's not like the Scheme way(no extra stored data). Is there a simple way to solve this problem ?

推荐答案

TL; DR:是，带有继续通过样式.

非常有趣的问题！嵌套列表是一棵树，因此您要根据其中存在关键字'slot，将线性值列表合并到树的边缘中.

Very interesting question! Nested list is a tree, so you're merging a linear list of values into a tree's fringe, according to the presence of a keyword 'slot there.

因此，就像结构递归任务中的通常情况一样，我们首先遍历一棵树以创建它的精确副本，以获取其一生，

So we start, as is usual in structural recursions tasks, with traversing a tree to just create an exact copy of it, to get a hang of it,

(define (copy-tree tree)
    (cond
       [(not (pair? tree)) tree]                   ; return the leaf
       [else (cons (copy-tree (car tree))          ; combine results from car
                   (copy-tree (cdr tree)))]))      ;     and results from cdr

接下来，我们通过 CPS 将其线性化，

Next we linearize it by going CPS,

(define (copy-tree tree k)
    (cond
       [(not (pair? tree)) (k tree)]               ; "return" the leaf into k
       [else (copy-tree (car tree) (lambda (r)     ; collect results from car as r
               (copy-tree (cdr tree) (lambda (q)   ;  collect results from cdr as q
                 (k (cons r q))))))]))             ;   "return" combined r and q into k

然后我们遍历状态，遍历给定值的列表以替换关键字的每个实例:

and then we thread our state through, traversing the list of given values to substitute for each instance of the keyword:

(define (merge-tree-fringe vals tree keywd k)
  (cond
    [(not (pair? tree))                  ; for each leaf:
     (if (not (eq? tree keywd))          ; if it is not the keyword,
       (k vals tree)                     ;   "return" vals AND leaf into k, or
       (k (cdr vals) (car vals)))]       ;   USE the first of vals, if it is
    [else
     (merge-tree-fringe vals (car tree) keywd (lambda (Avals r)    ; collect from car,
      (merge-tree-fringe Avals (cdr tree) keywd (lambda (Dvals q)  ;  collect from cdr,
       (k Dvals (cons r q))))))]))       ; return the last vals and the combined results

我们称其为

> (merge-tree-fringe '(1 2 3 4) 
                     '(* slot (- slot (/ slot slot))) 
                     'slot
                     (lambda (v r) r))
'(* 1 (- 2 (/ 3 4)))

> (merge-tree-fringe '(1 2 3 4) 
                     '(* (+ slot slot) (- slot slot))
                     'slot
                     (lambda (v r) r))
'(* (+ 1 2) (- 3 4))

可以通过添加错误检查并将其转换为名称更短且参数更少的内部定义来进一步清理.

This can be further cleaned up by adding error checking, and converting to an internal definition with shorter name and fewer arguments.

edit:在一个模式匹配的伪代码中，它可能更易于阅读/遵循，是

edit: In a pattern-matching pseudocode, which might be easier to read/follow, it is

merge-tree-fringe vals tree keywd = g vals tree (v r => r)
  where
  g vals [a, ...d] k = g vals a (avals r =>
                           g avals d (dvals q => 
                               k dvals [r, ...q]))
  g [v, ...vs] lf  k 
             | lf == keywd = k vs   v     -- use first value for a matching leaf
  g vals       lf  k       = k vals lf

这种通过计算将变化的状态线程化的计算模式正是(哈斯克尔的)State monad所要实现的；上面的代码会写在这里(没有"tree"类型的细节)为

This computational pattern of threading a changing state through the computations is exactly what (Haskell's) State monad is about; the above would be written there (sans the particulars of the "tree" type) as

merge_tree_fringe vals tree keywd = evalState (g tree) vals
    where
    g (a:d)            = do { r <- g a ; q <- g d ; return (r:q) }
    g lf | lf == keywd = do { (v:vs) <- get ; put vs ; return v }
         | otherwise   = do { return lf }

其中状态(我们的值")作为有状态计算管道"的一部分隐式传递，并具有自动正确的排序(我们必须手动小心地使用avals和dvals手动进行处理)每个在我们的计划代码中的适当位置)；和evalState会执行整个组合计算，同时丢弃最终状态，就像我们的收集器/连续函数(lambda (v r) r)一样，仅返回最终计算出的值.

where the state - our "values" - is passed around as part of a "stateful computation pipeline" implicitly, with automatically correct sequencing (which we had to take care of manually, using the avals and dvals carefully each in its appropriate place in our Scheme code); and evalState performs this whole combined computation while discarding the end state, returning only the finally computed value just like our collector/continuation-function (lambda (v r) r) did.

将后者转换为前者只是一个纯粹的句法转换问题.因此，这没什么特别的，这是monad 的东西，毕竟.它是一种一种计算模式，已被说明，捕获.

Turning the latter into the former is a matter of a purely syntactic transformation. So it's nothing special, this "monad" thing, after all. It's a computational pattern, explicated, captured.

这篇关于在Scheme中位置合并两个列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！