Функции как типы в haskell

Ответ 1

Вы можете использовать шаблон "цепочка ответственности": функция вставки проверяет, соответствует ли аргумент результату Dict его собственному ключу, иначе он делегирует предыдущий Dict, который был получен как аргумент.

type Dict a b = a -> Maybe b

insertDict :: (Eq a) => a -> b -> Dict a b -> Dict a b
-- Note that the k' is the argument of the result dict function
insertDict k v dict k' = if k == k' then Just v else dict k'

emptyDict :: Dict a b
emptyDict _ = Nothing

Некоторые примеры в ghci:

Λ insertDict 'a' (1::Int) emptyDict $ 'a'
Just 1
Λ insertDict 'b' 2 (insertDict 'a' (1::Int) emptyDict) $ 'a'
Just 1
Λ insertDict 'b' 2 (insertDict 'a' (1::Int) emptyDict) $ 'x'
Nothing

Представление карт как функций хорош в первом приближении, но это представление имеет ряд недостатков:

• Сложность поиска значения линейна по количеству ключей.
• Функции довольно "непрозрачные", что означает, что вы не можете проверить или сериализовать карту, как вы могли бы сделать, если бы вы использовали тип данных .

Ответ 2

Вот один из способов, который вы можете использовать для написания таких функций самостоятельно. Сначала напишите сигнатуру типа:

insertDict :: (Eq k) => k -> v -> Dict k v -> Dict k v

Для ясности здесь использовались k и v для "ключа" и "значения". Затем начните с написания реализации как отверстия:

insertDict key value dict
  = _

Компилятор (или GHCi) должен дать вам сообщение типа "Найденное отверстие: _ :: Dict k v [...] Релевантные привязки включают в себя: dict :: Dict k v, value :: v, key :: k. Итак, вы видите, что можете просто вернуться dict, потому что тип совпадает, но это игнорирует key и value.

Поскольку вы знаете, что Dict k v - это тип функции, вы можете добиться прогресса, добавив лямбда с другим отверстием, чтобы узнать, что предлагает компилятор:

insertDict key value dict
  = \ key' -> _

Теперь мы имеем _ :: Maybe v, value :: v, key' :: k, key' :: k, dict :: Dict k v. Мы всегда могли бы возвращать Just value, но, как вы заметили, это не делает то, что мы хотим - оно представляет собой словарь, который всегда отвечает "Да, этот ключ находится в словаре, а его значение - value" для любой клавиши, которую вы задаете! (Это полезная вещь, которую можно представить, ее просто не было написано.)

Итак, это не похоже, что мы можем добиться прогресса только с этими, но подождите, у нас также есть ограничение Eq k! И только две вещи, которые мы можем сравнить: key и key', поэтому давайте разложим это на if с помощью ==:

insertDict key value dict
  = \ key' -> if key == key' then _1 else _2

Теперь компилятор сообщает _1 :: Maybe v и _2 :: Maybe v. Что мы должны возвращать в каждом из этих случаев? Давайте рассмотрим некоторые примеры того, как эта функция используется на самом деле: если вы посмотрите ключ в словаре после вставки пары ключ-значение, вы должны, естественно, найти значение:

(insertDict key value dict) key == Just value
                                   ----------

Итак, для _1 мы можем написать Just value:

insertDict key value dict
  = \ key' -> if key == key' then Just value else _2
                                  ----------

Если вы посмотрите на другой ключ, чем тот, который вы только что вставили, то самая последняя вставленная пара ключ-значение не имеет значения; он должен искать ключ дальше в словаре:

(insertDict key value dict) key' == dict key'  -- If key /= key'
                                    ---------

Итак, для _2 мы можем написать dict key':

insertDict key value dict
  = \ key' -> if key == key' then Just value else dict key'
                                                  ---------

И все было сделано!: D

Эта комбинация программирования, ориентированного на тип и эквациональное рассуждение, очень полезна при написании в Haskell, особенно для таких полиморфных функций, которые имеют ограниченное число возможных (нормальных) реализаций.