Блог

У меня проблема с написанием функции (sublist list from to) , которая использует два параметра, from и to , и создает подпоследовательность из списка, который начинается с индекса from и заканчивается перед индексом to , с которого начинается индексация 0 . Например,

  (sublist '(a b c d e f g h) 1 4) ==> '(b c d)
 (sublist '(a b c d e f g h) 1 1) ==> '()
 (sublist '(a b c d) 0 30) ==> '(a b c d)
 

Я понимаю, что если нам разрешено использовать локальные вспомогательные функции, мы можем написать вспомогательную функцию, которая подсчитывает 0 и продолжает оттуда.

Однако, если нам не разрешено использовать local , возможно ли использовать только встроенные функции списка более высокого порядка и функции lambda для решения этой проблемы? С благодарностью!

Все, что вы можете сделать с помощью вспомогательной функции, вы можете сделать с помощью рекурсии в основной функции, изменив назначение ее аргументов.

Например, вы sublist ожидаете целых чисел в качестве своего 2-го и 3-го параметра; вы можете поместить туда что угодно (обычно список с тегами, например (list 'sublist_internal_invocation n1 n2 ...) ) и заставить вашу функцию реагировать на этот факт, зная, что она сама поместила его туда, т. Е. Таким Образом он используется в качестве собственного помощника.

То есть, если в этом есть необходимость. В вашем случае, вероятно, нет, т. Е. Его можно просто записать как простую рекурсивную функцию, увеличивая список и / или индексы при каждом рекурсивном вызове.

Чтобы дать вам подсказку,

      (sublist '(a b c d e f g h) 1 4)
 

совпадает с

        (sublist '(b c d e f g h) 0 3)
 

и это то же самое, что

 (cons 'b (sublist '(c d e f g h) 0 2))
 

Верно?

Таким образом (sublist '(d e f g h) 0 1) (cons 'd (sublist '(e f g h) 0 0)) , и, следовательно (sublist '(e f g h) 0 0) , должно быть '() .

обновление: если по какой-то причине прямая рекурсия — это не то, что вы хотите, приведенное выше вписывается в foldr парадигму, поэтому действительно может быть переведено в нее; хотя и с изюминкой. foldr определяется так, что

 (foldr g z (cons x xs))  ==  (g x (foldr g z xs))   ; AND
(foldr g z (list))  ==  z
 

Таким образом, мы видим, что для соответствия приведенным выше примерам g необходимо определить так, чтобы

 ((g x (foldr g z xs)) i j)  ==  
   ==  (cons x ((foldr g z xs) i (- j 1)))  , WHEN i == 0, j > i   ; OR
   ==  ((foldr g z xs) (- i 1) (- j 1))     , WHEN i > 0, j > i    ; OR
   ==  (list)                               , OTHERWISE            ; AND

((foldr g z (list)) i j)
   ==  (z i j)
   ==  (list)
 

Третий случай в первом предложении учитывает также возможность того, что индексы, предоставленные пользователем, были недействительными; а второе предложение определяет определение z .

Теперь осталось просто записать все это с помощью обычного lambda синтаксиса:

 (define (sublist xs i j)
  ((foldr 
     (lambda (x ys) 
       (lambda (i j)
         (cond 
           ((and (= i 0) (> j i))
             (cons x (ys i (- j 1))))
           ((and ...... )
                     ............)
           (else
             (list)))))
      (lambda (i j)
             ......)
      xs)  i  j ))
 

Более простая возможность

 (define (sublist xs i j)
  (map .....
    (filter
      (lambda (xk)
         (and (>= (cadr xk) .....) (..... (cadr xk) .....)))
      (map list
           xs
           (build-list (....... xs) (lambda (x) x))))))
 

Вам нужно будет заполнить недостающие части по точкам.

Да, это возможно сделать, и ключ думает о том, что from и to означает:

• если from больше нуля, это означает, что мы еще не в начале интересного фрагмента списка, поэтому мы хотим просто повторить попытку в конце списка, но с from amp; to на единицу меньше, чем в настоящее время;
• если to равно нулю, то мы находимся в конце интересного фрагмента списка и хотим немедленно вернуться '() ;
• в противном случае мы активно собираем элементы, поэтому организуйте сбор первого элемента в сочетании со сбором элементов из хвоста списка, опять же с from и to на единицу меньше их текущих значений (на самом деле вам не нужно беспокоиться о вычитании чего-либо из from ).

Обратите внимание, что в этом коде нет проверок работоспособности: в реальной жизни вы хотели бы выполнить первоначальную проверку того, что from и to являются нормальными.

Использование map filter second range list lambda < -

 (define (sublist lst from to)
  (map second (filter (lambda (p) (< (- from 1) (car p) to))
                      (map list (range (length lst)) lst))))
 

0. Соедините каждый элемент lst с его индексным номером.
   (map list (range (length lst)) lst) .
1. фильтр для пар (< (- from 1) index-number to) . (filter <condition-fulfiller> <index-paired lst>) .
2. С помощью (map second ...) снова удалите номера индексов.

Рекурсивное решение с конечным вызовом

 (define (sublist lst from to (acc '()))
  (cond ((or (empty? lst) (zero? to)) (reverse acc))
        ((zero? from) (sublist (cdr lst) 0 (- to 1) (cons (car lst) acc)))
        (else (sublist (cdr lst) (- from 1) (- to 1) acc))))
 

Соберите текущий первый элемент lst и отправьте промежуточные результаты в acc whenever from равно нулю, но lst не является ни пустым, ни to еще не равен нулю. На каждом шаге, переходя от элемента к элементу, уменьшайте from и to на единицу, за исключением from того, что уже равно нулю, затем передайте ноль для from .