Staat in einer zustandslosen Welt halten

Question

Ich konvertiere eine kontextfreie Grammatik in Greifach Normal Form (GNF). Die Haupttransformation (von Hopcroft & Ullman) ist eine Folge von Iterationen über die indizierten Variablen der Grammatik. Es ist im Wesentlichen "staatenlos". Ich habe es als eine Folge von Falten über den entsprechenden Indizes umgesetzt (die Umsetzung ist recht einfach):

gnf :: Ord a => Set (Rule a) -> Set (Rule a) 
gnf rl = foldl step1 rl [1..maxIndex rl] 
where step1 rl' k = foldl step2 rl' [1..k - 1] 
     where step2 rl'' j = noLR k (subst rl'' k j) 

MaxIndex rl den maximalen Variablenindex in einer Reihe von Regeln gibt; subst rl k j führt Substitution auf die k-indizierten Regeln durch die Regeln, deren rechte Seite beginnt mit einer j -indizierte Variable. Nachdem ich gnf durchgeführt habe, muss ich einen letzten Durchgang über die Grammatik in umgekehrter Reihenfolge durchführen.

Das Problem ist noLR, die eine Grammatik mit linksrekursive k -indexed Regeln transformiert. Dies ist eine "stateful" -Funktion, da für jede Regel (oder k -indexierte Regel) eine eindeutige Variable generiert werden muss, auf die noLR angewendet wird. Also schrieb ich eine Stateful-Funktion

noLR :: Ord a => Int -> Set (Rule a) -> State [Sym a] (Set (Rule a)) 
noLR rl = do (n:ns) <- get; put ns; 
      let rl' = ... remove left recursion rl n ... 
       in return rl' 

Ich kann die noLR um sequenzieren zusammen die n zu aktualisieren, die noLR als Parameter annimmt. Ich bin nicht sicher, wie man noLR innerhalb Schritt2 in der obigen Funktion durchzuführen, obwohl. Ich kann das Schema let ... in nicht verwenden, weil die statusbehaftete Berechnung in mehrere rekursive Funktionen eingebettet ist.

Was will ich tun haben n irgendeine Art von globalen Variablen sein, ähnlich wie bei einem expliziten Einfädeln n, die ich innerhalb schritt2 nennen und Update kann, weshalb ich ursprünglich die Funktion geschrieben als eine Falte mit eta -Expansion (für n). Weiß jemand, wie ich gnf innerhalb der Staat Monade strukturieren könnte, um diese Art von Effekt zu erreichen? Bis auf die letzte Berechnung in der Falte ist nichts anderes "stateful", und ich bin nur mit der Zustands-Monade mit "trivialen" Beispielen vertraut. Ich bin ziemlich verloren.

Answer 1

Um noLR mit dem Typ zu verwenden, die Sie gegeben haben, müssen Sie Ihre GNF Funktion entlang der folgenden Zeilen umschreiben:

gnf :: Ord a => Set (Rule a) -> Set (Rule a) 
gnf rl = evalState (foldM step1 rl [1..maxIndex rl]) (... generate the initial state [Sym a] here ...) 
where step1 rl' k = foldM step2 rl' [1..k - 1] 
     where step2 rl'' j = noLR k (subst rl'' k j) 

Ihre Zustandsgröße während der gesamten Berechnung vorhanden ist, und dass Tatsache muss im Code explizit gemacht werden.

Wenn Sie nur brauchen, dass die neu generierten Variablennamen nicht miteinander kollidieren, dann können Sie noLR rein machen, indem Sie einen neuen Symbolnamen aus den Indizes k und j generieren - so etwas wie "foo_42_16" für k == 42 und j == 16. Wenn die Eingabegrammatik bereits solche Symbolnamen enthält, könnten Sie jedoch Probleme haben.

Wenn Sie brauchen, dass Ihre Symbole in der Grammatik einzigartig sind, warum nicht einfach das sagen?

newSymbol :: Set (Rule a) -> Sym a 
newSymbol rl = ... find a symbol name not used in rl ... 

Dies ist definitiv nicht effizient, aber es sei denn, Sie Set ersetzen (Regel a) durch eine andere Art, die Sie newSymbol Betrieb effizienter implementieren kann.

Answer 2

Ich würde versuchen, noLR rein zu schreiben. Sind Sie sicher, dass Sie es nicht umschreiben können, um ein Symbol zu erzeugen, das nur vom Namen der Regel und ihrem Index (oder etwas Ähnlichem) abhängt?

noLR k j = noLR' k j $ newSymbol k j 
    where newSymbol k j = ... -- some concatenation of k and j 
      noLR' k j sym = ... -- your now pure function