> {-# OPTIONS_HADDOCK show-extensions #-}
> {-|
> Module    : LTK.Learn.StringExt
> Copyright : (c) 2019 Dakotah Lambert
> License   : MIT
> 
> A generic implementation of Jeff Heinz's "String Extension Learning".
> For details, see https://www.aclweb.org/anthology/P10-1092
>
> @since 0.3
> -}
> module LTK.Learn.StringExt ( Grammar(..)
>                            , learn
>                            , augmentSE
>                            , isRecognizedBy
>                            ) where

> import Control.DeepSeq (NFData)

> import LTK.Containers
> import LTK.FSA (FSA)

> -- |Construct a grammar from a finite initial segment of a positive text.
> -- The function argument \(f\) should be such that
> -- if \(G=f(L)\) and \(f(w)\in G\) then \(w\in L\).
> -- In order to be able to learn the empty set,
> -- the text argument allows for time points at which
> -- no data is provided.
> learn :: (Grammar g, Ord b, Collapsible s) =>
>          (a -> g b) -> s (Maybe a) -> g b
> learn :: (a -> g b) -> s (Maybe a) -> g b
learn a -> g b
f = (a -> g b) -> g b -> s (Maybe a) -> g b
forall (g :: * -> *) b (s :: * -> *) a.
(Grammar g, Ord b, Collapsible s) =>
(a -> g b) -> g b -> s (Maybe a) -> g b
augmentSE a -> g b
f g b
forall (g :: * -> *) a. (Grammar g, Ord a) => g a
emptyG

> -- |Add more data to a grammar generated by @learn@.
> augmentSE :: (Grammar g, Ord b, Collapsible s) =>
>              (a -> g b) -> g b -> s (Maybe a) -> g b
> augmentSE :: (a -> g b) -> g b -> s (Maybe a) -> g b
augmentSE a -> g b
f = (Maybe a -> g b -> g b) -> g b -> s (Maybe a) -> g b
forall (c :: * -> *) a b.
Collapsible c =>
(a -> b -> b) -> b -> c a -> b
collapse (g b -> g b -> g b
forall (g :: * -> *) a. (Grammar g, Ord a) => g a -> g a -> g a
augmentG (g b -> g b -> g b) -> (Maybe a -> g b) -> Maybe a -> g b -> g b
forall b c a. (b -> c) -> (a -> b) -> a -> c
. g b -> (a -> g b) -> Maybe a -> g b
forall b a. b -> (a -> b) -> Maybe a -> b
maybe g b
forall (g :: * -> *) a. (Grammar g, Ord a) => g a
emptyG a -> g b
f)

> -- |True iff the given object is in the set represented by the given grammar.
> isRecognizedBy :: (Grammar g, Ord b) => (a -> g b) -> g b -> a -> Bool
> isRecognizedBy :: (a -> g b) -> g b -> a -> Bool
isRecognizedBy a -> g b
f g b
g = g b -> g b -> Bool
forall (g :: * -> *) a. (Grammar g, Ord a) => g a -> g a -> Bool
isSubGOf g b
g (g b -> Bool) -> (a -> g b) -> a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> g b
f

> -- |A grammar is a representation of a mechanism
> -- by which one can determine
> -- whether or not a given object is in a given set.
> class Grammar g
>     where genFSA :: (NFData a, Ord a) => g a -> FSA Integer a
>           augmentG :: Ord a => g a -> g a -> g a
>           isSubGOf :: Ord a => g a -> g a -> Bool
>           emptyG :: Ord a => g a