The state of the greedy parse between steps. Generally, the current reduction consists of frozen transitions between the ⋊ and the current location and open transitions between the current location and ⋉.

⋊==[1]==[2]==[3]——[4]——[5]——⋉
  └ frozen  ┘  | └   open  ┘
            midSlice (current position)

frozen:   ==[2]==[1]==
midSlice: [3]
open:     ——[4]——[5]——

This is the GSSemiOpen case: The slice at the current pointer ([3]) is represented as an individual slice (midSlice). The frozen part is represented by a Path of frozen transitions (tr') and slices (slc). in reverse direction, i.e. from midslice back to ⋊ (excluding ⋊). The open part is a Path of open transitions (tr) and slices (slc) in forward direction from midSlice up to ⋉.

There are two special cases. All transitions can be frozen (GSFrozen), in which case state only contains the backward Path of frozen transitions (excluding ⋊ and ⋉):

⋊==[1]==[2]==[3]==⋉
                   └ current position
represented as: ==[3]==[2]==[1]==

Or all transitions can be open (GSOpen), in which case the state is just the forward path of open transitions:

⋊——[1]——[2]——[3]——⋉
└ current position
represented as: ——[1]——[2]——[3]——

The open and semiopen case additionally have a list of operations in generative order, and a flag that indicates whether the previous step was a left operation, which would prevent continuing with a right unsplit.

Helper function for showing the frozen part of a piece.

Helper function for showing the open part of a piece.

Single parent of a parsing action

A parsing action (reduction step) with a single parent transition. Combines the parent elements with a single-transition derivation operation.

Single parent of a parsing action

A parsing action (reduction step) with two parent transitions. Combines the parent elements with a double-transition derivation operation.

An alias that combines ActionSingle and ActionDouble, representing all possible reduction steps.

A helper function that checks whether an action: - - is a double action and goes left ('Just True') - - is a double action and goes right ('Just False') - - is a single action (Nothing, doesn't have to choose). - (See opGoesLeft.)

A helper function that checks whether a derivation operation: - - is a double op and goes left ('Just True') - - is a double op and goes right ('Just False') - - is a single op (Nothing, doesn't have to choose). - (See actionGoesLeft.)

Parse a piece in a greedy fashion. At each step, a policy chooses from the possible reduction actions, the reduction is applied, and parsing continues until the piece is fully reduced or no more reduction operations are available. Returns the full derivation from the top (⋊——⋉) or an error message.

Initializes a parse state. Takes an evaluator and a (frozen) input path. Returns the parsing state that corresponds to the unparsed input.

A single greedy parse step. Enumerates a list of possible actions in the current state and applies a policy function to select an action. The resulting state is returned, wrapped in a monad transformer stack containing String exceptions and the monad of the policy.

Enumerates the list of possible actions in the current state

A policy that picks the next action at random. Must be partially applied with a random generator before passing to parseGreedy.

Apply an action to a parsing state.

Parse a piece randomly using a fresh random number generator.

Parse a piece randomly using an existing random number generator.