Haskell - декартова функция для множества, реализованная в виде двоичного дерева - PullRequest
Новая
       18

Haskell - декартова функция для множества, реализованная в виде двоичного дерева

4 голосов
/ 08 января 2020

Я реализовал набор в виде двоичного дерева в Haskell следующим образом: 

data Set a = Node | Tree a (Set a) (Set a)

, и я пытаюсь определить функцию для поиска декартового произведения двух наборов, например 

cartesian :: Set a -> Set b -> Set (a, b)
cartesian as bs = fromList [(a,b) | a <- (toList as), b <- (toList bs)]

Кажется, я не вижу, в чем ошибка с этим кодом, любая помощь / исправления будут оценены.

Сообщение об ошибке: 

error:
    • No instance for (Ord a) arising from a use of ‘fromList’
      Possible fix:
        add (Ord a) to the context of
          the type signature for:
            cartesian :: forall a b. Set a -> Set b -> Set (a, b)
    • In the expression:
        fromList [(a, b) | a <- (toList as), b <- (toList bs)]
      In an equation for ‘cartesian’:
          cartesian as bs
            = fromList [(a, b) | a <- (toList as), b <- (toList bs)]

Ответы [ 2 ]

1 голос
/ 09 января 2020

Ваша функция fromList предполагает, что она получает несортированный список, который может содержать дубликаты, поэтому ей необходимо ограничение Ord, чтобы выяснить, куда поместить элементы, и очистить дубликаты. Однако в этом случае вы получаете два списка, которые всегда будут отсортированы и не содержат дубликатов, и берете их декартово произведение, и результирующий список также будет отсортирован и не будет содержать дубликатов. Вместо того, чтобы использовать fromList, чтобы превратить этот новый список в набор, вы должны создать для этой цели новую функцию, аналогично fromDistinctAscList в реальном Set. Чтобы построить это, разверните foldr insert Node (я бы показал вам, как это сделать, но вы не опубликовали свою функцию insert, поэтому я не могу), и замените все сравнения на жестко закодированный результат в зависимости от того, где они были , Тогда просто используйте его вместо fromList. Это также даст выигрыш в производительности, поскольку избавляет от необходимости выполнять все избыточные сравнения.

Редактировать: ваша функция insert совсем не заботится о поддержании какого-либо баланса двоичного дерева, поэтому вызов его в отсортированном списке приведет к максимально неуравновешенному дереву. Если вас это не волнует, то вот как вы можете реализовать fromDistinctAscList: 

insertLeast :: a -> Set a -> Set a
insertLeast x Leaf = singleton x
insertLeast x (Tree a left right) = Tree a (insertLeast x left) right

fromDistinctAscList :: [a] -> Set a -> Set a
fromDistinctAscList = foldr insertLeast Leaf

Они ведут себя точно так же, как insert и fromList, когда нет дубликатов и элементы находятся в в порядке возрастания Тем не менее, это имеет печальное следствие строгого foldr, что плохо. Мы можем немного оптимизировать его следующим образом: 

fromDistinctAscList :: [a] -> Set a -> Set a
fromDistinctAscList = foldr (`Tree` Leaf) Leaf

Это все равно будет максимально неуравновешенным, но теперь в другом направлении.

И вы также можете сделать свой обычный insert Функция также ленивее: 

insert :: Ord a => a -> Set a -> Set a
insert x xs = uncurry (Tree x) $ case xs of
  Node -> (Node, Node)
  Tree a left right -> case a `compare` x of
    LT -> (insert a left, right)
    EQ -> (left, right)
    GT -> (left, insert a right)
1 голос
/ 08 января 2020

Как говорит ошибка, ваша функция fromList имеет ограничение типа Ord a: 

fromList :: <b>Ord a =></b> [a] -> Set a
fromList = foldr insert Node

Так что это означает, что для использования функции fromList a должно быть член класса Ord. Но это не входит в сигнатуру вашей cartesian функции.

Как говорит ошибка, вы можете добавить это ограничение типа к вашей cartesian функции: 

cartesian :: <b>(Ord a, Ord b) =></b> Set a -> Set b -> Set (a, b)
cartesian as bs = fromList [(a,b) | a <- toList as, b <- toList bs]

Ord a, Ord b ограничения типа возникают из-за того факта, что 2-кортеж является экземпляром Ord, учитывая, что два элемента являются экземпляром элемента Ord. Действительно, экземпляр определяется как: 

instance <b>(Ord a, Ord b) =></b> Ord (a, b) where
    -- &hellip;
...