Haskell: «Карта (a, b) c» по сравнению с «Карта a (Карта 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, и это вполне может быть лучшим решением в этом случае; но там, где есть неизвестное/переменное количество свойств (например, в зависимости от типа человека), это также столкнется с трудностями.

Итак, я думаю, это также зависит от того, нужна ли вам такая функция запроса:

data QueryResult = PersonUnknown | PropertyUnknownForPerson | Value String
query :: Person -> Property -> Map (Person, Property) String -> QueryResult

Это сложно (если вообще возможно) написать в версии с карри, но легко в версии без карри.