#haskell #deriving
#haskell #вывод
Вопрос:
Предположим, я определяю простой тип следующим образом:
data Object = House | Table | Book
Чтобы иметь возможность использовать Object s в качестве ключей для карты, тип должен быть производным от Eq и Ord :
data Object = House | Table | Book deriving (Eq, Ord)
В чем причина этого ограничения? Почему ключи карты должны быть упорядочиваемыми?
Комментарии:
1. Я полагаю, это потому, что реализация использует сбалансированные двоичные деревья.
Ответ №1:
Data.Map предлагает O (log N) сложность для большинства операций (вставка, поиск, удаление, …). Он может это сделать, поскольку внутренне он использует сбалансированное дерево поиска. Это, в свою очередь, требует отношения упорядочения ключей, отсюда и Ord ограничение. Eq является суперклассом Ord , поэтому это также должно быть предоставлено.
С помощью only Eq мы не можем быть столь же эффективными, скажем, при поиске, поскольку лучшее, что мы можем сделать в таком случае, — это выполнить линейный поиск, который равен O (N).
Без Eq мы вообще не можем выполнить поиск, поскольку у нас нет возможности сравнить уже вставленные ключи с ключом для поиска.