Copyright	(c) 2017-2023 Jim Rogers and Dakotah Lambert
License	MIT
Safe Haskell	Safe-Inferred
Language	Haskell2010
Extensions	Cpp

LTK.Traversals

Description

Find paths through an automaton.

Synopsis

Documentation

data Path n e #

A path through an FSA.

Constructors

Path
Fields labels :: [Symbol e] Edge labels are gathered in reverse order, so `labels` is a reversed string. endstate :: Maybe (State n) Current `State`, if any. stateMultiset :: Multiset (State n) States seen so far, with multiplicity. depth :: Integer The number of edges taken so far.

Instances details

Ord n => Monoid (Path n e) #
Instance details Defined in LTK.Traversals Methods mempty :: Path n e # mappend :: Path n e -> Path n e -> Path n e # mconcat :: [Path n e] -> Path n e #
Ord n => Semigroup (Path n e) #
Instance details Defined in LTK.Traversals Methods (<>) :: Path n e -> Path n e -> Path n e # sconcat :: NonEmpty (Path n e) -> Path n e # stimes :: Integral b => b -> Path n e -> Path n e #
(Show e, Show n) => Show (Path n e) #
Instance details Defined in LTK.Traversals Methods showsPrec :: Int -> Path n e -> ShowS # show :: Path n e -> String # showList :: [Path n e] -> ShowS #
(Eq e, Eq n) => Eq (Path n e) #
Instance details Defined in LTK.Traversals Methods (==) :: Path n e -> Path n e -> Bool # (/=) :: Path n e -> Path n e -> Bool #
(Ord e, Ord n) => Ord (Path n e) #
Instance details Defined in LTK.Traversals Methods compare :: Path n e -> Path n e -> Ordering # (<) :: Path n e -> Path n e -> Bool # (<=) :: Path n e -> Path n e -> Bool # (>) :: Path n e -> Path n e -> Bool # (>=) :: Path n e -> Path n e -> Bool # max :: Path n e -> Path n e -> Path n e # min :: Path n e -> Path n e -> Path n e #

word :: Path n e -> [Symbol e] #

The reversal of the labels of the Path.

isAcyclic :: (Ord n, Ord e) => FSA n e -> Bool #

True iff the given FSA contains no reachable cycles.

Since: 1.0

initialsPaths :: (Ord e, Ord n) => FSA n e -> Set (Path n e) #

Initial open list for traversal from initial states.

initialsNDPath :: (Ord e, Ord n) => FSA n e -> Path (Set n) e #

Initial open list for non-deterministic traversal from initial states.

All paths of length less than or equal to a given bound that do not end in an accepting state.

acyclicPaths :: (Ord e, Ord n) => FSA n e -> Set (Path n e) #

All paths from initialsPaths that do not contain cycles.

extensions :: (Ord e, Ord n) => FSA n e -> Path n e -> Set (Path n e) #

Paths extending a given path by a single edge.

Extensions other than back-edges to a state that has been visited more than a given number of times.

The extensions of a non-deterministic path other than back-edges