Data.Enumeration.Traversal

Functionality for traversing an Enumeration.

This module provides a typeclass, Traversal, which represents a traversal scheme for Enumerations. 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 Enumerations, 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 Enumerations 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.

Documentation

class Traversal trav where

A typeclass representing a traversal scheme over an enumeration.

Minimal complete definition

mkTraversal, getNext

Methods

mkTraversal :: Enumeration ty -> trav ty

Create a Traversal from an Enumeration.

getNext :: trav ty -> Maybe (ty, Path, trav ty)

Get the next item in the traversal.

getAll :: trav ty -> [(ty, Path)]

Get all items in the traversal as a list.

Instances

Traversal Prioritized

Defined in Data.Enumeration.Traversal

Methods

mkTraversal :: Enumeration ty -> Prioritized ty

getNext :: Prioritized ty -> Maybe (ty, Path, Prioritized ty)

getAll :: Prioritized ty -> [(ty, Path)]

Traversal BreadthFirst

Defined in Data.Enumeration.Traversal

Methods

mkTraversal :: Enumeration ty -> BreadthFirst ty

getNext :: BreadthFirst ty -> Maybe (ty, Path, BreadthFirst ty)

getAll :: BreadthFirst ty -> [(ty, Path)]

Traversal DepthFirst

Defined in Data.Enumeration.Traversal

Methods

mkTraversal :: Enumeration ty -> DepthFirst ty

getNext :: DepthFirst ty -> Maybe (ty, Path, DepthFirst ty)

getAll :: DepthFirst ty -> [(ty, Path)]

data DepthFirst ty

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

Defined in Data.Enumeration.Traversal

Methods

mkTraversal :: Enumeration ty -> DepthFirst ty

getNext :: DepthFirst ty -> Maybe (ty, Path, DepthFirst ty)

getAll :: DepthFirst ty -> [(ty, Path)]

data BreadthFirst ty

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

Defined in Data.Enumeration.Traversal

Methods

mkTraversal :: Enumeration ty -> BreadthFirst ty

getNext :: BreadthFirst ty -> Maybe (ty, Path, BreadthFirst ty)

getAll :: BreadthFirst ty -> [(ty, Path)]

data Prioritized ty

Prioritized traversal. Will always pick the highest-scored option. Completeness depends entirely on the scoring function.

Instances

Traversal Prioritized

Defined in Data.Enumeration.Traversal

Methods

mkTraversal :: Enumeration ty -> Prioritized ty

getNext :: Prioritized ty -> Maybe (ty, Path, Prioritized ty)

getAll :: Prioritized ty -> [(ty, Path)]

scoring :: Prioritized ty -> (Enumeration ty, Integer) -> Float

The scoring function used in a Prioritized traversal scheme.

mkPrioritizedTraversal

Arguments

:: ((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.