Haskell, Как создать упорядоченные данные Set a = Set [a]
Мне нужно создать "набор данных" Haskell
data Set a = Set [a]
Упражнение давайте реализуем простой тип данных Set. Набор — это список уникальные элементы. Набор всегда держится в порядке.
Implement the functions below. You might need to add class
constraints to the functions' types.
Examples:
member 'a' (Set ['a','b','c']) ==> True
add 2 (add 3 (add 1 emptySet)) ==> Set [1,2,3]
add 1 (add 1 emptySet) ==> Set [1]
data Set a = Set [a]
deriving (Show,Eq)
до сих пор я определил:
-- emptySet is a set with no elements
emptySet :: Set a
emptySet = Set []
-- member tests if an element is in a set
member :: Eq a => a -> Set a -> Bool
member _ (Set[]) = False
member a (Set (x:xs))
| (a == x) = True
| otherwise = member a (Set xs)
но я изо всех сил пытаюсь определить метод «добавить», это не удается в тесте заказа
-- add a member to a set
add :: Ord a => a -> Set a -> Set a
add a (Set[]) = Set[a]
add a (Set (x:xs))
| (a > x) && (not ( member a (Set (x:xs)) )) = add a (Set xs)
| (a <= x) && (not ( member a (Set (x:xs)) )) = Set ( a :(x:xs) )
| (not ( member a (Set (x:xs)) )) = Set ((x:xs) ++ [a])
| otherwise = Set (x:xs)
Тесты не пройдены:
*** Failed! Falsified (after 6 tests):
add (Just 0) (Set [Nothing,Just (-5),Just 1,Just 3])
Expected: Set [Nothing,Just (-5),Just 0,Just 1,Just 3]
Was: Set [Just 0,Just 1,Just 3]
поэтому мой вопрос в том, как реализовать метод Add, но сохранить правильный порядок. или проще использовать вспомогательную функцию для упорядочения элементов после вставки.
Ответы 3
Вам не нужен тест member на каждой итерации вашей функции add, потому что вы знаете, что Set отсортирован. Просто пройдитесь по списку, на каждом этапе сравнивая добавляемый элемент с передней частью набора. Если добавляемый элемент равен наименьшему элементу, то можно остановиться: элемент уже присутствует. Если он меньше наименьшего элемента, то вы нашли его точку вставки: если он меньше наименьшего элемента, он должен быть меньше всех элементов и, следовательно, должен быть добавлен. Наконец, если добавляемый элемент больше самого маленького элемента, просто продолжайте, пока не найдете его точку вставки.
@cealex Вы не можете : два Set, как в Set ([x] : .... Вы можете только : два списка. Итак, преобразуйте набор add a (Set xs) в список (как?), добавьте x, а затем преобразуйте окончательный список обратно в набор (как?).
@chi Не два списка, конечно. Скорее, один список и один элемент для добавления на передний план.
@amalloy Верно! Я упростил, так как OP начинался с двух наборов, первый из которых был синглтоном.
Ты пишешь
add a (Set (x:xs))
| (a > x) && (not ( member a (Set (x:xs)) )) = add a (Set xs)
-- ^^^^^^^^^^^^^^
....
add a (Set xs) это результат.
Где x? Разве он не должен присутствовать и в результате?
решение, которое я смог найти, основываясь на советах @amalloy и @chi, было
toLista :: Set a -> [a]
-- toLista (Set[]) = []
-- toLista (Set (x:xs)) = [x] ++ toLista ( Set (xs))
toLista (Set lista) = lista
add :: Ord a => a -> Set a -> Set a
add a (Set[]) = Set[a]
add a (Set (x:xs))
| (a == x) = Set (x:xs)
| (a < x) = Set ( a :(x:xs) )
| otherwise = Set ( x : toLista ( add a (Set xs) ))
Существует гораздо более простой способ реализовать ваш toLista, не сопоставляя с шаблоном содержимое набора: toLista (set xs) = xs
Вы уже узнали о выражениях «как шаблоны» или case? Второй случай можно записать add a Set (xxs@(x:xs)) | a == x = Set xxs | a < x = Set (a : xxs) | otherwise = .... Я также предлагаю написать «списочную» версию, addList :: Ord a => a -> [a] -> [a], а затем обернуть ее: add a (Set l) = Set (addList a l). Это избавляет вас от необходимости возиться с применением и удалением конструктора Set в вашей рекурсии.
Итак, следуя вашему ходу мыслей, я добавил :: Ord a => a -> Set a -> Set add a (Set[]) = Set[a] add a (Set (x:xs)) | (a == x) = Установить (x:xs) | (a < x) = Set ( a :(x:xs)) | в противном случае = Set([x]): (добавить (Set xs)) но показывает ошибку: Не удалось сопоставить ожидаемый тип
[Set a]' with actual typeSet a' | иначе = Set([x]): (добавить (Set xs)) ^^^^^^^^^^^^^^^