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

Question

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

(position '((a b) c))

应该返回：

'((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))

时，返回

'((0 0) 0)

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

Answer 1

有一些错误：首先请注意，每次递归调用

position

时，索引都绑定为零。

其次，看看你的 else 分支。

(+ 1 index)

的计算结果为 1（它不会更改任何变量），而

index

的计算结果为 0。该分支只能评估一件事，因此会返回最后一个，其余的被丢弃。这就是你的零的来源。

在您的函数中，您似乎试图保持全局状态（当前索引）并在每次标记叶子时修改它。 “修改状态”部分不是很好的功能风格，但如果您对此感到满意，请查看 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:

(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

使用变异来维护自己的状态的示例，以便每个列表的每个项目都有唯一的 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)))])]))

Answer 5

另一种方法是通过使用返回两个值的辅助函数来避免改变状态变量 - 转换后的列表和要使用的下一个索引。在处理父列表的其余部分时，将使用转换嵌套列表的下一个索引值。

#lang racket/base
(require racket/match srfi/1)

(define (position list)
  (define (helper list idx)
    (let loop ([list list]
               [indexed '()]
               [idx idx])
      (match list
        ['() (values (reverse indexed) idx)] ; base case - empty list
        [(cons head tail) ; pair - recurse on both parts
         (let-values ([(indexed-head next-idx) (helper head idx)])
           (loop tail (cons indexed-head indexed) next-idx))]
        [_ ; base case - atom
         (values (append-reverse indexed idx) (add1 idx))])))
  (let-values ([(indexed _) (helper list 0)]) indexed))

(module+ test
  (require rackunit)
  (check-equal? (position 'a) 0)
  (check-equal? (position '((a b) c)) '((0 1) 2))
  (check-equal? (position '((a b . c) d)) '((0 1 . 2) 3))
  (check-equal? (position '((a b) (c d) x (e (f g) h))) '((0 1) (2 3) 4 (5 (6 7) 8))))

（这利用了

(append '() x)

返回

x

的方式（SRFI-1 的

append-reverse

，具有相同的行为）来消除一些条件检查）