Derive

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.

Documentation

derive :: Tree t => Refs -> [t] -> Except String Pattern

derive is the classic derivative implementation for trees.

calls :: Refs -> [Pattern] -> IfExprs

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 :: Refs -> ([Pattern], [Bool]) -> [Pattern]

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 => Refs -> [t] -> Except String Pattern

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