Haskell-koden är utvecklad för två sätt att lista strängarna i det språk som definieras av ett reguljärt uttryck: direkt genom inställda operationer och indirekt genom att konvertera till och simulera en likvärdig automaton. Övningen illustrerar tekniker för att hantera oändligt ordnade domäner och leder till en effektiv standardform för icke-deterministiska ändliga automata. Lata språk är väl lämpade för sekvensgenerering på grund av den lätthet med vilken de hanterar oändliga sekvenser. Problemet med att räkna upp strängarna i ett vanligt språk föreslogs av Jay Misra som ett vackert fall i punkt, enkelt att säga, men svårt att lösa. I detta dokument utvecklas två koncisa och radikalt olika lösningar i Haskell (Peterson et al., 1998), en direkt och en indirekt. Båda tillvägagångssätten utnyttjar Haskells enastående kondition för strukturell induktion. Det direkta tillvägagångssättet tolkar reguljära uttryck som recept för byggsatser. Här är huvudfrågan att programmera de primitiva för att kombinera uppsättningar: union, tvärprodukt, och stängning under en binär operation. De primitiva gäller alla välordnade domäner. Den indirekta metoden avleder genom automata, först konstruera en likvärdig icke-deterministisk finita automaton, sedan spåra utförandet vägar automaton i bredd-först ordning. Automaten har en ovanlig form: förutom ett enda sluttillstånd finns det exakt ett tillstånd per symbol i det reguljära uttrycket och detta tillstånd tar bara emot en symbol. De åtgärder som utvecklats för den första lösningen används igen, denna gång för att kombinera uppsättningar av stater snarare än uppsättningar av strängar. Använda Haskell kod är tillgänglig elektroniskt. (McIlroy, 2003) 1 Problemet Devise ett program för att räkna upp de distinkta strängar i det reguljära språket som betecknas med ett givet reguljärt uttryck. Den resulterande listan bör beställas efter stränglängd och lexikografiskt inom varje längd. Tolkning är inte aktuell; reguljära uttryck anses redan vara tolkade datastrukturer.
REF genomför uppräkning av alla strängar av ett vanligt språk i Haskell.
Enumerating the strings of regular languages
{'venue': 'J. Funct. Program.', 'journal': 'J. Funct. Program.', 'mag_field_of_study': ['Computer Science']}