![]() Note how similar this is to the technique of MemoisingCafs. IndirectToDirect :: IndirectDfa a -> DirectDfa a indirectToDirect ( start, states ) = tieArray ! start where tieArray = array ( 0, length states - 1 ) states ] direct ( IndirectState final trans ) = DirectState final However, in this case, the state numbers are dense integers, so it's probably easiest to use an array: In principle, you could use any dictionary data structure (e.g. What we can do is introduce a dictionary data structure to hold the (lazily evaluated) new states, then introducing a recursive reference can be done with a a simple dictionary lookup. Turning the indirect recursion into direct recursion requires tying knots, and it's not immediately obvious how to do this by holding onto lazy pointers, because any state can potentially point to any other state (or, indeed, every other state). As an exercise, consider how you might optimise transitions. (Note: We're only optimising state lookup here, not deciding which transition to take. RunDfa :: ( Eq a ) => DirectDfa a -> -> Bool runDfa ( DirectState final trans ) = final runDfa ( DirectState final trans ) ( x : xs ) = case [ s | ( x', s ) False ( s : _ ) -> runDfa s xs If this is the case, may need to use an auxiliary dictionary data structure to help you tie your knots.Ĭonsider, for example, how you would implement deterministic finite automata (DFAs). ![]() The above works for simple cases, but sometimes you need construct some very complex data structures, where the pattern of recursion is not known at compile time. This all works because of lazy evaluation. ![]() Here, we simply take the (first,last) pointers we get from go, and pass them back in as the next and prev pointers respectively, thus tying the knot. But how do we manage to create a circular list this way? How can we know right at the beginning what the pointer to the end of the list will be? ![]() This goes on right the way through the segment. We build the first node of the segment, using the given prev pointer for the left link, and the node pointer we are about to compute in the next step for the right link. go builds a segment of the list, given a pointer to the node off to the left of the segment and off to the right. ( takeF and takeR are simply to let you look at the results of mkDList: they take a specified number of elements, either forward or backward). The back pointers are easy, but what about the forward ones?ĭata DList a = DLNode ( DList a ) a ( DList a ) mkDList :: -> DList a mkDList = error "must have at least one element" mkDList xs = let ( first, last ) = go last xs first in first where go :: DList a -> -> DList a -> ( DList a, DList a ) go prev next = ( next, prev ) go prev ( x : xs ) next = let this = DLNode prev x rest ( rest, last ) = go this xs next in ( this, last ) takeF :: Integer -> DList a -> takeF 0 _ = takeF n ( DLNode _ x next ) = x : ( takeF ( n - 1 ) next ) takeR :: Show a => Integer -> DList a -> takeR 0 _ = takeR n ( DLNode prev x _ ) = x : ( takeR ( n - 1 ) prev ) Say you want to build a circular, doubly-linked list, given a standard Haskell list as input.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |