Safe Haskell	None
Language	GHC2024

Circuit.Diagram.Hyper

Description

Hypergraph normal form for the drawing-level hyper fragment of SDiagram (SWire, SSpider, multi-port SBox, SBeside, SThenD, SSwap).

A diagram is interpreted as port connectivity: every node port and every boundary port is a port reference, and a union-find over those references quotients them into wire classes. Spiders contribute no node — they simply merge the classes of all their ports, so spider fusion (and hence the bialgebra and spider laws) is automatic, and diagrams that differ only in tree shape normalise to the same value. Constructors outside the hyper fragment (cups, caps, unitors, …) are treated as opaque nodes with their natural port arities.

This is not a full graph-isomorphism check: node ports are keyed by box label, so two boxes carrying the same label are interchangeable. That is exact for the oracle suite and cheap; revisit if unlabelled node isomorphism ever matters.

Synopsis

data HyperGraph = HyperGraph {
- hgInArity :: Int
- hgOutArity :: Int
- hgNodes :: [HyperNode]
- hgWires :: [Wire]
}
data HyperNode = HyperNode {
- hnLabel :: String
- hnInArity :: Int
- hnOutArity :: Int
}
data Wire = Wire {
- wBoundary :: [BoundaryEnd]
- wPorts :: [PortEnd]
}
data BoundaryEnd
- = InB Int
- | OutB Int
data PortEnd = PortEnd String PortDir Int
data PortDir
- = In
- | Out
normalise :: SDiagram -> HyperGraph
hyperEquiv :: SDiagram -> SDiagram -> Bool
arity :: SDiagram -> (Int, Int)

Documentation

data HyperGraph Source #

A diagram as port connectivity: boundary arities, a sorted multiset of nodes, and the wires (equivalence classes of ports).

Constructors

HyperGraph
Fields hgInArity :: Int Number of input (left boundary) ports. hgOutArity :: Int Number of output (right boundary) ports. hgNodes :: [HyperNode] Sorted nodes. hgWires :: [Wire] Sorted wires.

Instances

Instances details

Eq HyperGraph Source #
Instance details Defined in Circuit.Diagram.Hyper Methods (==) :: HyperGraph -> HyperGraph -> Bool # (/=) :: HyperGraph -> HyperGraph -> Bool #
Show HyperGraph Source #
Instance details Defined in Circuit.Diagram.Hyper Methods showsPrec :: Int -> HyperGraph -> ShowS # show :: HyperGraph -> String # showList :: [HyperGraph] -> ShowS #

data HyperNode Source #

A box (or opaque constructor) with its port arities.

Constructors

HyperNode
Fields hnLabel :: String hnInArity :: Int hnOutArity :: Int

Instances

Instances details

Eq HyperNode Source #
Instance details Defined in Circuit.Diagram.Hyper Methods (==) :: HyperNode -> HyperNode -> Bool # (/=) :: HyperNode -> HyperNode -> Bool #
Ord HyperNode Source #
Instance details Defined in Circuit.Diagram.Hyper Methods compare :: HyperNode -> HyperNode -> Ordering # (<) :: HyperNode -> HyperNode -> Bool # (<=) :: HyperNode -> HyperNode -> Bool # (>) :: HyperNode -> HyperNode -> Bool # (>=) :: HyperNode -> HyperNode -> Bool # max :: HyperNode -> HyperNode -> HyperNode # min :: HyperNode -> HyperNode -> HyperNode #
Show HyperNode Source #
Instance details Defined in Circuit.Diagram.Hyper Methods showsPrec :: Int -> HyperNode -> ShowS # show :: HyperNode -> String # showList :: [HyperNode] -> ShowS #

data Wire Source #

One wire class: the boundary ends and node ports it connects, each sorted.

Constructors

Wire
Fields wBoundary :: [BoundaryEnd] wPorts :: [PortEnd]

Instances

Instances details

Eq Wire Source #
Instance details Defined in Circuit.Diagram.Hyper Methods (==) :: Wire -> Wire -> Bool # (/=) :: Wire -> Wire -> Bool #
Ord Wire Source #
Instance details Defined in Circuit.Diagram.Hyper Methods compare :: Wire -> Wire -> Ordering # (<) :: Wire -> Wire -> Bool # (<=) :: Wire -> Wire -> Bool # (>) :: Wire -> Wire -> Bool # (>=) :: Wire -> Wire -> Bool # max :: Wire -> Wire -> Wire # min :: Wire -> Wire -> Wire #
Show Wire Source #
Instance details Defined in Circuit.Diagram.Hyper Methods showsPrec :: Int -> Wire -> ShowS # show :: Wire -> String # showList :: [Wire] -> ShowS #

data BoundaryEnd Source #

A diagram boundary port.

Constructors

InB Int	Input port (left boundary) at the given index.
OutB Int	Output port (right boundary) at the given index.

Instances

Instances details

Eq BoundaryEnd Source #
Instance details Defined in Circuit.Diagram.Hyper Methods (==) :: BoundaryEnd -> BoundaryEnd -> Bool # (/=) :: BoundaryEnd -> BoundaryEnd -> Bool #
Ord BoundaryEnd Source #
Instance details Defined in Circuit.Diagram.Hyper Methods compare :: BoundaryEnd -> BoundaryEnd -> Ordering # (<) :: BoundaryEnd -> BoundaryEnd -> Bool # (<=) :: BoundaryEnd -> BoundaryEnd -> Bool # (>) :: BoundaryEnd -> BoundaryEnd -> Bool # (>=) :: BoundaryEnd -> BoundaryEnd -> Bool # max :: BoundaryEnd -> BoundaryEnd -> BoundaryEnd # min :: BoundaryEnd -> BoundaryEnd -> BoundaryEnd #
Show BoundaryEnd Source #
Instance details Defined in Circuit.Diagram.Hyper Methods showsPrec :: Int -> BoundaryEnd -> ShowS # show :: BoundaryEnd -> String # showList :: [BoundaryEnd] -> ShowS #

data PortEnd Source #

A node port: box label, direction and port index.

Constructors

PortEnd String PortDir Int

Instances

Instances details

Eq PortEnd Source #
Instance details Defined in Circuit.Diagram.Hyper Methods (==) :: PortEnd -> PortEnd -> Bool # (/=) :: PortEnd -> PortEnd -> Bool #
Ord PortEnd Source #
Instance details Defined in Circuit.Diagram.Hyper Methods compare :: PortEnd -> PortEnd -> Ordering # (<) :: PortEnd -> PortEnd -> Bool # (<=) :: PortEnd -> PortEnd -> Bool # (>) :: PortEnd -> PortEnd -> Bool # (>=) :: PortEnd -> PortEnd -> Bool # max :: PortEnd -> PortEnd -> PortEnd # min :: PortEnd -> PortEnd -> PortEnd #
Show PortEnd Source #
Instance details Defined in Circuit.Diagram.Hyper Methods showsPrec :: Int -> PortEnd -> ShowS # show :: PortEnd -> String # showList :: [PortEnd] -> ShowS #

data PortDir Source #

Whether a node port is an input or an output.

Constructors

In
Out

Instances

Instances details

Eq PortDir Source #
Instance details Defined in Circuit.Diagram.Hyper Methods (==) :: PortDir -> PortDir -> Bool # (/=) :: PortDir -> PortDir -> Bool #
Ord PortDir Source #
Instance details Defined in Circuit.Diagram.Hyper Methods compare :: PortDir -> PortDir -> Ordering # (<) :: PortDir -> PortDir -> Bool # (<=) :: PortDir -> PortDir -> Bool # (>) :: PortDir -> PortDir -> Bool # (>=) :: PortDir -> PortDir -> Bool # max :: PortDir -> PortDir -> PortDir # min :: PortDir -> PortDir -> PortDir #
Show PortDir Source #
Instance details Defined in Circuit.Diagram.Hyper Methods showsPrec :: Int -> PortDir -> ShowS # show :: PortDir -> String # showList :: [PortDir] -> ShowS #

normalise :: SDiagram -> HyperGraph Source #

Interpret a diagram as its hypergraph normal form.

Assumes composable diagrams (SThenD zips the inner ports and drops any excess): the drawing syntax is untyped, so ill-formed composites degrade to dangling ports rather than an error.

STurn is involutive and reverses composition order:

>>> hyperEquiv (STurn (STurn (SBox "f" 1 1))) (SBox "f" 1 1)
True
>>> hyperEquiv (STurn (SThenD (SBox "f" 1 1) (SBox "g" 1 1))) (SThenD (STurn (SBox "g" 1 1)) (STurn (SBox "f" 1 1)))
True

>>> putStr (toMermaid (STurn (SBox "f" 1 1)))
flowchart LR
  in0(["in 0"])
  out0(["out 0"])
  n0["f†"]
  in0 --> n0
  n0 --> out0

hyperEquiv :: SDiagram -> SDiagram -> Bool Source #

Structural equality of diagrams up to hypergraph connectivity.

arity :: SDiagram -> (Int, Int) Source #

Boundary port counts of a diagram: (inputs, outputs). The unit of a unitor carries no wire, so unitors are 1 -> 1.