-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | ADP for multiple context-free languages
--   
--   adp-multi is an implementation of Algebraic Dynamic Programming for
--   multiple context-free languages. It is a library based on the original
--   Haskell implementation and can be considered an unoptimized prototype.
@package adp-multi
@version 0.2.1


-- | Default model of rewriting functions used in adp-multi.
module ADP.Multi.Rewriting.Model

-- | Every 1-dim parser has one symbol, every 2-dim parser two symbols. In
--   a production with parsers p1 to pn, each parser has a number, 1 to n.
--   Each symbol of a parser also has a number, 1 or 2, as only two
--   dimensions are supported now. Both numbers form a unique identifier
--   for each symbol in a production.
--   
--   Example: f > r
--   
--   a and c shall have dimension 1, b dimension 2. Then a has id (1,1), b
--   has ids (2,1) and (2,2), and c has (3,1). Applying a rewriting
--   function of type <a>Dim1</a> or <a>Dim2</a> to the list of ids
--   produces a permutation of those, possibly split up in two dimensions.
--   
--   E.g., [(1,1),(2,1),(2,2),(3,1)] gets ([(2,1),(3,1)],[(2,2),(1,1)]) if
--   the rewriting function is: r [a,b1,b2,c] = ([b1,c],[b2,a]).
type SymbolID = (Int, Int)

-- | 1-dimensional rewriting function
type Dim1 = [SymbolID] -> [SymbolID]

-- | 2-dimensional rewriting function
type Dim2 = [SymbolID] -> ([SymbolID], [SymbolID])

-- | Convenience rewriting function for one or more dim1 symbols
id1 :: Dim1

-- | Convenience rewriting function for one dim2 symbol
id2 :: Dim2


-- | Some common types for parsers.
module ADP.Multi.Parser

-- | To support higher dimensions, a subword is a list of indices. Valid
--   list lengths are 2n with n&gt;0.
type Subword = [Int]
type Parser a b = Array Int a -> Subword -> [b]

-- | Static information about yield sizes of a parser. For supporting
--   dimensions &gt; 2, this type has to be expanded with more
--   constructors, or redesigned to be generic.
data ParserInfo
ParserInfo1 :: Int -> Maybe Int -> ParserInfo
minYield :: ParserInfo -> Int
maxYield :: ParserInfo -> Maybe Int
ParserInfo2 :: (Int, Int) -> (Maybe Int, Maybe Int) -> ParserInfo
minYield2 :: ParserInfo -> (Int, Int)
maxYield2 :: ParserInfo -> (Maybe Int, Maybe Int)
type RichParser a b = (ParserInfo, Parser a b)
class Parseable p a b | p -> a b
toParser :: Parseable p a b => p -> RichParser a b
instance Eq ParserInfo
instance Show ParserInfo
instance Parseable (RichParser a b) a b


-- | Elementary parsers for dimensions 1 and 2
module ADP.Multi.ElementaryParsers
string :: Eq a => [a] -> RichParser a [a]
string2 :: Eq a => [a] -> [a] -> RichParser a ([a], [a])
empty1 :: RichParser a EPS
empty2 :: RichParser a (EPS, EPS)
anychar :: RichParser a a
anycharExcept :: Eq a => [a] -> RichParser a a
anychar2 :: RichParser a (a, a)
char :: Eq a => a -> RichParser a a
char2 :: Eq a => a -> a -> RichParser a (a, a)
charLeftOnly :: Eq a => a -> RichParser a (a, EPS)
charRightOnly :: Eq a => a -> RichParser a (EPS, a)
data EPS
EPS :: EPS
instance Typeable EPS
instance Eq EPS
instance Show EPS
instance Data EPS
instance Parseable (Char, EPS) Char (Char, EPS)
instance Parseable (EPS, Char) Char (EPS, Char)
instance Parseable (Char, Char) Char (Char, Char)
instance Parseable Char Char Char
instance Eq a => Parseable ([a], [a]) a ([a], [a])
instance Eq a => Parseable [a] a [a]
instance Parseable (EPS, EPS) a (EPS, EPS)
instance Parseable EPS a EPS


-- | Combinators for two- and four-dimensional tabulation
module ADP.Multi.Tabulation

-- | Two-dimensional tabulation for one-dim. parsers
table1' :: Array Int a -> Parser a b -> Parser a b

-- | Two-dimensional tabulation for one-dim. parsers
table1 :: Array Int a -> RichParser a b -> RichParser a b

-- | Four-dimensional tabulation for two-dim. parsers
table2' :: Array Int a -> Parser a b -> Parser a b

-- | Four-dimensional tabulation for two-dim. parsers
table2 :: Array Int a -> RichParser a b -> RichParser a b


-- | Provides several convenience functions to ease parsing setup.
module ADP.Multi.Helpers

-- | Turns an input sequence into an array for use with a 1-dim parser.
--   Typically, this prepares the input for the <a>axiom</a> function.
mk :: [a] -> Array Int a

-- | Turns two input sequences into an array for use with a 2-dim parser.
--   Typically, this prepares the input for the <a>axiomTwoTrack</a>
--   function.
mkTwoTrack :: [a] -> [a] -> Array Int a

-- | Convenience function for parsing a given input using a 1-dim parser,
--   usually the start nonterminal.
axiom :: Array Int a -> RichParser a b -> [b]

-- | Convenience function for parsing a given input pair using a 2-dim
--   parser, usually the start nonterminal.
axiomTwoTrack :: Eq a => Array Int a -> [a] -> [a] -> RichParser a b -> [b]


-- | Types for the rewriting combinator
module ADP.Multi.Rewriting

-- | Tree of subwords. Every path in a tree represents a sequence of
--   subwords for a corresponding sequence of parsers in a production.
data SubwordTree
SubwordTree :: Subword -> [SubwordTree] -> SubwordTree
type SubwordConstructionAlgorithm a = a -> [ParserInfo] -> Subword -> [SubwordTree]
instance Show SubwordTree


-- | Parser combinators for use in grammars
module ADP.Multi.Combinators
(<<<) :: Parseable p a b => (b -> c) -> p -> ([ParserInfo], [SubwordTree] -> Parser a c)
(~~~) :: Parseable p a b => ([ParserInfo], [SubwordTree] -> Parser a (b -> c)) -> p -> ([ParserInfo], [SubwordTree] -> Parser a c)
class Rewritable r a b
(>>>) :: Rewritable r a b => ([ParserInfo], [SubwordTree] -> Parser a b) -> r -> RichParser a b
rewrite :: SubwordConstructionAlgorithm a -> ([ParserInfo], [SubwordTree] -> Parser b c) -> a -> Parser b c
(|||) :: RichParser a b -> RichParser a b -> RichParser a b
(...) :: RichParser a b -> ([b] -> [b]) -> RichParser a b

-- | Filters are not part of ADP-MCFL, but are sometimes used in RNA
--   folding to skip parses where subwords are too long, e.g. restricting
--   loop size to 30. It is included here for convenience.
type Filter a = Array Int a -> Subword -> Bool
with :: RichParser a b -> Filter a -> RichParser a b

-- | Explicitly specify yield size of a 1-dim parser.
yieldSize1 :: (Int, Maybe Int) -> RichParser a b -> RichParser a b

-- | Explicitly specify yield size of a 2-dim parser.
yieldSize2 :: (Int, Maybe Int) -> (Int, Maybe Int) -> RichParser a b -> RichParser a b


-- | Calculates yield sizes using rewriting functions.
module ADP.Multi.Rewriting.YieldSize
type YieldAnalysisAlgorithm a = a -> [ParserInfo] -> ParserInfo
determineYieldSize1 :: YieldAnalysisAlgorithm Dim1
determineYieldSize2 :: YieldAnalysisAlgorithm Dim2
combineYields :: [YieldSize] -> YieldSize

-- | min and max yield size
type YieldSize = (Int, Maybe Int)

-- | Maps each parser symbol to its yield size (remember: a 2-dim parser
--   has 2 symbols in a rewriting function)
type YieldSizeMap = Map (Int, Int) YieldSize
buildYieldSizeMap :: [ParserInfo] -> YieldSizeMap


-- | Convenience module to import everything except a specific rewriting
--   combinator implementation. See <a>ADP.Multi.Rewriting.All</a> for
--   that.
module ADP.Multi.All


-- | Debugging is enabled via the cabal flag <i>DEBUG</i>
module ADP.Debug
trace :: String -> a -> a

module ADP.Multi.Rewriting.Explicit
constructSubwords1 :: SubwordConstructionAlgorithm Dim1
constructSubwords2 :: SubwordConstructionAlgorithm Dim2


-- | Provides instance implementations for the &gt;&gt;&gt; combinator
--   using the <i>explicit</i> subword construction algorithm.
module ADP.Multi.Rewriting.Combinators
instance Rewritable Dim2 a b
instance Rewritable Dim1 a b


-- | Convenience module to import the specific rewriting function model and
--   combinator implementation known as <i>explicit</i>. In package
--   adp-multi-monadiccp, there is another combinator implementation.
module ADP.Multi.Rewriting.All