Safe Haskell	Safe-Inferred
Language	Haskell2010

Pattern.Graph

Contents

Graph Lens Type
Node Operations
Relationship Operations
Walk Operations
Navigation Operations
Graph Analysis Operations

Description

Graph Lens: Interpretive view of Pattern structures as graphs.

This module provides the Graph Lens feature, which enables interpreting Pattern structures as graph structures (nodes, relationships, walks) through a minimal, elegant design based on a single predicate.

Overview

A Graph Lens provides an interpretive view of a Pattern as a graph structure. Rather than defining graph concepts (nodes, relationships, walks) as intrinsic properties of Pattern, they emerge through the lens's interpretation. This design enables multiple graph views of the same Pattern and supports higher-order graphs where relationships or entire graphs become nodes.

Core Design

The Graph Lens consists of:

scopePattern: The Pattern that defines the boundary for all graph operations. Only direct elements of this pattern are considered for graph structure.
testNode: A predicate determining which direct elements are nodes. All other graph concepts (relationships, walks) derive from this single predicate.

Design Principles

**Scope-bounded operations**: All graph operations only consider direct elements of scopePattern, never descending into nested structures.

**Single predicate foundation**: Only testNode is required. All other graph predicates (relationships, walks, etc.) are derived from this.
**Context captured at construction**: If a predicate needs context, that context must be captured when the predicate is created, not during evaluation.
**Interpretation, not intrinsic**: Graph structure is not a property of Pattern itself, but an interpretation through the lens.

Categorical Interpretation

Graph Lens provides a functorial interpretation where Pattern structures are transformed into graph interpretations. The transformation Pattern → Graph interpretation is functorial in nature.

Example

>>> let graphPattern = pattern "graph" [point "a", point "b", pattern "r1" [point "a", point "b"]]
>>> let isAtomic (Pattern _ els) = null els
>>> let atomicLens = GraphLens graphPattern isAtomic
>>> nodes atomicLens
[Pattern "a" [],Pattern "b" []]

See design/graph-lens.md and specs023-graph-lensquickstart.md for comprehensive examples and usage patterns.

Synopsis

data GraphLens v = GraphLens {
- scopePattern :: Pattern v
- testNode :: Pattern v -> Bool
}
nodes :: GraphLens v -> [Pattern v]
isNode :: GraphLens v -> Pattern v -> Bool
isRelationship :: GraphLens v -> Pattern v -> Bool
relationships :: GraphLens v -> [Pattern v]
source :: GraphLens v -> Pattern v -> Maybe (Pattern v)
target :: GraphLens v -> Pattern v -> Maybe (Pattern v)
reverseRel :: Pattern v -> Pattern v
isWalk :: Eq v => GraphLens v -> Pattern v -> Bool
walks :: Eq v => GraphLens v -> [Pattern v]
walkNodes :: Eq v => GraphLens v -> Pattern v -> [Pattern v]
neighbors :: Eq v => GraphLens v -> Pattern v -> [Pattern v]
incidentRels :: Eq v => GraphLens v -> Pattern v -> [Pattern v]
degree :: Eq v => GraphLens v -> Pattern v -> Int
connectedComponents :: Ord v => GraphLens v -> [[Pattern v]]
bfs :: Ord v => GraphLens v -> Pattern v -> [Pattern v]
findPath :: Ord v => GraphLens v -> Pattern v -> Pattern v -> Maybe [Pattern v]

Graph Lens Type

data GraphLens v Source #

A Graph Lens provides an interpretive view of a Pattern as a graph structure.

The lens consists of: * scopePattern: The Pattern that defines the boundary for all graph operations. Only direct elements of this pattern are considered for graph structure. * testNode: A predicate determining which direct elements are nodes. All other graph concepts (relationships, walks) derive from this predicate.

Categorical Interpretation

Graph Lens provides a functorial interpretation where Pattern structures are transformed into graph interpretations. The transformation Pattern → Graph interpretation is functorial in nature.

Design Principles

Scope-bounded: All operations only consider direct elements of scopePattern
Single predicate foundation: Only testNode is required, all else derives
Context at construction: Predicate context captured when lens is created
Interpretation, not intrinsic: Graph structure is an interpretation, not a property of Pattern itself

Example

>>> let atomicLens = GraphLens pattern (\(Pattern _ els) -> null els)
>>> nodes atomicLens
[[a], [b], [c]]

Constructors

GraphLens
Fields scopePattern :: Pattern v The Pattern that defines the graph scope testNode :: Pattern v -> Bool Predicate determining which elements are nodes

Node Operations

nodes :: GraphLens v -> [Pattern v] Source #

Extract all nodes from the graph lens.

Nodes are direct elements of scopePattern that satisfy the testNode predicate.

Time Complexity

O(n) where n is the number of direct elements in scopePattern

Example

>>> let lens = GraphLens pattern isAtomic
>>> nodes lens
[[a], [b], [c]]

isNode :: GraphLens v -> Pattern v -> Bool Source #

Determine if a Pattern is a node according to the lens.

This is the context-aware version that uses the lens's testNode predicate. The lens parameter provides the predicate context.

Example

>>> let lens = GraphLens pattern isAtomic
>>> isNode lens (point "a")
True
>>> isNode lens (pattern "rel" [point "a", point "b"])
False

Relationship Operations

isRelationship :: GraphLens v -> Pattern v -> Bool Source #

Determine if a Pattern is a relationship according to the lens.

A relationship is a non-node pattern with exactly two node elements.

Properties

Must not be a node (does not satisfy testNode predicate)
Must have exactly two elements
Both elements must be nodes (according to the lens)

Example

>>> let lens = GraphLens pattern isAtomic
>>> let rel = pattern "knows" [point "Alice", point "Bob"]
>>> isRelationship lens rel
True

relationships :: GraphLens v -> [Pattern v] Source #

Extract all relationships from the graph lens.

Relationships are non-node patterns with exactly two node elements.

Time Complexity

O(n) where n is the number of direct elements in scopePattern

Example

>>> let lens = GraphLens pattern isAtomic
>>> relationships lens
[[knows | [Alice], [Bob]], [likes | [Bob], [Charlie]]]

source :: GraphLens v -> Pattern v -> Maybe (Pattern v) Source #

Extract the source node from a relationship.

For directed relationships, the source is the first element. Returns Nothing if the pattern is not a relationship.

Example

>>> let lens = GraphLens pattern isAtomic
>>> let rel = pattern "knows" [point "Alice", point "Bob"]
>>> source lens rel
Just (point "Alice")

target :: GraphLens v -> Pattern v -> Maybe (Pattern v) Source #

Extract the target node from a relationship.

For directed relationships, the target is the second element. Returns Nothing if the pattern is not a relationship.

Example

>>> let lens = GraphLens pattern isAtomic
>>> let rel = pattern "knows" [point "Alice", point "Bob"]
>>> target lens rel
Just (point "Bob")

reverseRel :: Pattern v -> Pattern v Source #

Reverse the direction of a relationship pattern.

Swaps the first and second elements, effectively reversing the relationship direction.

Example

>>> let rel = pattern "knows" [point "Alice", point "Bob"]
>>> reverseRel rel
pattern "knows" [point "Bob", point "Alice"]

Walk Operations

isWalk :: Eq v => GraphLens v -> Pattern v -> Bool Source #

Determine if a Pattern is a walk according to the lens.

A walk is a non-node pattern whose elements are all relationships, where consecutive relationships share nodes (target of one equals source of next).

Properties

Must not be a node (does not satisfy testNode predicate)
All elements must be relationships (according to the lens)
Consecutive relationships must be connected

Example

>>> let lens = GraphLens pattern isAtomic
>>> let walk = pattern "path" [rel1, rel2, rel3]
>>> isWalk lens walk
True

walks :: Eq v => GraphLens v -> [Pattern v] Source #

Extract all walks from the graph lens.

Walks are non-node patterns whose elements are all relationships, where consecutive relationships share nodes.

Time Complexity

O(n) where n is the number of direct elements in scopePattern

Example

>>> let lens = GraphLens pattern isAtomic
>>> walks lens
[[path | [rel1], [rel2], [rel3]]]

walkNodes :: Eq v => GraphLens v -> Pattern v -> [Pattern v] Source #

Extract nodes from a walk in traversal order.

Returns the source of the first relationship, followed by the targets of subsequent relationships. Returns empty list if the pattern is not a valid walk.

Example

>>> let lens = GraphLens pattern isAtomic
>>> let walk = pattern "path" [rel1, rel2]
>>> walkNodes lens walk
[pattern "A", pattern "B", pattern "C"]

Navigation Operations

neighbors :: Eq v => GraphLens v -> Pattern v -> [Pattern v] Source #

Find all neighbors of a node.

Neighbors are nodes connected to the given node via relationships (either as source or target).

Time Complexity

O(r) where r is the number of relationships in the graph

Example

>>> let lens = GraphLens pattern isAtomic
>>> neighbors lens (point "Alice")
[point "Bob", pattern "Charlie"]

incidentRels :: Eq v => GraphLens v -> Pattern v -> [Pattern v] Source #

Find all relationships involving a node.

Returns relationships where the node is either source or target.

Time Complexity

O(r) where r is the number of relationships in the graph

Example

>>> let lens = GraphLens pattern isAtomic
>>> incidentRels lens (point "Alice")
[[knows | [Alice], [Bob]], [likes | [Charlie], [Alice]]]

degree :: Eq v => GraphLens v -> Pattern v -> Int Source #

Compute the degree of a node (number of incident relationships).

The degree is the count of relationships where the node is either source or target.

Time Complexity

O(r) where r is the number of relationships in the graph

Example

>>> let lens = GraphLens pattern isAtomic
>>> degree lens (point "Alice")
3

Graph Analysis Operations

connectedComponents :: Ord v => GraphLens v -> [[Pattern v]] Source #

Find all connected components in the graph.

A connected component is a set of nodes that are reachable from each other via relationships. Returns a list of lists, where each inner list represents a component.

Time Complexity

O(n + r) where n is number of nodes and r is number of relationships

Example

>>> let lens = GraphLens pattern isAtomic
>>> connectedComponents lens
[[pattern "A", pattern "B", pattern "C"], [pattern "D", pattern "E"]]

bfs :: Ord v => GraphLens v -> Pattern v -> [Pattern v] Source #

Perform breadth-first search from a starting node.

Returns all nodes reachable from the starting node via relationships.

Time Complexity

O(n + r) where n is number of nodes and r is number of relationships

Example

>>> let lens = GraphLens pattern isAtomic
>>> bfs lens (point "Alice")
[point "Alice", point "Bob", pattern "Charlie"]

findPath :: Ord v => GraphLens v -> Pattern v -> Pattern v -> Maybe [Pattern v] Source #

Find a path between two nodes if one exists.

Returns Just [nodes] if a path exists, Nothing otherwise. The path is a sequence of nodes connecting start to end.

Time Complexity

O(n + r) where n is number of nodes and r is number of relationships

Example

>>> let lens = GraphLens pattern isAtomic
>>> findPath lens (point "Alice") (pattern "Charlie")
Just [point "Alice", point "Bob", pattern "Charlie"]