Safe Haskell | None |
---|---|
Language | Haskell2010 |
Functionality for traversing an Enumeration
.
This module provides a typeclass, Traversal
, which represents a
traversal scheme for Enumeration
s. Traversals should be largely
independent of the Enumeration
, though some variants like
Prioritized
cannot be wholly independent.
Three Traversal
instances are provided by this module:
DepthFirst
, BreadthFirst
, and Prioritized
. All traversals
work by maintaining a set of positions, which consist of an
Enumeration
and an index (the next value to give as a first path
element). At each step, some position is "expanded" by replacing
it with two positions: one with the index as an additional prefix
element, and one with the index incremented.
DepthFirst
is a simple depth-first scheme. It is not guaranteed
to reach all elements, and in some Enumeration
s, it may never
produce an answer.
BreadthFirst
is a breadth-first scheme, which tends to be
better-behaved than DepthFirst
. It explores paths in ascending
order of path length. For Enumeration
s with infinite-sized
branches, its behavior is not strictly breadth-first (as this would
never yield an answer), but it should still behave well for this
case.
Prioritized
is a scheme that uses a scoring function to rank
paths. At each step, it will select the "best" (highest-ranked)
option and expand it.
Synopsis
- class Traversal trav where
- mkTraversal :: Enumeration ty -> trav ty
- getNext :: trav ty -> Maybe (ty, Path, trav ty)
- getAll :: trav ty -> [(ty, Path)]
- data DepthFirst ty
- data BreadthFirst ty
- data Prioritized ty
- scoring :: Prioritized ty -> (Enumeration ty, Integer) -> Float
- mkPrioritizedTraversal :: ((Enumeration ty, Integer) -> Float) -> Enumeration ty -> Prioritized ty
Documentation
class Traversal trav where Source #
A typeclass representing a traversal scheme over an enumeration.
mkTraversal :: Enumeration ty -> trav ty Source #
Create a Traversal
from an Enumeration
.
getNext :: trav ty -> Maybe (ty, Path, trav ty) Source #
Get the next item in the traversal.
getAll :: trav ty -> [(ty, Path)] Source #
Get all items in the traversal as a list.
Instances
Traversal Prioritized Source # | |
Defined in Data.Enumeration.Traversal mkTraversal :: Enumeration ty -> Prioritized ty Source # getNext :: Prioritized ty -> Maybe (ty, Path, Prioritized ty) Source # getAll :: Prioritized ty -> [(ty, Path)] Source # | |
Traversal BreadthFirst Source # | |
Defined in Data.Enumeration.Traversal mkTraversal :: Enumeration ty -> BreadthFirst ty Source # getNext :: BreadthFirst ty -> Maybe (ty, Path, BreadthFirst ty) Source # getAll :: BreadthFirst ty -> [(ty, Path)] Source # | |
Traversal DepthFirst Source # | |
Defined in Data.Enumeration.Traversal mkTraversal :: Enumeration ty -> DepthFirst ty Source # getNext :: DepthFirst ty -> Maybe (ty, Path, DepthFirst ty) Source # getAll :: DepthFirst ty -> [(ty, Path)] Source # |
data DepthFirst ty Source #
Depth-first traversal. Note that this style of traversal is not guaranteed to be complete (it may deep-dive and never visit some possibilities). However, this implementation should continue producing results even with infinite-sized branches, so long as the depth of any one path isn't too great.
Instances
Traversal DepthFirst Source # | |
Defined in Data.Enumeration.Traversal mkTraversal :: Enumeration ty -> DepthFirst ty Source # getNext :: DepthFirst ty -> Maybe (ty, Path, DepthFirst ty) Source # getAll :: DepthFirst ty -> [(ty, Path)] Source # |
data BreadthFirst ty Source #
Breadth-first traversal. This style of traversal is guaranteed to be complete- that is, it will visit every possibility eventually. However, it may take a very long time to reach any given possibility.
Instances
Traversal BreadthFirst Source # | |
Defined in Data.Enumeration.Traversal mkTraversal :: Enumeration ty -> BreadthFirst ty Source # getNext :: BreadthFirst ty -> Maybe (ty, Path, BreadthFirst ty) Source # getAll :: BreadthFirst ty -> [(ty, Path)] Source # |
data Prioritized ty Source #
Prioritized traversal. Will always pick the highest-scored option. Completeness depends entirely on the scoring function.
Instances
Traversal Prioritized Source # | |
Defined in Data.Enumeration.Traversal mkTraversal :: Enumeration ty -> Prioritized ty Source # getNext :: Prioritized ty -> Maybe (ty, Path, Prioritized ty) Source # getAll :: Prioritized ty -> [(ty, Path)] Source # |
scoring :: Prioritized ty -> (Enumeration ty, Integer) -> Float Source #
The scoring function used in a Prioritized
traversal scheme.
mkPrioritizedTraversal Source #
:: ((Enumeration ty, Integer) -> Float) | The scoring function to use. |
-> Enumeration ty | The enumeration to use. |
-> Prioritized ty |
Create a prioritized traversal with a given scoring function.