Quiero escribir una función que busque dos elementos entre los que se encuentra un número dado; (elemento1

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

Tengo que usar (car (filter list? x)) para eliminar #<void> salidas en x, lo que resulta '(#<void> #<void> #<void> #<void> #<void> #<void> #<void> #<void> #<void> #<void> #<void> #<void> (4 5 12) #<void> #<void> #<void> #<void> #<void>).

¿Cómo evito que los #<void> de la lista salgan de for/list en x? Parece que hay pasos innecesariamente más largos en la función find-interval. Todas las sugerencias son bienvenidas y apreciadas.

0
Toat 13 dic. 2016 a las 12:28

2 respuestas

La mejor respuesta

Suponiendo que la lista está siempre en orden ascendente, la función se puede definir con una recursividad de cola simple que se compila de forma iterativa:

(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)
1
Renzo 13 dic. 2016 a las 10:15

Aquí se puede usar un let con nombre para probar a través de la lista:

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

Devuelve #f si tal condición no ocurre en la lista.

La siguiente versión producirá una lista de listas que indican múltiples ubicaciones donde se satisface la condición:

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

No es necesario que la lista de entrada tenga elementos ordenados en ninguna de las funciones anteriores.

1
rnso 14 dic. 2016 a las 02:57