Блог

Главная - Вопросы по программированию - Карта Haskell: ошибки преобразования ключа и перехвата

Карта Haskell: ошибки преобразования ключа и перехвата

#dictionary #haskell #error-handling

#словарь #haskell #обработка ошибок

Вопрос:

Я изо всех сил пытаюсь найти решение (отличное от использования Data.Map.fromList и toList ) для следующей проблемы:

Преобразуйте ключ с помощью функции, которая возвращает Either String k где, как обычно, ошибки выражаются как Left , и все преобразование завершается неудачей, если одно преобразование ключа завершается неудачей.

 import Data.Map.Strict

mapEitherKey :: (k -> Either String k') -> Map k a -> Either String (Map k' a)

Для правой части v Map k v это легко сделать с помощью mapM , потому что
Map k является экземпляром Monad .

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

Будем признательны за любую информацию.

Комментарии:

1. Это не может быть бифунктором из-за Ord ограничения на ключи. Кроме того, применение произвольной функции к ключам может нарушить инвариант дерева (функция может быть немонотонной или неинъекционной), поэтому нужно было бы построить новое дерево с нуля, эффективно используя что-то вроде fromList/toList .

2. Библиотека действительно предлагает mapKeys :: Ord k2 => (k1 -> k2) -> Map k1 a -> Map k2 a некоторую функциональность для ключей. Это O (n * log n) вместо O (n), потому что дерево необходимо перестроить. Если у вас есть монотонная функция, вы можете использовать mapKeysMonotonic :: (k1 -> k2) -> Map k1 a -> Map k2 a , которая выполняется в O (n) — будьте осторожны, чтобы не нарушить инвариант.

Ответ №1:

Я хотел бы поддержать то, что сказал @chi; если вы не знаете, что порядок сохранен, вам придется каждый раз заново вставлять ключ. Это означает, что toList а затем повторная вставка с fromList должна быть лучшей, которую вы можете получить асимптотически.

Однако, поскольку вы просили способ сделать это без этих функций, я хотел бы предложить использовать foldMapWithKey .

 import Data.Monoid (Ap(..))
import qualified Data.Map as M


mapEitherKey :: (Ord k, Ord k') => (k -> Either String k') -> Map k a -> Either String (Map k' a)
mapEitherKey f = getAp . M.foldMapWithKey (k v -> Ap (flip M.singleton v <$> f k))

Идея этого состоит в том, чтобы перенести реконструкцию карты с помощью ключа k' (что мы делаем, объединяя кучу одиночных элементов) в Either String аппликатив, который закорачивается, если он сталкивается с Left .

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

Обратите внимание, что вам нужны Ord ограничения на k и k' .

Пример использования:

 Prelude> f k = if k > 10 then Left "bad number" else Right $ show k
Prelude> mapEitherKey f (M.fromList [(0,0),(1,1),(2,2)])
Right (fromList [("0",0),("1",1),("2",2)])
Prelude> mapEitherKey f (M.fromList [(0,0),(1,1),(2,2),(11,11)])
Left "bad number"