2015-09-18 16 views
7

Prendi questo semplice funtore base e altri macchinari per una monade libero con termini vincolanti:Esaminando la struttura di legame in una monade libera AST

{-# LANGUAGE DeriveFunctor #-} 

import Control.Monad.Free 

data ProgF r = 
    FooF (Double -> r) 
    | BarF Double (Int -> r) 
    | EndF 
    deriving Functor 

type Program = Free ProgF 

foo = liftF (FooF id) 
bar a = liftF (BarF a id) 

Ed ecco un semplice programma

prog :: Program Int 
prog = do 
    a <- foo 
    bar a 

E 'il in seguito (a mano artigianale) AST:

prog = 
    Free (FooF (\p0 -> 
    Free (BarF p0 (\p1 -> 
     Pure p1)) 

Quello che mi piacerebbe essere in grado di fare è ragionare su termini legata al fol modo muggito:

  • cerca il termine Pure nella AST
  • nota variabili associate che si verificano ci
  • annotare i corrispondenti nodi vincolanti in AST

Annotazione direttamente monade AST gratuito tramite un cofree comonad sembra impossibile senza fare some kind of pairing, ma potresti immaginare di ottenere qualcosa come il seguente AST annotato (via, diciamo, Fix) in cui i nodi vincolano le variabili che appaiono in Pure è annotato con Just True:

annotatedProg = 
    Just False :< FooF (\p0 -> 
    Just True :< BarF p0 (\p1 -> 
     Nothing :< EndF)) 

Quindi: c'è un modo per ispezionare le associazioni in un programma come questo in un modo ad hoc? Ad esempio, senza introdurre un tipo di variabile distinto à la this question, ad esempio.

Sospetto che ciò sia impossibile da fare. Le opzioni come data-reify sono interessanti ma sembra estremamente difficile o impossibile rendere ProgF un'istanza dei tipi di caratteri richiesti (Foldable, Traversable, MuRef).

L'intuizione è corretta, o ci sono dei mezzi per fare ciò che non ho considerato? Nota che sono felice di intrattenere ogni mezzo incredibilmente pericoloso o dinamico.

+0

Sospetto che sarete in grado di farlo abbastanza facilmente per i Dags, ma le altre strutture saranno cattive. – dfeuer

+0

@dfeuer Sto credendo sempre meno che sia facile. Ma mi piacerebbe essere smentito! :) – jtobin

+0

Penso che la domanda potrebbe essere un po 'più chiara. – dfeuer

risposta

1

Sono convinto che ciò non sia possibile con qualsiasi metodo "sano" ad hoc, per lo stesso motivo per cui non è possibile esaminare la struttura di legame di ad es. \a -> \b -> \c -> b + a.