指定された数字の昇順にリストから2つの要素を見つける

Question

与えられた数字が間にある2つの要素を検索する関数を書いてみたいと思います。 （element1 < num < element2）、およびリスト内の最初の要素の位置。

;; check x is between num-1 and num-2 
(define (in-between? x num-1 num-2) 
     (or (and (> num-1 x) (< num-2 x)) 
      (and (> num-2 x) (< num-1 x)))) 

;; the list elements values are always in ascending order 
(define lst '(0 0 0 1 1 1 2 2 2 3 3 4 4 5 5 6 6 6 7)) 

(define num 4.5) 
;; expected-output=> 4.5 lies between element 4 and 5 of lst 
;; '(4 5 12) ;; 12 is the position of first-element 

;; output is list of 2 elements and the position of first-element 
(define (find-interval u lst) 
    (let* ([x (for/list ([a (drop-right lst 1)] 
         [b (cdr lst)] 
         [i (in-naturals)]) 
       (when (in-between? u a b) 
       (list a b i)))]) 
    (car (filter list? x)))) ; to remove all #<void> 
;; => '(4 5 12) 

Iは '(#<void> #<void> #<void> #<void> #<void> #<void> #<void> #<void> #<void> #<void> #<void> #<void> (4 5 12) #<void> #<void> #<void> #<void> #<void>)を得され、xに#<void>出力を排除する(car (filter list? x))を使用しなければなりません。

リスト内の#<void>が出てこないようにするにはfor/listにxを入れますか？ find-interval機能に不必要に長いステップがあるようです。すべての提案は歓迎され、感謝しています。

Answer 1

リストは昇順に常にあると仮定すると、関数は、反復方法でコンパイルされる単純な末尾再帰を使用して定義することができます。

(define (find-interval el lst (pos 0)) 
    (cond ((null? lst) '()) 
     ((null? (cdr lst)) '()) 
     ((>= (car lst) el) '()) 
     ((< (car lst) el (cadr lst)) (list (car lst) (cadr lst) pos)) 
     (else (find-interval el (cdr lst) (+ 1 pos))))) 

(find-interval 4.5 '(0 0 0 1 1 1 2 2 2 3 3 4 4 5 5 6 6 6 7)) ; => '(4 5 12) 

Answer 2

は、名前付きletが通じテストするために、ここで使用することができますリスト：

(define (find-interval u lst) 
    (let loop ((idx 1)) 
    (if (= idx (length lst)) 
     #f 
     (begin (let ((a (list-ref lst (sub1 idx))) 
        (b (list-ref lst idx))) 
       (if (in-between? u a b) 
        (list a b (sub1 idx)) 
        (loop (add1 idx)))))))) 

このような条件がリストにない場合は#fを返します。

バージョン条件がsatifiedされた複数の位置を示すリストのリストを生成する次のとおり

(define (find-interval u lst) 
    (let loop ((idx 1) 
      (ol '())) 
    (if (= idx (length lst)) 
     (reverse ol) 
     (begin (let ((a (list-ref lst (sub1 idx))) 
        (b (list-ref lst idx))) 
       (if (in-between? u a b) 
        (loop (add1 idx) (cons (list a b (sub1 idx)) ol)) 
        (loop (add1 idx) ol))))))) 

(find-interval 4.5 '(0 0 0 1 1 1 2 2 2 3 3 4 4 5 5 6 6 6 7 4 6)) 
; => '((4 5 12) (7 4 18) (4 6 19)) 

入力リストを上記の関数のいずれかでソート順にアイテムを有する必要はありません。