Как работает порядок объектов? - PullRequest
Новая
       7

Как работает порядок объектов?

1 голос
/ 04 мая 2011

сначала я должен сказать, что я никогда не видел ни одного кода на Haskell. Теперь у меня есть алгоритм, который я должен реализовать на другом языке. К сожалению, этот алгоритм основан на некоторых характеристиках и возможностях Haskell, поэтому я хотел бы попросить вас о помощи, как это работает, чтобы правильно его реализовать?

Есть код: 

data Utree = Tree[Utree]

instance Eq Utree where
    Tree(p) == Tree(q) = p == q
instance Ord Utree where
    Tree(p) <= Tree(q) = p <= q

norm(Tree(p)) = Tree(sort(map norm p))


iso p q = (norm p) == (norm q)

sort[] = []
sort(a:x) = ins a (sort x)

ins a [] = [a]
ins a (b:x)
   | a <= b = a:b:x
   | a > b = b:(ins a x)

Теперь, как я это понимаю. UTree - это какая-то древовидная структура, которая использует список для хранения поддеревьев. (Респ. Должно быть) Определенная сортировка - это вставка сортировки, это понятно.

Но здесь используется порядок Eq a Ord, но я абсолютно не знаю, как это работает. Есть некоторое определение TreeA

Можете ли вы объяснить это, пожалуйста?

Ответы [ 2 ]

7 голосов
/ 04 мая 2011

Ваш код дает определения того, что значит сравнивать два дерева.Например, для равенства: 

instance Eq Utree where
    Tree(p) == Tree(q) = p == q

Это говорит о том, что равенство двух деревьев совпадает с равенством их списков поддеревьев.Таким образом, в этом коде p и q являются списками .Равенство в списках заранее задано в Haskell, так как два дерева равны, если они имеют одинаковую длину, а элементы попарно равны.Поскольку элементы p и q являются деревьями , это рекурсивно вызывает сравнение равенства на деревьях.

Интуитивно это означает, что два дерева равны, если они имеют одинаковую форму.

Аналогично, порядок двух деревьев определяется в порядке упорядочения списка поддеревьев. 

instance Ord Utree where
    Tree(p) <= Tree(q) = p <= q

Порядок в списках в Haskell предопределен как лексикографическое упорядочение на основена порядок элементов, т.е. вы сравниваете два первых элемента.Опять же, это вызывает сравнение на деревьях рекурсивно.Если они отличаются, используйте это как ответ, в противном случае сравните следующие два элемента и т. Д. Если у вас заканчивается один список перед другим, самый короткий список стоит первым в порядке.

В этом случае это означает, что упорядочение этих деревьев примерно такое, как мы смотрим на крайнюю левую точку, в которой они различаются.На этом этапе «наименьшее» дерево стоит первым в порядке.

Например, предположим, у нас есть два дерева: 

*Main> let a = Tree [Tree [], Tree [Tree []]]
*Main> let b = Tree [Tree [Tree []], Tree []] 
*Main> compare a b
LT

Деревья в этом примере выглядят так: 

         *               *
a =     / \        b =  / \
       x   *           x   *
          /           /
         *           *

То есть a меньше b, потому что когда мы смотрим на крайнюю левую точку, где они различаются, x, a имеет пустое поддерево, тогда как b имеет единственный узелесть.

1 голос
/ 04 мая 2011

UTrees сравниваются путем сравнения их списков элементов, это то, что видно из определений экземпляров.Списки сравниваются обычным способом, сравнивая их элементы попарно.Например, реализация == для списков выглядит следующим образом: 

[] == [] = True
(a:as) == (b:bs) = a == b && as == bs
_ == _ = False

Вся информация, касающаяся классов Eq и Ord, может быть найдена в соответствующем отчете Haskell, который, я уверен, вам пригодится.

Функция сравнения для списков может выглядеть так (на самом деле, она немного отличается, но здесь это не имеет значения): 

[] > _ = False     -- the empty list is not greater than any other list
(a:as) > [] = True -- nonempty is greater than empty
(a:as) > (b:bs)
   | a < b = False
   | a > b = True
   | otherwise = as > bs
...