NonEmpty for CyclicSCC about containers HOT 11 CLOSED

Or even go for

data SCC vertex = SCC vertex [vertex]

and AcyclicSCC / CyclicSCC become pattern synonyms for backward compatibility.

from containers.

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.

from containers.

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 #-}

from containers.

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.

from containers.

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

from containers.

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

from containers.

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

from containers.

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

from containers.

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 [].

from containers.

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

from containers.

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.

from containers.