katydid- A haskell implementation of Katydid

Safe HaskellNone




This module is a simple implementation of the internal derivative algorithm.

It is intended to be used for explanation purposes.

This means that it gives up speed for readability.

Thus it has no type of memoization.



derive :: Tree t => Grammar -> [t] -> Either String Pattern Source #

derive is the classic derivative implementation for trees.

calls :: Grammar -> [Pattern] -> IfExprs Source #

calls returns a compiled if expression tree. Each if expression returns a child pattern, given the input value. In other words calls signature is actually:

  Refs -> [Pattern] -> Value -> [Pattern]

, where the resulting list of patterns are the child patterns, that need to be derived given the trees child values.

returns :: Grammar -> ([Pattern], [Bool]) -> [Pattern] Source #

returns takes a list of patterns and list of bools. The list of bools represent the nullability of the derived child patterns. Each bool will then replace each Node pattern with either an Empty or EmptySet. The lists do not to be the same length, because each Pattern can contain an arbitrary number of Node Patterns.

zipderive :: Tree t => Grammar -> [t] -> Either String Pattern Source #

zipderive is a slighty optimized version of derivs. It zips its intermediate pattern lists to reduce the state space.

Internal functions

These functions are exposed for testing purposes.

removeOneForEach :: [a] -> [[a]] Source #

For internal testing. removeOneForEach creates N copies of the list removing the n'th element from each.