Ракетка - разделяйте четные и нечетные числа?

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

Это то, что у меня есть до сих пор:

    (define (segregate lst)
      (if (empty? lst)
          '()
          (if (even? (car a lst))
              (append (car alst) (segregate (cdr alst))))

И оттуда я застрял. Таким образом, с этим условием четные числа будут отсортированы в один список. Но мне нужны и нечетные числа. Оператор else в этом условии даст вам эти нечетные числа, но я понятия не имею, как поместить их в отдельный список.

Это первый раз, когда я действительно задаю вопрос на этом сайте, потому что моего профессора по какой-то причине нет в его кабинете.


list sublist racket
person user3451298    schedule 24.03.2014    source источник
comment
Этот код не будет работать в данный момент. car ожидает ровно один аргумент, но у вас есть (car a lst). У вас также есть (car alst) и (cdr alst), но нет переменной alst.   -  person Joshua Taylor    schedule 25.03.2014
comment
Улучшил форматирование, теперь будет понятнее?   -  person leppie    schedule 27.03.2014

Ответы (5)


arrow_upward
1
arrow_downward

Итак, ваша функция должна возвращать два списка, верно? Ваш базовый случай должен возвращать два пустых списка, а затем в ваших рекурсивных случаях вы заполняете соответствующий список в зависимости. Вот скелетный код (заполните <???>):

(define (odds-and-evens lst)
  (if (null? lst)
      (values '() '())
      (let-values (((odds evens) (odds-and-evens (cdr lst))))
        (cond ((odd? (car lst)) (values (cons <???> <???>) <???>))
              ((even? (car lst)) (values <???> (cons <???> <???>)))
              (else (values odds evens))))))
person Chris Jester-Young    schedule 24.03.2014
comment
Да, и большое спасибо. До сих пор не знал о функции let-values. - person user3451298; 25.03.2014

arrow_upward
1
arrow_downward

let-values-версия Криса пикантна, но я бы написал ее так, чтобы сделать ее рекурсивной:

(define (split left? lst)
  (let loop ((lst lst) (a '()) (b '()))
    (if (null? lst)
        ;; you don't need to use values. `cons` or `list` are sometimes preferred
        (values (reverse a) (reverse b)) 
        (let ((e (car lst)))
          (if (left? e)
              (loop (cdr <???>) (cons <???> <???>) <???>)
              (loop (cdr <???>) <???>  (cons <???> <???>)))))))

(split odd? '(1 2 3 4 ...)) 
; ==> 
; (1 3 ...)
; (2 4 ...)

Несмотря на то, что он дважды пересекает оба списка (один для разделения и один для обратного), он все равно во много раз быстрее и IMO проще следовать.

Если вас не волнует порядок, просто пропустите шаг reverse, и это будет еще быстрее.

person Sylwester    schedule 24.03.2014

arrow_upward
1
arrow_downward

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

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

(define segregate
  (lambda (A o e) ;A is the list of integers, o is the list of odds and e is for evens.
      (cond ((empty? A) (list o e))
            ((even? (car A)) (segregate (cdr A) o (append e (car A)))
            (else (segregate (cdr A) (append o (car A)) e)))))
person David Merinos    schedule 24.03.2014
comment
Спасибо. Очевидно, новички не могут ответить на свои вопросы, но я думаю, что нашел решение, создав промежуточную функцию, которая извлекает списки на основе любой логической функции, а затем я просто создаю список с двумя подсписками, которые вызывают функцию для четных и нечетных . - person user3451298; 25.03.2014
comment
Это на самом деле отличный подход. Вы увеличиваете абстракцию кода. Хорошая работа. - person David Merinos; 25.03.2014
comment
Ваш вариант крайне неэффективен. Списки на основе cons предназначены для построения справа налево с использованием cons (что является операцией O(1)). Попытка построить его слева направо с использованием append (что равно O(n) для каждого вызова) — неверный путь. Есть два способа сделать это: вы можете использовать левое сгибание, а затем обратить результат, что и является решением Сильвестра. Или вы можете использовать правый фолд, что и является моим решением. - person Chris Jester-Young; 25.03.2014
comment
Большинство курсов CS пытаются научить студентов рекурсивному алгоритму с использованием методов свертывания вправо, поэтому мое решение предпочло это. Раньше я тоже предпочитал сворачивать влево для всего, но я пришел к выводу, что сгибание вправо является правильным (хар-хар) в некоторых ситуациях, например, если вам нужно обратить результат сгиба влево. - person Chris Jester-Young; 25.03.2014
comment
Да, у хвостовой рекурсии есть преимущества, если нет других затрат. В вашем случае append добавляет огромные затраты, которые сводят на нет любое преимущество хвостовой рекурсии. Даже reverse в решении Сильвестра добавляет стоимость, но это единовременная стоимость, и нигде так плохо, как вызов append в цикле. - person Chris Jester-Young; 25.03.2014

arrow_upward
1
arrow_downward

Другой альтернативой может быть использование папки

(define (odd-even xs)
  (foldr (lambda (x b)
           (if (odd? x)
               (list (cons x (first b)) (second b))
               (list (first b) (cons x (second b))))) '(()()) xs))

racket@> (odd-even '(1 2 3 4 5 6 7))
'((1 3 5 7) (2 4 6))
person beoliver    schedule 27.03.2014

arrow_upward
1
arrow_downward

Используя встроенный partition:

(define (segregate lst)
  (let-values ([(e o) (partition even? lst)])
    (list e o)))
person caisah    schedule 27.03.2014
comment
Нет, мое решение - это partition напрямую, без let-values или преобразования в список. ;-) Кроме того, если вы хотите преобразовать в список, вероятно, более эффективно использовать call-with-values напрямую: (call-with-values (lambda () (partition even? lst)) list) - person Chris Jester-Young; 29.03.2014
comment
Извините, я только отсканировал ваш код, когда писал ответ. Ты прав. Починил это. - person caisah; 30.03.2014