NonEmpty for CyclicSCC

[Bodigrim]

containers/containers/src/Data/Graph.hs

Lines 146 to 149 in 48196fb

	data SCC vertex = AcyclicSCC vertex -- ^ A single vertex that is not
	-- in any cycle.
	| CyclicSCC [vertex] -- ^ A maximal set of mutually
	-- reachable vertices.

How about changing this to CyclicSCC (NonEmpty vertex)? This could shave a number of unsafe Data.List.head in GHC and other compilers.

Not sure about backward compatibility / migration schedule, probably a pattern synonym can help to ease the breakage.

[Bodigrim]

Or even go for

data SCC vertex = SCC vertex [vertex]

and AcyclicSCC / CyclicSCC become pattern synonyms for backward compatibility.

[treeowl]

Yes, let's do something of this sort. Your second representation doesn't seem to distinguish properly between vertices with no edges and ones with a single edge to themselves.

import Data.Graph

main :: IO ()
main =  do
  print $ stronglyConnComp [((), (), [()])]
  print $ stronglyConnComp [((), (), [])]

This gives

[CyclicSCC [()]]
[AcyclicSCC ()]

As I understand it, your SCC would represent these two the same.

[Bodigrim]

Your second representation doesn't seem to distinguish properly between vertices with no edges and ones with a single edge to themselves.

Ah, excellent point.

How about this? Any better naming than CyclicSCC'?

data SCC vertex = AcyclicSCC vertex
                | CyclicSCC' (NonEmpty vertex)

pattern CyclicSCC :: [vertex] -> SCC vertex
pattern CyclicSCC xs <- CyclicSCC' (NE.toList -> xs) where
  CyclicSCC xs = CyclicSCC' (NE.fromList xs)

{-# COMPLETE AcyclicSCC, CyclicSCC #-}

[treeowl]

I must admit to some trepidation about committing to NonEmpty given the current lack of a plan for improving its laziness story. If we do use it, I imagine it should be strict and unpacked.

[Bodigrim]

Do you mean CyclicSCC' !vertex ![vertex]?

[treeowl]

I meant if you want NonEmpty it should probably be {-# UNPACK #-} !(NonEmpty vertex). But unpacking by hand wouldn't be unreasonable either.

[Bodigrim]

{-# UNPACK #-} and a bang are more readable, I'd rather keep NonEmpty. Shall I prepare a PR? @meooow25 any comments?

[treeowl]

I'd like to see how this affects the code, yeah.

[meooow25]

Can we maybe skip introducing the partial CyclicSCC -> CyclicSCC' pattern? It's unlikely someone would be making their own SCCs. And even with the pattern it's a breaking change if they do CyclicSCC [].

[treeowl]

@meooow25 , we can just make it unidirectional, right?

[meooow25]

Yes, that's what I meant, should have stated explicitly.
Also this is only a suggestion, it comes down to whether we really don't want to break some code out there that is constructing CyclicSCCs and always with non-empty lists.