2011-08-28 1 views
26

Ho appena reinventato un po 'di monade, ma non sono sicuro di quale. Permette di modellare le fasi di un calcolo, in modo da poter interlacciare i passaggi di numerosi calcoli per trovare quale finisce per primo.Haskell: quale monade ho appena reinventato?

{-# LANGUAGE ExistentialQuantification #-} 
module Computation where 

-- model the steps of a computation 
data Computation a = forall b. Step b (b -> Computation a) | Done a 

instance Monad Computation where 
    (Step b g) >>= f = Step b $ (>>=f) . g 
    (Done b) >>= f = Step b f 
    return = Done 

runComputation :: Computation a -> a 
runComputation (Step b g) = runComputation (g b) 
runComputation (Done a) = a 

isDone :: Computation a -> Bool 
isDone (Done _) = True 
isDone _ = False 

-- an order for a set of computations 
data Schedule a = a :> Computation (Schedule a) | Last 

toList :: Schedule a -> [a] 
toList Last = [] 
toList (a :> c) = a : (toList . runComputation) c 

-- given a set of computations, find a schedule to generate all their results 
type Strategy a = [Computation a] -> Computation (Schedule a) 

-- schedule all the completed computations, and step the rest, 
-- passing the remaining to the given function 
scheduleOrStep :: (Queue (Computation a) -> Computation (Schedule a)) -> Strategy a 
scheduleOrStep s cs = scheduleOrStep' id cs 
    where scheduleOrStep' q ((Done a):cs) = Done $ a :> scheduleOrStep' q cs 
     scheduleOrStep' q ((Step b g):cs) = scheduleOrStep' (q . (g b:)) cs 
     scheduleOrStep' q [] = s q 

-- schedule all completed compuations, step all the rest once, and repeat 
-- (may never complete for infinite lists) 
-- checking each row of 
-- [ [ c0s0, c1s0, c2s0, ... ] 
-- , [ c0s1, c1s1, c2s1, ... ] 
-- , [ c0s2, c1s2, c2s2, ... ] 
-- ... 
-- ] 
-- (where cNsM is computation N stepped M times) 
fair :: Strategy a 
fair [] = Done Last 
fair cs = scheduleOrStep (fair . ($[])) cs 

-- schedule more steps for earlier computations rather than later computations 
-- (works on infinite lists) 
-- checking the sw-ne diagonals of 
-- [ [ c0s0, c1s0, c2s0, ... ] 
-- , [ c0s1, c1s1, c2s1, ... ] 
-- , [ c0s2, c1s2, c2s2, ... ] 
-- ... 
-- ] 
-- (where cNsM is computation N stepped M times) 
diag :: Enqueue (Computation a)-> Strategy a 
diag _ [] = Done Last 
diag enq cs = diag' cs id 
    where diag' (c:cs) q = scheduleOrStep (diag' cs) (enq c q $ []) 
     diag' [] q = fair (q []) 

-- diagonal downwards : 
-- [ c0s0, 
-- c1s0, c0s1, 
-- c2s0, c1s1, c0s2, 
-- ... 
-- cNs0, c{N-1}s1, ..., c1s{N-1}, c0sN, 
-- ... 
-- ] 
diagd :: Strategy a 
diagd = diag prepend 

-- diagonal upwards : 
-- [ c0s0, 
-- c0s1, c1s0, 
-- c0s2, c1s1, c2s0, 
-- ... 
-- c0sN, c1s{N-1}, ..., c{s1N-1}, cNs0, 
-- ... 
-- ] 
diagu :: Strategy a 
diagu = diag append 

-- a queue type 
type Queue a = [a] -> [a] 
type Enqueue a = a -> Queue a -> Queue a 

append :: Enqueue a 
append x q = q . (x:) 

prepend :: Enqueue a 
prepend x q = (x:) . q 

Mi sento come questo è probabilmente un qualche tipo di filettatura monade?

+18

Haskell è l'unica lingua che conosco dove non si può sapere quale ruota si è appena reinventata ... –

+0

Stavo per chiudere come "localizzato", ma le persone passano davvero il loro tempo sapendo che stanno reinventando roba in Haskell ma non "cosa" stanno reinventando, rendendo questa domanda un po 'legittima (presumendo che molte persone finirebbero per reinventare questa cosa esatta, qualunque essa sia)? – Mat

+11

@Mat: Sì, in realtà. Almeno in certi modi. La gente di tanto in tanto fa battute non del tutto a Haskell, dato un codice sufficientemente generico, se digita i controlli è quasi certo che farà qualcosa di utile anche se non sei sicuro di cosa. Questo è un po 'sulla stessa linea, in quanto se si inventa qualcosa per risolvere un problema specifico e chiaramente si generalizza facilmente, è probabile che sia già stato fatto. Quando stavo imparando per la prima volta Haskell, almeno una volta ho generalizzato una soluzione specifica solo per rendermi conto di aver reinventato un angolo oscuro delle librerie standard. –

risposta

5

Sembra una monade di ripresa con stato. Penso che ci fosse una monade di ripresa in MTL intorno a GHC 6.6 ma se fosse scomparso. William Harrison presso l'Università del Missouri ha un numero di articoli sulle monadi di ripresa - http://people.cs.missouri.edu/~harrisonwl/publications.html

2

Non ho speso troppo tempo a capire il tuo codice, ma suona davvero come il monogramma di coroutine dal pacchetto monade-coroutine, che può essere un po 'più generico

+0

Lanciai brevemente un'occhiata a questo: sembrava che le coroutine fossero basate sulla comunicazione, mentre queste non erano comunicative. – rampion

2

Questo è simile alla definizione di fusione di flusso utilizzata da Don Stewart qualche tempo fa, ed è anche in qualche modo correlato agli iterate (sebbene non includa la spinta di dati nell'iterazione utilizzando un enumeratore), ma meno della fusione di flussi Suppongo.

5

non capisco perché non

data Computation a = Step (Computation a) | Done a 

instance Monad Computation where 
    (Step g) >>= f = Step $ g >>= f 
    (Done b) >>= f = Step (f b) 
    return = Done 

Non sono sicuro di ciò che questo monade è, ma è sicuramente più semplice e sembra essere equivalente sotto molti aspetti.

+0

buon punto. Mi piace. – rampion

+1

Questa è la semplice monade di ripresa. La monade originale di Rampion ha uno stato filettato come la funzione 'unfoldr', anche se non riesco a vedere se lo stato è necessario per l'esempio dato. In uno dei suoi articoli, William Harrison commenta che la monade di ripresa è fondamentalmente "inerte" senza aggiungere uno stato (inerte non è la sua parola originale ma non riesco a trovare la citazione al momento). –

+1

@stephen tetley: Con la quantificazione esistenziale ho dato lo stato, tuttavia, non c'è nulla che * può * essere fatto con esso, quindi, in effetti, è solo ritardare il calcolo. Qual è la valutazione pigra in ogni caso, quindi è equivalente alla monade di ripresa. Quindi questa è la risposta. – rampion