DrRacket - студент среднего уровня с лямбдой - упорядочение списка - PullRequest
Новая
       52

DrRacket - студент среднего уровня с лямбдой - упорядочение списка

1 голос
/ 20 ноября 2011

У меня есть вопрос о назначении, который просит меня написать функцию, используя лямбду, которая использует список чисел и удаляет все, кроме первого вхождения каждого числа. Моя функция, я думаю, довольно хорошая, за исключением того, что она дает неправильный результат! Он создает список, который содержит последнее вхождение каждого числа. Он создает список с теми же значениями, что и соответствующий список, только в другом порядке. Вот мой код: 

    (define (remove-duplicates numlist)
      (foldr (lambda (a b) 
               (cond
                 [(not (member? a b)) (cons a b)]
                 [else b])) empty numlist))

Я пытался использовать foldl вместо foldr, но неудивительно, что он выдает правильный список, но в обратном порядке. Есть ли способ создания правильного списка без обращения к списку, созданному foldl с другим лямбда-выражением?

Пожалуйста, имейте в виду, это домашнее задание, поэтому, пожалуйста, никаких явных ответов.

Спасибо всем!

1 Ответ

1 голос
/ 20 ноября 2011

Подумайте, как семантически ведет себя Foldr.Он начинается с самого правого элемента списка и выполняет сгиб, двигаясь влево.Это означает, что в вашей лямбда-функции a представляет элемент непосредственно слева от сложенного таким образом списка, а b представляет результат свертывания всего справа от элемента списка a.Имея это в виду, рассмотрим: 

[(not (member? a b)) (cons a b)]
[else b]

Вы проверяете, содержит ли список b уже a.Если это так, то вы сбрасываете a, сохраняя b как есть.Это объясняет, почему ваш код сохраняет последнее (самое правое) вхождение, а не первое.Если вы хотите выполнить правильный фолд, вы должны изменить свою логику.Вам нужно как-то «очистить» b элемента-нарушителя a, который в нем содержится. 

[(not (member? a b)) (cons a b)]
[else (cons a (purge a b))]

Таким образом, вы в конечном итоге будете сохранять только крайний левый, а не самый правый вхождение каждого уникальногоэлемент.Может быть целесообразно выполнить member? и purge одновременно, так как они оба должны пройти через список;это потребует дополнительного рефакторинга.

Обратите внимание, что, поскольку функция в любом случае требует O (n 2 ) времени, это действительно не повредит сложность времени, чтобы добавить O (n) обратно к версии foldl.

...