Рассматривая карты как представления конечных функций, отображение двух или более переменных может быть задано либо в кардианной, либо в неопознанной форме; то есть типы Map (a,b) c и Map a (Map b c) являются изоморфными или близкими к ним.
Какие существуют практические соображения - эффективность и т.д. - для выбора между двумя представлениями?
Экземпляр кортежей Ord использует лексикографический порядок, поэтому Map (a, b) c сначала будет сортироваться по a, поэтому общий порядок будет таким же. Что касается практических соображений:
Поскольку Data.Map представляет собой двоичное дерево поиска, разделяющее ключ, сопоставимо с поиском, поэтому получение подкапа для данного a в неопознанной форме не будет значительно дороже, чем в карри форма.
Карридная форма может давать менее сбалансированное дерево в целом, по очевидной причине наличия нескольких деревьев вместо одного.
Для сохранения вложенных карт в картонной форме будет немного дополнительных накладных расходов.
Вложенные карты карри-формы, представляющие "частичные приложения", могут быть разделены, если некоторые значения a дают одинаковый результат.
Аналогичным образом, "частичное приложение" карри-формы дает вам существующую внутреннюю карту, в то время как необработанная форма должна создавать новую карту.
Таким образом, непонятная форма явно лучше вообще, но кардинальная форма может быть лучше, если вы часто будете часто выполнять "частичное приложение" и выиграете от обмена значениями Map b c.
Обратите внимание, что для обеспечения фактического выигрыша от этого потенциального совместного использования вам потребуется некоторое внимание. вам нужно будет явно определять любые общие внутренние карты и повторно использовать одно значение при построении полной карты.
Изменить: Тихон Джелвис отмечает в комментариях, что накладные расходы на память конструкторов кортежей, которые я не думал об учетной записи, вовсе не ничтожны. Конечно, есть некоторые накладные расходы на карри, но эти накладные расходы пропорциональны количеству различных значений a. С другой стороны, служебные данные конструктора кортежа в неопознанной форме пропорциональны общему количеству ключей.
Так что, если в среднем для любого заданного значения a есть три или более различных ключа, использующих его, вы, вероятно, сохраните память, используя версию в карри. Разумеется, опасения относительно несбалансированных деревьев все же применяются. Чем больше я думаю об этом, тем больше я подозреваю, что карри-форма недвусмысленно лучше, за исключением, возможно, если ваши ключи очень разрежены и неравномерно распределены.
Обратите внимание, что, поскольку арность определений имеет значение для GHC, такая же осторожность требуется при определении функций, если вы хотите, чтобы подвыражения были разделены; это одна из причин, по которым вы иногда видите функции, определенные в таком стиле:
foo x = go
where z = expensiveComputation x
go y = doStuff y z
Кортежи ленивы в обоих элементах, поэтому версия кортежа вводит немного дополнительной лености. Является ли это хорошим или плохим, сильно зависит от вашего использования. (В частности, сравнения могут заставлять элементы кортежа, но только если есть много повторяющихся значений a.)
Помимо этого, я думаю, это будет зависеть от того, сколько у вас дубликатов. Если a почти всегда различается всякий раз, когда b, у вас будет много маленьких деревьев, поэтому версия кортежа может быть лучше. С другой стороны, если противоположность верна, версия без кортежа может сэкономить вам немного времени (не постоянно перечитывая a после того, как вы найдете соответствующее поддерево, и вы ищете b).
Мне напоминают о попытках и как они хранят общие префиксы один раз. Версия, отличная от кортежа, кажется немного похожей. Trie может быть более эффективным, чем BST, если имеется множество общих префиксов и менее эффективен, если нет.
Но нижняя строка: сравните ее!!; -)
Помимо аспектов эффективности, также существует прагматическая сторона этого вопроса: что вы хотите сделать с этой структурой?
Вы, например, хотите иметь возможность хранить пустую карту для заданного значения типа a? Если это так, то необоснованная версия может быть более практичной!
Вот простой пример: скажем, мы хотим сохранить String -значные свойства людей - скажем, значение некоторых полей на странице профиля пользователя stackoverflow.
type Person = String
type Property = String
uncurriedMap :: Map Person (Map Property String)
uncurriedMap = fromList [
("yatima2975", fromList [("location","Utrecht"),("age","37")]),
("PLL", fromList []) ]
curriedMap :: Map (Person,Property) String
curriedMap = fromList [
(("yatima2975","location"), "Utrecht"),
(("yatima2975","age"), "37") ]
В версии с кариесом нет хорошего способа записать тот факт, что пользователь "PLL" известен системе, но не заполнил никакой информации. Пара человек/свойство ("PLL",undefined) будет вызывать сбои во время выполнения, поскольку Map является строгим в ключах.
Вы можете изменить тип curriedMap на Map (Person,Property) (Maybe String) и сохранить Nothing там, и это может быть наилучшим решением в этом случае; но там, где существует неизвестное/изменяющееся количество свойств (например, в зависимости от вида Person), которое также столкнется с трудностями.
Итак, я думаю, это также зависит от того, нужна ли вам такая функция запроса:
data QueryResult = PersonUnknown | PropertyUnknownForPerson | Value String
query :: Person -> Property -> Map (Person, Property) String -> QueryResult
Трудно писать (если не невозможно) в версии с карри, но легко в неопубликованной версии.