Данные Haskell.Поиск И удаление карты одновременно

#dictionary #haskell #lookup

#словарь #haskell #поиск

Вопрос:

Недавно я использовал Map тип из Data.Map внутри монады состояния, и поэтому я хотел написать функцию, которая ищет значение на карте, а также удаляет его с карты внутри монады состояния. Моя текущая реализация выглядит следующим образом:

 lookupDelete :: (Ord k) => k -> State (Map k v) (Maybe v)
lookupDelete k = do
    m <- get
    put (M.delete k m)
    return $ M.lookup k m
  

Хотя это работает, это кажется довольно неэффективным. С изменяемыми картами в императивных языках нередко встречаются delete функции, которые также возвращают значение, которое было удалено.
Я не смог найти функцию для этого, поэтому я был бы очень признателен, если кто-нибудь знает ее (или может объяснить, почему ее нет)

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

1. lookupDelete k = at k <<.= Nothing

Ответ №1:

Простая реализация заключается в alterF :

 lookupDelete :: Ord k => k -> State (Map k v) (Maybe v)
lookupDelete = state . alterF (x -> (x, Nothing))
  

Аргумент x in alterF — это Maybe значение, хранящееся в ключе, переданном lookupDelete . Эта анонимная функция возвращает (Maybe v, Maybe v) . (,) (Maybe v) это функтор, и в основном он служит «контекстом», с помощью которого мы можем сохранять любые данные, из которых мы хотим x . В этом случае мы просто сохраняем все x . Nothing В правом элементе указывает, что мы хотим удалить. После полного применения, alterF затем выдает нам (Maybe v, Map k v) , где контекст (левый элемент) — это все, что мы сохранили в анонимной функции, а правый элемент — измененная карта. Затем мы завершаем эту операцию с отслеживанием состояния в state .

alterF довольно мощный: из него можно построить множество операций, просто выбрав правильный функтор «контекста». Например, insert и delete возникают при использовании Identity , и lookup возникают при использовании Const (Maybe v) . Специализированная функция для lookupDelete не нужна, когда у нас есть alterF . Один из способов понять, почему alterF это так мощно, — распознать его тип:

 flip alterF k :: Functor f => (Maybe a -> f (Maybe a)) -> Map k a -> f (Map k a)
  

Вещи с типами в этом шаблоне

 SomeClass f => (a -> f b) -> s -> f t
  

называются «оптикой» (когда SomeClass есть Functor , они называются «линзами»), и они представляют, как «находить», «мутировать» и «сопоставлять» «поля» внутри «структур», потому что они позволяют нам сосредоточиться на части структуры, модифицировать ее (с помощью аргумента функции) и сохранять некоторую информацию через контекст (позволяя нам выбирать f ). Другие варианты использования этого шаблона см. в lens пакете. (Как alterF указано в документах, это в основном at из lens .)

Ответ №2:

Специально для «удаления и поиска» нет функции. Вместо этого вы используете более общий инструмент: updateLookupWithKey — это «поиск и обновление», где обновление может быть удалением или изменением.

 updateLookupWithKey :: Ord k => 
  (k -> a -> Maybe a) -> k -> Map k a -> (Maybe a, Map k a)

lookupDelete k = do
  (ret, m) <- gets $ updateLookupWithKey (_ _ -> Nothing) k
  put m
  pure ret