Konstruieren von effizienten Monad-Instanzen auf `Set` (und anderen Containern mit Constraints) unter Verwendung der Fortsetzungs-Monade

Question

Set, ähnlich wie [] hat eine perfekt definierte monadische Operationen. Das Problem ist, dass sie erfordern, dass die Werte Ord Constraint erfüllen, und daher ist es unmöglich, return und ohne Einschränkungen zu definieren. Das gleiche Problem gilt für viele andere Datenstrukturen, die eine Art von Einschränkungen für mögliche Werte erfordern.

Der Standardtrick (vorgeschlagen zu mir in haskell-cafe post) ist, Set in die continuation monad zu wickeln. ContT ist es egal, ob der zugrundeliegende Typ funktor irgendwelche Einschränkungen hat. Die Zwänge geworden nur benötigt, wenn Verpackung/Abwickeln Set s in/aus Fortsetzungen:

import Control.Monad.Cont 
import Data.Foldable (foldrM) 
import Data.Set 

setReturn :: a -> Set a 
setReturn = singleton 

setBind :: (Ord b) => Set a -> (a -> Set b) -> Set b 
setBind set f = foldl' (\s -> union s . f) empty set 

type SetM r a = ContT r Set a 

fromSet :: (Ord r) => Set a -> SetM r a 
fromSet = ContT . setBind 

toSet :: SetM r r -> Set r 
toSet c = runContT c setReturn 

Dieser Bedarf arbeitet. Zum Beispiel können wir eine nicht-deterministischen Funktion, der entweder erhöht dessen Argument von 1 oder lässt sie intakt simulieren:

step :: (Ord r) => Int -> SetM r Int 
step i = fromSet $ fromList [i, i + 1] 

-- repeated application of step: 
stepN :: Int -> Int -> Set Int 
stepN times start = toSet $ foldrM ($) start (replicate times step) 

Tatsächlich stepN 5 0fromList [0,1,2,3,4,5] ergibt. Wenn wir [] Monade stattdessen verwendet, würden wir

[0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5] 

stattdessen bekommen.

---

Das Problem ist Effizienz. Wenn wir stepN 20 0 aufrufen, dauert die Ausgabe ein paar Sekunden und stepN 30 0 endet nicht innerhalb einer angemessenen Zeit. Es stellt sich heraus, dass alle Set.union Operationen am Ende ausgeführt werden, anstatt sie nach jeder monadischen Berechnung durchzuführen. Das Ergebnis ist, dass viele Set s nur am Ende konstruiert und union ed sind, was für die meisten Aufgaben nicht akzeptabel ist.

Gibt es einen Weg um diese Konstruktion effizient zu machen? Ich habe es versucht, aber ohne Erfolg.

(ich auch vermuten, dass es könnte einige Arten von theoretischen Grenzen liegen folgende von Curry-Howard Isomorphismus und Glivenko's theorem. Glivenko Theorem besagt, dass für jede Aussage Tautologie φ die Formel ¬¬φ kann in intuitionismus nachgewiesen werden Ich vermute jedoch, dass die Länge des Beweises (in normaler Form) exponentiell lang sein kann. Also könnte es Fälle geben, in denen eine Berechnung in die Fortsetzungsmonade exponentiell länger gemacht wird?)

Answer 1

Monaden eine bestimmte Art und Weise der Strukturierung und Sequenzierung Berechnungen vermieden werden. Die Bindung einer Monade kann deine Berechnung nicht magisch restrukturieren, um so effizienter zu geschehen. Es gibt zwei Probleme mit der Art, wie Sie Ihre Berechnung strukturieren.

1. Wenn stepN 20 0 Auswertung, wird das Ergebnis der step 0 20 mal berechnet werden. Dies liegt daran, dass jeder Schritt der Berechnung 0 als eine Alternative erzeugt, die dann dem nächsten Schritt zugeführt wird, der auch 0 als Alternative erzeugt, und so weiter ...

   Vielleicht kann ein bisschen Memoisierung hier helfen.

2. Ein viel größeres Problem ist der Effekt von ContT auf die Struktur Ihrer Berechnung. Mit etwas equational Argumentation, das Ergebnis der replicate 20 step Erweiterung aus, die Definition von foldrM und so oft wie nötig zu vereinfachen, können wir sehen, dass stepN 20 0 entspricht:

   (...(return 0 >>= step) >>= step) >>= step) >>= ...) 
   

   Alle Klammern dieses Ausdrucks assoziieren zu der links. Das ist großartig, weil es bedeutet, dass die RHS jedes Auftretens von (>>=) eine elementare Berechnung ist, nämlich step, anstatt eine zusammengesetzte. Allerdings Zoomen für ContT auf die Definition von (>>=) in,

   m >>= k = ContT $ \c -> runContT m (\a -> runContT (k a) c) 
   

   wir sehen, dass, wenn eine Kette von (>>=) Zuordnen nach links Auswertung jeder bind wird eine neue Berechnung auf die aktuelle Fortsetzung c drücken. Um zu zeigen, was los ist, können wir wieder ein bisschen equational Argumentation verwenden, diese Definition erweitert out für (>>=) und die Definition für runContT und vereinfacht, wodurch man

   setReturn 0 `setBind` 
       (\x1 -> step x1 `setBind` 
        (\x2 -> step x2 `setBind` (\x3 -> ...)...) 
   

   nun für jedes Auftreten von setBind, lassen Sie uns Fragen Sie sich, was das Argument RHS ist. Für das am weitesten links liegende Vorkommen ist das RHS-Argument der gesamte Rest der Berechnung nach setReturn 0. Für das zweite Auftreten, ist es alles nach step x1 etc. Lassen Sie uns vergrößern auf die Definition von setBind:

   setBind set f = foldl' (\s -> union s . f) empty set 
   

   Hier f stellt den Rest der Berechnung alles auf der rechten Seite eines Auftretens setBind. Das bedeutet, dass wir bei jedem Schritt den Rest der Berechnung als f erfassen und f so oft anwenden, wie es Elemente in set gibt. Die Berechnungen sind nicht elementar wie zuvor, sondern eher zusammengesetzt, und diese Berechnungen werden viele Male wiederholt.

Der Kern des Problems ist, dass die ContT monadisch Transformator die Ausgangsstruktur der Berechnung ist die Umwandlung, die man als eine linke assoziative Kette von setBind ‚s bedeutet, in einer Berechnung mit einer anderen Struktur, dh ein rechte assoziative Kette.Dies ist schließlich völlig in Ordnung, weil einer der Monade Gesetze sagt, dass für jeden m, f und g wir haben

(m >>= f) >>= g = m >>= (\x -> f x >>= g) 

jedoch nicht die Monade Gesetze auferlegen, dass die Komplexität auf jeder Seite gleich bleiben von die Gleichungen jedes Gesetzes. Und in der Tat ist in diesem Fall die links assoziative Art, diese Berechnung zu strukturieren, viel effizienter. Die linke Assoziativkette von setBind wird in kürzester Zeit ausgewertet, da nur elementare Subcomputationen dupliziert werden.

Es stellt sich heraus, dass andere Lösungen Shoehorning Set in eine Monade auch unter dem gleichen Problem leiden. Insbesondere das Paket set-monad liefert ähnliche Laufzeiten. Der Grund dafür ist, dass auch links assoziative Ausdrücke in rechts assoziative Ausdrücke umgeschrieben werden.

Ich glaube, Sie mit dem Finger auf einem sehr wichtig, noch eher subtilen Problem gestellt haben mit darauf, dass Set eine Monad Schnittstelle gehorcht. Und ich denke nicht, dass es gelöst werden kann. Das Problem ist, dass die Art des bind eines monadisch

(>>=) :: m a -> (a -> m b) -> m b 

dh keine Klasse constraint entweder zugelassen sein muss, auf a oder b. Das bedeutet, dass wir Bindungen links nicht verschachteln können, ohne zuerst die Monadengesetze aufzurufen, um sie in eine rechte assoziative Kette umzuwandeln. Hier ist der Grund: (m >>= f) >>= g, der Typ der Berechnung (m >>= f) hat die Form m b. Ein Wert der Berechnung (m >>= f) ist vom Typ b. Da wir jedoch keine Klassenbeschränkung auf die Typvariable b aufhängen können, können wir nicht wissen, dass der Wert, den wir erhalten haben, eine Ord-Einschränkung erfüllt. Daher kann dieser Wert nicht als Element einer Menge verwendet werden, auf die wir zugreifen können zu berechnen union 's.

Answer 2

I don Denken Sie, dass Ihre Leistungsprobleme in diesem Fall auf die Verwendung von Cont

zurückzuführen sind

step' :: Int -> Set Int 
step' i = fromList [i,i + 1] 

foldrM' f z0 xs = Prelude.foldl f' setReturn xs z0 
    where f' k x z = f x z `setBind` k 

stepN' :: Int -> Int -> Set Int 
stepN' times start = foldrM' ($) start (replicate times step') 

wird eine ähnliche Leistung auf den Cont basierte Implementierung, sondern tritt ganz in der Set „restricted Monade“

Ich bin nicht sicher, ob ich Ihre Behauptung über Glivenko Theorem glauben an (normalisiert) der Nachweis Größe exponentiellen Anstieg führt - zumindest im Call-by-Need-Kontext. Das liegt daran, dass wir Subproofs beliebig wiederverwenden können (und unsere Logik ist zweiter Ordnung, wir brauchen nur einen einzigen Beweis von forall a. ~~(a \/ ~a)). Beweise sind keine Bäume, sie sind Graphen (Teilen).

Im Allgemeinen sind Sie wahrscheinlich Leistungskosten von Cont Einwickeln Set zu sehen, aber sie können in der Regel über

smash :: (Ord r, Ord k) => SetM r r -> SetM k r 
smash = fromSet . toSet 

Answer 3

Vor kurzem auf Haskell Cafe Oleg gave an example wie Sie die Set Monad effizient implementieren. Zitieren:

... Und doch ist die effiziente Original Set Monad möglich.

... Anbei die effiziente Original Set Monade. Ich habe es direkt geschrieben (es scheint sowieso schneller zu sein). Der Schlüssel ist, die optimierte Auswahlfunktion zu verwenden, wenn wir können.

{-# LANGUAGE GADTs, TypeSynonymInstances, FlexibleInstances #-} 

    module SetMonadOpt where 

    import qualified Data.Set as S 
    import Control.Monad 

    data SetMonad a where 
     SMOrd :: Ord a => S.Set a -> SetMonad a 
     SMAny :: [a] -> SetMonad a 

    instance Monad SetMonad where 
     return x = SMAny [x] 

     m >>= f = collect . map f $ toList m 

    toList :: SetMonad a -> [a] 
    toList (SMOrd x) = S.toList x 
    toList (SMAny x) = x 

    collect :: [SetMonad a] -> SetMonad a 
    collect [] = SMAny [] 
    collect [x] = x 
    collect ((SMOrd x):t) = case collect t of 
          SMOrd y -> SMOrd (S.union x y) 
          SMAny y -> SMOrd (S.union x (S.fromList y)) 
    collect ((SMAny x):t) = case collect t of 
          SMOrd y -> SMOrd (S.union y (S.fromList x)) 
          SMAny y -> SMAny (x ++ y) 

    runSet :: Ord a => SetMonad a -> S.Set a 
    runSet (SMOrd x) = x 
    runSet (SMAny x) = S.fromList x 

    instance MonadPlus SetMonad where 
     mzero = SMAny [] 
     mplus (SMAny x) (SMAny y) = SMAny (x ++ y) 
     mplus (SMAny x) (SMOrd y) = SMOrd (S.union y (S.fromList x)) 
     mplus (SMOrd x) (SMAny y) = SMOrd (S.union x (S.fromList y)) 
     mplus (SMOrd x) (SMOrd y) = SMOrd (S.union x y) 

    choose :: MonadPlus m => [a] -> m a 
    choose = msum . map return 


    test1 = runSet (do 
    n1 <- choose [1..5] 
    n2 <- choose [1..5] 
    let n = n1 + n2 
    guard $ n < 7 
    return n) 
    -- fromList [2,3,4,5,6] 

    -- Values to choose from might be higher-order or actions 
    test1' = runSet (do 
    n1 <- choose . map return $ [1..5] 
    n2 <- choose . map return $ [1..5] 
    n <- liftM2 (+) n1 n2 
    guard $ n < 7 
    return n) 
    -- fromList [2,3,4,5,6] 

    test2 = runSet (do 
    i <- choose [1..10] 
    j <- choose [1..10] 
    k <- choose [1..10] 
    guard $ i*i + j*j == k * k 
    return (i,j,k)) 
    -- fromList [(3,4,5),(4,3,5),(6,8,10),(8,6,10)] 

    test3 = runSet (do 
    i <- choose [1..10] 
    j <- choose [1..10] 
    k <- choose [1..10] 
    guard $ i*i + j*j == k * k 
    return k) 
    -- fromList [5,10] 

    -- Test by Petr Pudlak 

    -- First, general, unoptimal case 
    step :: (MonadPlus m) => Int -> m Int 
    step i = choose [i, i + 1] 

    -- repeated application of step on 0: 
    stepN :: Int -> S.Set Int 
    stepN = runSet . f 
    where 
    f 0 = return 0 
    f n = f (n-1) >>= step 

    -- it works, but clearly exponential 
    {- 
    *SetMonad> stepN 14 
    fromList [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14] 
    (0.09 secs, 31465384 bytes) 
    *SetMonad> stepN 15 
    fromList [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15] 
    (0.18 secs, 62421208 bytes) 
    *SetMonad> stepN 16 
    fromList [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16] 
    (0.35 secs, 124876704 bytes) 
    -} 

    -- And now the optimization 
    chooseOrd :: Ord a => [a] -> SetMonad a 
    chooseOrd x = SMOrd (S.fromList x) 

    stepOpt :: Int -> SetMonad Int 
    stepOpt i = chooseOrd [i, i + 1] 

    -- repeated application of step on 0: 
    stepNOpt :: Int -> S.Set Int 
    stepNOpt = runSet . f 
    where 
    f 0 = return 0 
    f n = f (n-1) >>= stepOpt 

    {- 
    stepNOpt 14 
    fromList [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14] 
    (0.00 secs, 515792 bytes) 
    stepNOpt 15 
    fromList [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15] 
    (0.00 secs, 515680 bytes) 
    stepNOpt 16 
    fromList [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16] 
    (0.00 secs, 515656 bytes) 

    stepNOpt 30 
    fromList [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30] 
    (0.00 secs, 1068856 bytes) 
    -} 

Answer 4

fand ich eine andere Möglichkeit, bezogen auf ConstraintKinds Erweiterung des GHC. Die Idee ist Monad neu zu definieren, so dass es ein parametrisches Einschränkung auf erlaubte Werte beinhaltet:

{-# LANGUAGE ConstraintKinds #-} 
{-# LANGUAGE TypeFamilies #-} 
{-# LANGUAGE RebindableSyntax #-} 

import qualified Data.Foldable as F 
import qualified Data.Set as S 
import Prelude hiding (Monad(..), Functor(..)) 

class CFunctor m where 
    -- Each instance defines a constraint it valust must satisfy: 
    type Constraint m a 
    -- The default is no constraints. 
    type Constraint m a =() 
    fmap :: (Constraint m a, Constraint m b) => (a -> b) -> (m a -> m b) 
class CFunctor m => CMonad (m :: * -> *) where 
    return :: (Constraint m a) => a -> m a 
    (>>=) :: (Constraint m a, Constraint m b) => m a -> (a -> m b) -> m b 
    fail :: String -> m a 
    fail = error 

-- [] instance 
instance CFunctor [] where 
    fmap = map 
instance CMonad [] where 
    return = (: []) 
    (>>=) = flip concatMap 

-- Set instance 
instance CFunctor S.Set where 
    -- Sets need Ord. 
    type Constraint S.Set a = Ord a 
    fmap = S.map 
instance CMonad S.Set where 
    return = S.singleton 
    (>>=) = flip F.foldMap 

-- Example: 

-- prints fromList [3,4,5] 
main = print $ do 
    x <- S.fromList [1,2] 
    y <- S.fromList [2,3] 
    return $ x + y 

(Das Problem mit diesem Ansatz in dem Fall ist, die monadische Werte Funktionen sind, wie m (a -> b), weil sie nicht erfüllen kann Einschränkungen wie Ord (a -> b). So man nicht combinators verwenden kann wie <*> (oder ap) für diesen Set Monade eingeschränkt.)