Есть ли способ преобразовать список в набор в схеме? - PullRequest
Новая
       12

Есть ли способ преобразовать список в набор в схеме?

3 голосов
/ 21 августа 2011

Я хочу проверить на равенство между списками, но мне действительно важно, чтобы члены были одинаковыми, а не по порядку. Есть ли простые операторы, чтобы проверить это?

Довольно тривиальный пример 

(my-equal? (a b) (b a))

Должен вернуть # т.

Очевидно, что этот конкретный пример можно легко сделать, проверив оба списка, а затем перевернув второй и проверив снова 

(or (equal? (a b) (b a)) (equal? (a b) (reverse (b a)))

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

Я использую мит-схему 9.0.1

Ответы [ 3 ]

4 голосов
/ 21 августа 2011

Если ваша реализация имеет SRFI 1 , есть lset= для достижения того, что вы хотите:

Операции над списками

3 голосов
/ 21 августа 2011

Если бы вы использовали Racket, я бы указал на эту страницу со встроенной поддержкой наборов.

Нет, это не ответ на ваш вопрос, я знаю.

1 голос
/ 25 августа 2011

Или, если вы хотите сделать это в старой школе, вы можете просто написать несколько небольших функций.

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

(define (unordered-union-set set1 set2)
    (cond ((null? set2) set1)
        (else 
            (if (in-set? (car set2) set1)
                (unordered-union-set set1 (cdr set2)) 
                (cons (car set2) (unordered-union-set (cdr set2) set1))))))

(define (in-set? item set)
    (cond ((null? set) #f)
        ((equal? item (car set)) #t)
        (else (in-set? item (cdr set)))))

(define (set-equal? set1 set2)
    (if (equal? (length set1) (length set2))
        (if (equal? (length set1) (length (unordered-union-set set1 set2)))
            #t
            #f)
    #f))

Использованиеравно установленный?на любых двух наборах.

Это работает на основе некоторой простой теории множеств.Если объединение двух наборов эквивалентной мощности приводит к набору с количеством элементов, эквивалентным количеству элементов первого или последнего набора, наборы эквивалентны.

Моя точка зрения заключается в том, чтобы сказать, что существуетдля этого нет простого оператора, но длинная сложная процедура не требуется, если вы используете трюк с объединением множеств.

Моя реализация не имеет SRFI 1, но я очень сомневаюсь, что lset = будет быстрее этой функции.

Но теперь, когда я прочитал ваши комментарии, вам нужно, чтобы они были действительны для '(1 1 2) и' (2 1).Поскольку это не наборы, этот метод не будет работать, но его не сложно реализовать.Так что, на самом деле, эта процедура эквивалентна lset =.

...