Схема - возвращение первых n-элементов массива - PullRequest
Новая
       3

Схема - возвращение первых n-элементов массива

0 голосов
/ 12 марта 2019

Я пытаюсь написать функцию в Scheme, которая возвращает первые n элементов в списке. Я хочу сделать это без циклов, просто с помощью этой базовой структуры ниже.

То, что я пробовал, это: 

(define n-first
(lambda (lst n)
(if (or(empty? lst) (= n 0))
    (list)
    (append (car lst) (n-first (cdr lst) (- n 1))))))

Но я получаю сообщение об ошибке: 

append: contract violation
expected: list?
given: 'in

Я попытался отладить его, и похоже, что хвост рекурсии разбивает его, то есть сразу после возврата пустого списка программа вылетает.

При замене оператора "append" на "list" я получаю:

Ввод: (n-first '(кот в шляпе) 3)

Выход: 

'(the (cat (in ())))

Но я хочу получить добавленный список.

Ответы [ 2 ]

0 голосов
/ 15 марта 2019

попробуйте так 

(define first-n
  (lambda (l)
    (lambda (n)
      ((lambda (s)
         (s s l n (lambda (x) x)))
       (lambda (s l n k)
         (if (or (zero? n)
                 (null? l))
             (k '())
             (s s (cdr l) (- n 1)
                (lambda (rest)
                  (k (cons (car l) rest))))))))))

(display ((first-n '(a b c d e f)) 4))
(display ((first-n '(a b)) 4))

В схеме вы должны мысленно вычислять типы каждого выражения, так как оно не включает проверку типов / вывод типов.

0 голосов
/ 12 марта 2019

Список, который выглядит как (1 2 3) Я построил как (1 . (2 . (3 . ()))) или, если вы более знакомы с cons (cons 1 (cons 2 (cons 3 '()))). Таким образом (list 1 2 3)) делает именно это под капотом. Это важная информация для того, чтобы уметь работать с ними. Обратите внимание, что первый cons не может быть применен до завершения (cons 2 (cons 3 '())), поэтому список всегда создается от конца к началу. Также список повторяется от начала до конца.

Итак, вы хотите: 

(define lst '(1 2 3 4 5))

(n-first lst 0) ; == '()
(n-first lst 1) ; == (cons (car lst) (n-first (- 1 1) (cdr lst)))
(n-first lst 2) ; == (cons (car lst) (n-first (- 2 1) (cdr lst)))

append работает так: 

(define (append lst1 lst2)
  (if (null? lst1)
      lst2
      (cons (car lst1)
            (append (cdr lst1) lst2))))

append - это O (n) сложность времени, поэтому если вы используете эту каждую итерацию из n частей списка, вы получите O (n ^ 2). Для небольших списков вы этого не заметите, но даже списки среднего размера из ста тысяч элементов, которые вы заметите, append использует примерно в 50 раз больше времени, чем один cons, а для больших списков вы не хотите дождитесь результата, так как он растет в геометрической прогрессии.

...