liveBook · Manning

Frontier

As explained in Learn Haskell by Example

A frontier is the collection of graph nodes currently being explored or awaiting expansion in a search.

A frontier is the collection of graph nodes currently being explored or awaiting expansion. Breadth-first search updates it layer by layer instead of immediately following one neighbor as depth-first search does. section 6.1.1

A breadth-first search updates the frontier by:

  • Starting with the graph and starting node as the initial frontier. section 6.1.1
  • Collecting neighboring nodes for every node in the current frontier. section 6.1.1
  • Deleting the current frontier from the graph so visited nodes are not revisited. section 6.1.1
  • Using the newly collected nodes as the next frontier and recording predecessors for path reconstruction. section 6.1.1 section 6.1.2

Search-state implementation

A search state can store the frontier, the remaining graph, and a predecessor graph: `type SearchState a = ([a], DiGraph a, DiGraph a)`. Each recursive step deletes the current frontier, computes children still present in the graph, concatenates them into `frontier'`, and continues searching. section 6.1.2

How Learn Haskell by Example covers it

How deep it goes
Explains frontier updates procedurally, including child collection, visited-node deletion, predecessor recording, and termination checks.
Examples
Uses graph-layer diagrams, a word-ladder search, and typed search-state and breadth-first-search definitions.
What it assumes
Assumes graphs, nodes, neighbors, and breadth-first versus depth-first search, while introducing an explicit search-state representation.
What you can do after
Apply the frontier pattern to implement breadth-first path searches with visited-node tracking and predecessor-based reconstruction.
How it connects
Connects the frontier to breadth-first search, depth-first search, graphs, search state, and predecessor graphs.
Cover of Learn Haskell by Example
liveBookmanning.com
Read Learn Haskell by Example on liveBook Get the book at manning.com

Also explained in

Compare how 2 books explain frontier →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Learn Haskell by Example. The section links point to the parts of the book it draws on.