在 Racket 中对列表进行细分

Question

我想在 Scheme 中创建一个函数，以一种我可以给出开始细分的值和停止细分的值的方式从列表中生成子列表，如下所示：

(function '(1 2 3 1 4 5 6 3) 1 3)
>'((1 2 3) (1 4 5 6 3))

而且我找不到正确的方法，正如您所看到的，该函数会以 1 开始一个子列表并以 3 结束它，我该如何实现这样的事情？

Answer 1

这是非贪婪的，所以它会做出最短的答案（在遇到开始后停在最开始的一端）并在最后一个结束位置之后继续寻找匹配项。这是一个你自己的解决方案，没有花哨的列表过程，但它也是尾递归的。

(define (sublist src start end)
  (let loop ((lst src) (acc #f) (results '()))
    (cond 
      ((null? lst) (reverse results)) ; remove reverse if the order of matches isn't an issue
      ((not acc) (loop (cdr lst) (if (eqv? (car lst) start) (list (car lst)) #f) results))
      ((not (eqv? (car lst) end)) (loop (cdr lst) (cons (car lst) acc) results))
      (else (loop (cdr lst) #f (cons (reverse (cons (car lst) acc)) results))))))


(sublist '(1 2 1 3 2 2 2 2 2) 1 2) ; ==> ((1 2) (1 3 2))
(sublist '(1 2 3 1 4 5 6 3 1 4 8 7 9 5) 4 5) ; ((4 5) (4 8 7 9 5))

对于找到重叠结果的东西，这可能有效：

(define (sublist-full src start end)
  (let loop ((lst src) (acc #f) (backtrack #f) (results '()))
    (if (null? lst)
        (if backtrack 
            (loop backtrack #f #f results)
            (reverse results))
        (let ((a (car lst)))
          (if acc
              (cond ((and (eqv? a start) (not backtrack)) (loop (cdr lst) (cons a acc) lst results))
                    ((eqv? a end) (loop (cdr lst) (cons a acc) backtrack (cons (reverse (cons a acc)) results)))
                    (else (loop (cdr lst) (cons a acc) backtrack results)))
              (if (eqv? a start)
                  (loop (cdr lst) (cons a '()) #f results)
                  (loop (cdr lst) #f #f results)))))))

(sublist-full '(1 2 1 3 2 2 2 2 2) 1 2) 
; ==> ((1 2) (1 2 1 3 2) (1 2 1 3 2 2) (1 2 1 3 2 2 2) 
;      (1 2 1 3 2 2 2 2) (1 2 1 3 2 2 2 2 2) (1 3 2) 
;      (1 3 2 2) (1 3 2 2 2) (1 3 2 2 2 2) (1 3 2 2 2 2 2))

Answer 2

这是我能想到的最好的方法——毫无疑问，还有更优雅的方法。

想法是在找到 "start" 值之前删除所有内容，然后保留所有内容直到找到 "stop" 值（如果有的话），然后递归遍历剩余的列表。

#lang racket
(require srfi/1) ; For drop-while

(define (subdiv ls start stop)
  (let ([part-one (drop-while (lambda (x) (not (= x start))) ls)])
    (let-values ([(main rest) (splitf-at part-one (lambda (x) (not (= x stop))))])
      (if (null? rest)         ; empty means the stop value wasn't found
          '()
          (cons (append main (list stop)) 
                (subdiv (cdr rest) start stop))))))

示例：

> (subdiv '(3 4 5 1 111 1 1 1 2 2 3 1 2) 1 2)
'((1 111 1 1 1 2) (1 2))
> (subdiv '(3 4 5 1 2 3 1 2) 1 2)
'((1 2) (1 2))
> (subdiv '(1 2) 1 2)
'((1 2))
> (subdiv '(1) 1 2)
'()
>

在 Racket 中对列表进行细分

Make subdivisions of lists in Racket

scheme

function

list

racket