¿Existe una instancia de mónada para Data.Map/Data.IntMap?

Question

Tengo un algoritmo que opera en un IntMap que creo que sería mejor expresar de forma imperativa. Es decir, me gustaría decir cosas como:

• Busque el valor X en el mapa.
• Si coincide con un criterio, elimine este valor del mapa.
• Haz un bucle hasta que no existan más valores en el mapa.

Esto sería bastante trivial para expresar como una recursión de dos líneas, pero el algoritmo real es un poco más compleja, que implica varias operaciones de búsqueda y supresiones, así que me gustaría ser capaz de expresarlo en notación do .

¿Existe un "Estado" estándar -como mónada donde el estado está representado por Data.Map o Data.IntMap, donde puedo hacer algo como:

do 
    insert 5 20 
    (ma, mv) <- lookup 4 
    case mv of 
    Just v -> delete (fromJust ma) 
    Nothing -> return() 

Honestamente no estoy seguro de cómo expresar mejor esto. debido a lookup parece beneficiarse de algún tipo de pila MaybeT IntMap m o algo así.

lo hice hacer un poco de trabajo tratando de definir mi propia mónada estado basado en Data.IntMap, incluso llegó tan lejos como hacer insert y delete trabajo, pero tiene un poco atascado con la forma de hacer frente a lookup. En general, creo que esto probablemente sea algo que alguien ya ha resuelto, pero no puedo encontrarlo en Hackage.

Answer 1

¿Hay alguna razón en particular por la que desee evitar el uso de transformadores de mónada? si se obtiene el paquete de MaybeT Hackage se puede lograr lo que quiere de esta manera:

import Control.Monad 
import Control.Monad.Maybe 
import Control.Monad.State 
import qualified Data.Map as Map 

type MapM k v a = MaybeT (State (Map.Map k v)) a 

lookupM k = MaybeT $ Map.lookup k `liftM` get 
insertM k = modify . Map.insert k 
deleteM k = modify $ Map.delete k 

runMap m = (flip execState) m . runMaybeT 

foo = runMap Map.empty $ do 
    insertM 5 20 
    v <- lookupM 4 
    deleteM v 

Cuando lookupM falla el resto de la computación falla. Puede ingresar y escapar de estas mónadas en cualquier momento para poder ocultarlas bajo una interfaz de función pura, es solo la mónada IO de la que no se supone que salga, excepto en la principal (y el uso de funciones inseguras).

Todo lo que necesita recordar es cualquier acción de estado que devuelva Quizás el tipo solo se levante en el constructor MaybeT. Si desea hacer IO cambie State to StateT.