Вставка значения в заказанное дерево в Haskell
В основном я определил Древовидный тип данных, который определяется следующим образом:
data Tree a = Empty
| Leaf a
| Node (Tree a) a (Tree a)
deriving (Eq, Ord, Show)
Теперь я должен создать функцию для вставки значения в заказанное дерево (это не должно сортировать дерево, просто добавить значение). Это - то, что я придумал до сих пор:
insert :: a -> Tree a -> Tree a
insert x Empty = Leaf x
insert x (Leaf m) | m < x = Node (Leaf x) m Empty
| otherwise = Node Empty m (Leaf x)
insert x (Node l m r) | x > m = Node (Leaf l) m (insert x r)
| otherwise = Node (insert x l) m (Leaf r)
Однако, когда я выполняю это, я получаю следующее сообщение об ошибке:
Не мог соответствовать ожидаемому типу (твердая переменная) против выведенного типа 'Дерево' связанного подписью типа для 'вставки' в Основном hs:11:10 В первом аргументе 'Листа', а именно, 'l' В первом аргументе 'Узла', а именно,' (Лист l)' В выражении: Узел (Лист l) m (вставляют x r),
Я предполагаю, что это - что-то, чтобы сделать с типами, но я не вижу, куда я поместил любые типы, которые не должны быть там.
3 ответа
Примерный перевод с type-checker-ese на английский:
Не удалось сопоставить ожидаемый тип 'a' ( жесткая переменная)
Это означает, что ожидался произвольный тип a , который также используется где-то еще (отсюда «жесткий»), поэтому он не может просто принимать какой-либо старый тип.
против предполагаемого типа 'Tree a'
Это означает, что вместо этого было найдено Tree , содержащее элементы ожидаемого жесткого полиморфного типа. Это явно не имеет смысла, поэтому он жалуется.
'a' привязано к сигнатуре типа для 'insert' в Main.hs: 11: 10
Это просто говорит о том, что тип ограничен, потому что вы указали его в этой сигнатуре типа.
В первом аргументе 'Leaf', а именно 'l' В первом аргументе 'Node', а именно '(Leaf l)' В выражении: Node (Leaf l) m (insert xr )
Это просто говорит вам, на какой конкретный термин он жалуется, с некоторым контекстом.
Итак, чтобы разобраться: переменная l представляет собой дерево a , используемое в контексте, которому требуется только a . В этом случае l , очевидно, имеет правильный тип, поэтому ошибка заключается в том, как он используется.Почему средство проверки типов искало тип a ? Потому что вы применили к нему конструктор данных Tree . Но подождите, l уже является деревом a ! et voila , чешуя падает с наших глаз, и истина видна.
... все это было просто длинным способом объяснить, почему быстрый ответ Эдварда Кметта верен, и какие рассуждения можно использовать, чтобы прийти к такому ответу.
Ваша проблема в том, что
insert x (Node l m r) | x > m = Node (Leaf l) m (insert x r)
| otherwise = Node (insert x l) m (Leaf r)
, вероятно, должно быть
insert x (Node l m r) | x > m = Node l m (insert x r)
| otherwise = Node (insert x l) m r
, потому что l и r уже являются деревьями .
Джон говорит о том, как система Windows (и другие системы на основе окон - X Window , оригинальная Mac OS....) реализуют асинхронные пользовательские интерфейсы с использованием событий через систему сообщений.
За кадром для каждого приложения есть система обмена сообщениями, где каждое окно может отправлять события в другие окна или прослушиватели событий - это реализуется путем добавления сообщения в очередь сообщений. Существует основной цикл, который всегда просматривает эту очередь сообщений и затем отправляет сообщения (или события) слушателям.
В статье Википедии Цикл сообщений в Microsoft Windows показан пример кода базовой программы Windows - и, как вы можете видеть на самом базовом уровне, программа Windows - это просто «насос сообщений».
Итак, собрать все вместе. Причина, по которой программа Windows, разработанная для поддержки пользовательского интерфейса, не может работать как служба, заключается в том, что для включения поддержки пользовательского интерфейса необходимо постоянно запускать цикл сообщений. Если реализовать ее как службу, как описано выше, она не сможет обрабатывать внутреннюю асинхронную обработку событий.
-121--764496- Если хеширование с помощью GenerateSalt (31) возвращается почти мгновенно, это ошибка. Вы должны сообщить, что восходящий (у меня есть, для jBCrypt).: -)
По умолчанию log-rounds равно 10. Это означает, что (если я правильно помню) используется 1024 раунда. При каждом приращении скруглений количество скруглений удваивается.
В 30 раундах вы делаете 1073741824 раундов. Это по праву занимает много времени. При 31 раунде необходимо выполнить 2147483648 раундов, но я подозреваю, что конкретная реализация, которую вы используете вместо переполнения.: - (
-121--1617800- l является первым параметром Node и поэтому имеет тип Tree a (все левое поддерево). Лист , с другой стороны, просто принимает одно значение в качестве параметра, а не целое дерево. Поэтому Leaf l дает ошибку типа, поскольку пытается сделать Leaf из целого дерева. Вероятно, вы просто хотели l вместо Leaf l в этом месте.
Кроме того, какова разница между Leaf x и Node Empty x Empty ? Вы уверены, что вам нужны оба конструктора?