Implementazione di una bind monade sensibile alle chiavi per la mappa valore-chiave

Question

Implementazione di una bind monade sensibile alle chiavi per la mappa valore-chiave

#1 da (2 voti)
#2 da (0 voti)

3

Sulla base della monade List ho deciso di definire Monad istanze per il tipo Map da Data.Map , per eseguire unioni e pieghe concatenate su Map s come elenchi, ma con l'efficiente ordinamento e fusione di Map s:

{-# LANGUAGE FlexibleInstances #-}

import qualified Data.Map as M

instance Monad (M.Map Integer) where
  return = M.singleton 0
  f >>= g = M.foldr (\a -> M.union (g a)) M.empty f

Questo compila bene, ma vorrei che g sia sensibile alla chiave di ogni valore su cui opera. Ciò consentirebbe all'output di g di avere chiavi sfalsate per un comportamento di unione più ricco. Questo è fittizio Haskell e non tipograficamente, ma sarebbe bello avere:

type PairMap (a,b) = Map a b

instance Monad PairMap where
  return :: (k,a) -> PairMap (k,a)
  return (k,a) = M.singleton k a
  (>>=) :: PairMap (k,a) -> ((k,a) -> PairMap (k',a')) -> PairMap (k',a'))
  f >>= g = M.foldrWithKey (\(k,a) -> M.union (g k a)) M.empty f

Se sostituisci PairMap (a,b) con [(a,b)] ottieni di nuovo esattamente la monade Elenco. Ma GHC non mi permette di imbrogliare e trasformare i due parametri di Map in una coppia. Il meglio che potevo gestire era qualcosa del genere: (dovevo aggiungere il vincolo Ord c a typecheck con i sindacati)

class PairMonad m where
  return2 :: a -> b -> m a b
  (>>==) :: (Ord c) => m a b -> (a -> b -> m c d) -> m c d

instance PairMonad M.Map where
  return2 = M.singleton
  f >>== g = M.foldrWithKey (\k a -> M.union (g k a)) M.empty f

Spero che tu possa vedere quanto questo sia simile al sogno di PairMap , quindi dovrebbe essere possibile farlo in modo più elegante con la magia monadica stabilita o altri concetti relativi alle monadi. Non ho bisogno che sia una monade finché riesco a ottenere quella "legatura sensibile alla chiave".

Ultimo resort

Se non c'è modo di farlo elegantemente, farò ricorso al collasso ogni Map a un elenco di valori-chiave [(a,b)] e usa la lista monad.
Si potrebbe suggerire di includere la chiave nel valore per aiutare g a calcolare sulla chiave, ma la vedo come contamina il valore con informazioni estranee.

haskell dictionary list monad

posta Herng Yi 10.06.2016 - 16:01

fonte

2 risposte

Leggi altre domande sui tag haskell dictionary list monad

Le API istanziate sono un problema in un'interfaccia C? Progettazione di una API di comando centralizzata

score 2 · Answer 1

Anche se avesse una sintassi Haskell valida, il tuo PairMap "monad" non è in realtà un monad , perché impone al tipo di risultato dell'operazione di bind di essere una coppia, il che impedisce al possibilità di utilizzarlo in contesti in cui non è richiesta una coppia (es. la funzione sequence non può accettarla, perché restituisce m t a dove m è il tipo monad e t è un tipo attraversabile, cioè il risultato non è una coppia quindi non può funzionare con esso). Non ho una prova in questo momento, ma intuitivamente parlando, questo deve essere vero per qualsiasi tentativo di trasformare Map in una monade diversa dall'uso di chiavi costanti come qualsiasi tentativo di questo tipo può funzionare solo da aggiungere ulteriori requisiti strutturali che impedirebbero alla tua "monade" di lavorare con gli utenti esistenti della classe di Monad.

In effetti stai osservando una generalizzazione di Monade che non si adatta alle restrizioni della classe esistente. È possibile che tu possa essere in grado di farlo coesistere con le generalizzazioni esistenti di Monadi; quello che salta alla mente è Control.Arrow.Arrow , che ha già una comprensione incorporata nella classe di caratteri di usarlo per operare su coppie, quindi è potenzialmente molto più adatto a quello che stai cercando di ottenere.

score 0 · Answer 2

La ricerca di Arrow s sul suggerimento di Jules mi ha portato alla classe Category , che mi ha permesso di progettare ciò che volevo di seguito:

import qualified Control.Category as C
import qualified Data.Map as M

newtype KeyValMorphism k a b = KeyVal ((k, a) -> M.Map k b)

instance (Ord k) => C.Category (KeyValMorphism k) where
  id = KeyVal (uncurry M.singleton)
  KeyVal g . KeyVal f = KeyVal (M.foldrWithKey (\k a -> M.union (g (k,a))) M.empty . f)

Sono leggermente insoddisfatto di questo perché:

Il wrapper newtype che mi impedisce di utilizzare le funzioni non elaborate (k,a) -> M.Map k b , ma per ragioni di tipo type penso che sia così il meglio che si può fare.
Il tipo k delle chiavi deve essere corretto durante i calcoli, che si adatta alla mia applicazione e sembra un ragionevole sacrificio per la semplicità di questa dichiarazione di istanza.