Как правильно конвертировать между списками и преобразователями монад ListT?

В настоящее время я пишу проект, в котором я активно использую ListT монадный преобразователь. При использовании простых списков реализовать недетерминизм очень просто. Однако как только мне пришлось преобразовать мой код в ListT, все стало намного сложнее 1.

В качестве простого примера: преобразование из [a] в ListT a фактически требует составления двух функций:

conv :: (Monad m) => [a] -> ListT m a
conv = ListT . return

Хотя это просто, я удивлен, что этого еще нет.

Вопросы:

  • Есть ли лучший способ справиться с недетерминизмом, когда требуется монадный преобразователь?
  • Существуют ли какие-либо методы/библиотеки для чистого преобразования между списками и ListT?

1 Точные причины довольно сложны, поэтому я не хочу подробно останавливаться на этом.


list haskell monads monad-transformers non-deterministic
person julx    schedule 09.02.2012    source источник

Ответы (2)


arrow_upward
6
arrow_downward

Я не думаю, что для этого есть какие-либо библиотеки; В конце концов, conv — невероятно простая функция, а наоборот — всего лишь runListT.

conv похож на liftMaybe, который часто требуется при использовании MaybeT:

liftMaybe :: (Monad m) => Maybe a -> MaybeT m a
liftMaybe = MaybeT . return

Я бы рекомендовал назвать его как-нибудь вроде liftList.1

Что касается лучшего преобразователя монад для недетерминизма, я рекомендую взглянуть на пакет logict, на основе преобразователя LogicT Олега, который представляет собой логическую монаду с возвратом на основе продолжения с некоторые полезные операции. В качестве бонуса, поскольку [] является экземпляром MonadLogic, эти операции также работают со списками.

1 Интересно, что мы можем определить функцию, которая обобщает шаблон conv и liftMaybe:

import Data.Foldable (Foldable)
import qualified Data.Foldable as F

choose :: (Foldable t, MonadPlus m) => t a -> m a
choose = F.foldr (\a b -> return a `mplus` b) mzero

Это, вероятно, сделает ваш код довольно запутанным, поэтому я не рекомендую его использовать :)

person ehird    schedule 09.02.2012
comment
Да, я согласен, что conv — простая функция. Я просто удивлен, что его еще нет. В модуле ListT почти нет утилит, что заставляет меня чувствовать, что я заново изобретаю велосипед. Это все. - person julx; 09.02.2012

arrow_upward
0
arrow_downward

Я только что наткнулся на этот вопрос несколько месяцев спустя, потому что мне было интересно что-то подобное. Итак, я придумал следующее:

{-# LANGUAGE MultiParamTypeClasses, FunctionalDependencies #-}

import Control.Monad.Trans.Class
import Control.Monad.Trans.Maybe
import Control.Monad.Trans.List


-- | Minimal implementation: either joinLift or joinT
class (MonadTrans t, Monad m) => MonadTransJoin t m | m -> t, t -> m where
    joinLift :: (Monad m', Monad (t m')) => m' (m a) -> t m' a
    joinLift = joinT . lift

    joinT :: (Monad m', Monad (t m')) => t m' (m a) -> t m' a
    joinT = (>>= (joinLift . return))


instance MonadTransJoin MaybeT Maybe where
    joinLift = MaybeT
    joinT = (>>= maybe mzero return)

instance MonadTransJoin ListT [] where
    joinLift = ListT
    joinT = (>>= foldr mcons mzero)
        where mcons x xs = return x `mplus` xs

Пока все хорошо — и мой метод joinT для пары ListT/[] выглядит так, как будто он как-то связан с choose Эхерда.

Но проблема в том, что на самом деле не существует единого интерфейса между преобразователем монады и монадой, поведением которой она наделяет свою базовую монаду. У нас есть MaybeT :: m (Maybe a) -> MaybeT m a и ListT :: m [a] -> ListT m a, но OTOH у нас есть StateT :: (s -> m (a, s)) -> StateT s m a. Я не знаю, есть ли способ обойти это — это определенно требует

person Luis Casillas    schedule 07.08.2012