Please add Traversals

[tomjaguarpaw]

Could we please have some traversals (lenses)? This is the entire implementation. It doesn't depend on anything outside FGL and base.

I'm happy to submit this as a PR if you guarantee you'll accept it.

module Data.Graph.Inductive.Lens
       ( traverseNodes
       , traverseEdges ) where

import           Control.Applicative        ((<$>), (<*>), pure, Applicative)
import qualified Data.Graph.Inductive.Graph as FGL
import           Data.Graph.Inductive.Graph ((&))
import qualified Data.Traversable           as T

-- | Walk all nodes in the graph in the order they were created
traverseNodes :: (FGL.DynGraph gr, Applicative f)
              => (a -> f a')
              -> gr a b
              -> f (gr a' b)
traverseNodes f = FGL.ufold (mergeNode f) (pure FGL.empty)

mergeNode :: (Applicative f, FGL.DynGraph gr)
          => (a -> f a')
          -> FGL.Context a b
          -> f (gr a' b)
          -> f (gr a' b)
mergeNode f (adj, node, a, adj') g =
  (\a' g' -> (adj, node, a', adj') & g') <$> f a <*> g

-- | Walk all edges in the graph in the order they were created
traverseEdges :: (FGL.DynGraph gr, Applicative f)
              => (b -> f b')
              -> gr a b
              -> f (gr a b')
traverseEdges f g = FGL.ufold (mergeEdge f) (pure FGL.empty) g

mergeEdge :: (Applicative f, FGL.DynGraph gr)
          => (b -> f b')
          -> FGL.Context a b
          -> f (gr a b')
          -> f (gr a b')
mergeEdge f (adj, node, a, adj') g =
  (\adj1 g' adj1' -> (adj1, node, a, adj1') & g')
      <$> (T.traverse . _1) f adj
      <*> g
      <*> (T.traverse . _1) f adj'

_1 :: Functor f => (a -> f a') -> (a, b) -> f (a', b)
_1 f (a, b) = (\a' -> (a', b)) <$> f a

[ivan-m]

I'll have a think about this.

I personally don't use lenses, so I'm not sure how useful these functions would be. Can you please provide some examples of how they would be used? (Especially as I'm not sure what the performance of these functions would be like with the Applicative usage.)

[tomjaguarpaw]

I shouldn't have mentioned the word "lens", it's a red herring. traverseEdges is a Traversable instance for gr a and traverseNodes is a Traversable instance for gr _ b (with the caveat that the type arguments need to be shuffled around). They are generalizations of nmap and emap.

As for examples of how they'd be used, they would be used the same as any other Traversable instance in the Haskell ecosystem, i.e. very widely and to great advantage!

[ivan-m]

I can add something like this in (probably called nmapA and emapA or some such); but without the associated Traversable instance + associated functions (which I won't add in due to the the * -> * -> * nature of graphs meaning it will only apply to edges) I don't think they'd be as useful as you're suggesting (I'm willing to be proven wrong however).

[tomjaguarpaw]

That would be great. I guarantee that you are wrong :) I'm already using these functions to decorate graphs with SBV variables.

[expipiplus1]

It might also be worth considering adding an instance for Bitraversable for the concrete data types in fgl. I came here looking for bisequenceA for graphs.

[ivan-m]

@expipiplus1 is Bitraversable in base? Since FGL is a Platform library I don't want to add any extra dependencies if possible.

[tomjaguarpaw]

@expipiplus1 Do you really want a Bitraversable instance rather than just a function which does the same job?

[expipiplus1]

@ivan-m no, it's part of the bifunctors package.

@tomjaguarpaw Either would do.

[ivan-m]

OK, I'll look into adding an instance for Bifunctor (for newer versions of base) and functions implementing Bitraversable (but not actual instances until/unless bifunctors gets added to the Haskell Platform).

[tomjaguarpaw]

On Fri, May 27, 2016 at 04:30:18AM -0700, Ivan Lazar Miljenovic wrote:

OK, I'll look into adding an instance for Bifunctor (for newer versions of base) and functions implementing Bitraversable (but not actual instances until/unless bifunctors gets added to the Haskell Platform).

That's great, thanks!

[ivan-m]

OK, I'm adding the Bifunctor instance for base >= 4.8.0.0, but I won't be adding any Bitraversable-like functions as I'm not sure how much sense they make.

The problem is that the traversable functions are all about traversing (strangely enough)... but in which order? Unless it was something of questionable nature like "traverse in ascending order of the neighbour's node IDs" (and even then there's the question of multiple edges and loops), there's no real sensible way of doing it.

The closest I can think of is to have a BFS traversal and a DFS traversal, but even then I question their validity.