Scheme

Question

我正在尝试用它的位置替换方案列表中的元素。例如，调用：

(position '((a b) c))

应该return:

'((0 1) 2)

到目前为止，我的代码保持列表格式，但索引没有更新。

(define (position term1)
  (define index 0)
    (cond [(null? term1) '()]
          [(list? term1) (cons (position (car term1)) (position(cdr term1)))]
          [else (+ 1 index) index]))

调用(position '((a b) c))时，returns

'((0 0) 0)

有人可以解释为什么索引没有更新吗？

Answer 1

有几处错误：首先请注意，每次递归调用 position，索引都绑定为零。

其次，查看您的 else 分支。 (+ 1 index) 的计算结果为 1（它不更改任何变量），index 的计算结果为 0。此分支只能计算一件事，所以最后一个被返回，其余的被丢弃。这就是你的零的来源。

在你的函数中，你似乎试图保持全局状态（当前索引）并在每次标记叶子时修改它。 "modifying state" 部分不是很好的函数式样式，但如果您对此没问题，请查看 set!.

Answer 2

这是使用 CPS 的一种解决方案：

#lang racket

(define (index xs [i 0] [continue (λ (xs i) xs)])
  (match xs
    [(cons x xs) (index x i
                        (λ (js j)
                          (index xs j
                                 (λ (ks k)
                                   (continue (cons js ks) k)))))]
    ['()         (continue '() i)]
    [x           (continue i (+ i 1))]))

; Example
;(index '((a b) (c d) x (e (f g) h)))
; '((0 1) (2 3) 4 (5 (6 7) 8))

此处(index xs i continue)将xs中的元素替换为索引，计数从i开始。假设索引 xs 的结果是 js，然后使用索引结果调用 continue 和下一个要使用的索引：(continue js j).

Answer 3

Daenerys Naharis 已经指出了问题所在，所以让我指出一些您可能不知道的 Scheme 和 Racket 的功能，您可以在保持函数式风格的解决方案中使用这些功能。

这叫做命名的让:

(let loop ((index 0)
           (result '()))
   (if (= index 10)
       (reverse result)
       (loop (+ 1 index) (cons index result)))

在 let 形式中，loop 被绑定为一个将所有局部变量作为参数的函数。递归调用它会调用 let 表单本身。这样你就可以使 index 成为一个参数，而不用将其作为 position 的一个参数。您还可以将结果放在一个参数中，这样您就可以对 loop 进行尾调用。

另一个特性在现有的 Scheme 实现中不太普遍：可选参数。在 Racket 中，它们是这样定义的：

(define (position term1 (index 0)) ...)

然后 position 可以使用或不使用 index 参数调用。

Answer 4

一个使用 mutation 的例子维护它自己的状态，这样每个列表的每个项目都有一个唯一的 id。

用法示例：

> (position '((a b) c))
'((0 1) 2)
> (position '((a b) c (d (e))))
'((3 4) 5 (6 (7)))

示例实现：

#lang racket

(provide position)

(define base -1)

(define (indexer)
  (set! base (add1 base))
  base)

(define (position list-of-x)
  (cond [(null? list-of-x) null]
        [else
         (define head (first list-of-x))
         (cond [(list? head) 
                (cons (position head)
                      (position (rest list-of-x)))]
               [else (cons (indexer) 
                           (position (rest list-of-x)))])]))

Scheme - 用索引替换列表中的元素

Scheme - Replacing elements in a list with its index

racket