Trouver deux éléments de la liste dans l'ordre croissant du nombre donné

Question

Je veux écrire une fonction qui recherche deux éléments dont un nombre donné se situe entre; (element1 < num < element2), et leur position du premier élément dans la liste.

;; 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) 

Je dois utiliser (car (filter list? x)) pour éliminer #<void> sorties dans x, ce qui entraîne '(#<void> #<void> #<void> #<void> #<void> #<void> #<void> #<void> #<void> #<void> #<void> #<void> (4 5 12) #<void> #<void> #<void> #<void> #<void>).

Comment puis-je empêcher ceux #<void> dans la liste qui sort de for/list dans x? Il semble qu'il y ait des étapes inutilement plus longues dans la fonction find-interval. Toutes les suggestions sont les bienvenues et appréciées.

Answer 1

Si l'on suppose que la liste est toujours dans l'ordre croissant, la fonction peut être définie par une simple queue-récursion qui est compilé de manière itérative:

(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 nom peut être utilisé ici pour tester par la liste:

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

Il retourne #f si cette condition ne se produit pas dans la liste.

version suivante produira une liste de listes indiquant plusieurs endroits où la condition est 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)) 

La liste d'entrée n'a pas besoin d'avoir des éléments dans un ordre de tri dans l'une des fonctions ci-dessus.