Graph

Your graph is defined by a type a and a function that give the next element in the graph, if any. isCycle tells you wether the graph is a cycle.

Cycle detection

isCycle : (a -> Maybe a) -> a -> Bool

Takes a function that gives the possible next element in the graph and the first element, returns True if the graph is a cycle

Example usage:

Here is a function that takes an integer and gives the next integer. The cycle loops for numbers above 5 and not for negative ones.

next : Int -> Maybe Int
next n = if n > 10 then Just 5 else if n == 0 then Nothing else Just (n + 1)

We can check that the graph is a cycle if we start from above 0:

isCycle next 2
--> True


isCycle next -5
--> False

endOrCycle : (a -> Maybe a) -> a -> Result a a

Takes a function that gives the possible next element in the graph and the first element, and returns:

- (Ok x) if x is the output of the path
- (Err x) if x is the entry of a cycle

Example usage:

Here is a function that takes an integer and gives the next integer. The cycle loops for numbers above 5 and not for negative ones.

next : Int -> Maybe Int
next n = if n > 10 then Just 5 else if n == 0 then Nothing else Just (n + 1)

The output of the graph is at number 0:

endOrCycle next -5
--> Ok 0

There is a cycle, we can find the entry point of the cycle:

endOrCycle next 2
--> Err 5