The online hangout for Göteborg Functional Programming Group and everybody interested.

OK, so the wrong crowd, but if you had to solve the following problem using OO, how would you approach it? Assume I have a graph class (vertices and directed edges) that implements a bunch of behaviors, but I also frequently need to do some of those operations on the transpose/inverse of the graph (the direction of the edges is reversed) so I want transposition to be an O(1) operation in time. I want to be able to reuse the graph class, but I would also want to not hardcode a specific class, because maybe I find a better class for working with graphs. Any suggestions?

My suggestion would be to not write it in an OO style 😝 if you make it data-centric you can keep an association list [(VertexID, VertexID)] which you treat as [(From, To)] or [(To, From)] depending on the direction of the graph. Perhaps you can still make the graps/vertices/edges API feel OO-like?

@Zalastax I have a FP solution to this, but I'm a poor at representing OO style, so I wanted to learn how you'd do it in OO to compare and contrast.

@Zalastax Regarding representation, having a list of edges (could be) good for transposing, but you pay for that in every (?) other operation.

@Zalastax My solution is two just use two

`Map a (Set a)`

where one is the transpose.
But as I said, I don't want to be tied to a particular representation (but I have no problem using double memory).

Yeah, probably. Graphs are tricky bastards so you really need to think about what operations you need to be quick (as far as I know).

I really think data centric is the way to go though but I detest data hiding so I'm quite biased

So there are already modules that implement graph operations, the challenge is to add this property of maintaining a transpose as well.

Yeah, so my question comes from that I don't know a good way to do this in OO. But rather than concluding that an OO solution is bad, I asked for suggestions.

Alright! I'm in the same camp as you then and hope someone could show us the way

I guess the OOP way is to have a node with an edge list?

That's not really the problem in focus here though; what I'm after is reusing an existing class (for all your graph needs, like path finding, topological sorting, transitive closure, etc) and still have fast transpose.

Or rather, immediately available operations on transpose. So reverse transitive closure, for instance.

My approach would be to, assuming the graph class has a copy method, have something like this

`init(graph) { this.graph = graph.copy(); this.transpose = construct_transpose_from_graph(graph) }`

(or use

`.transpose()`

if that was avilable)
then my class'

`transpose()`

would just be `transpose() { graph = this.graph; this.graph = this.transpose; this.transpose = graph; }`

`graph`

and `transpose`

would have to be private in order to assure that neither is updated so that they no longer are each other's transpose.
Then I would require that the reused graph class implements an interface with all the methods that I need. Obviously, I would have to write methods for adding and removing vertices and edges which would updated the internal graph and the internal transpose accordingly. Then I would also have to delegate all behaviors I needed to

`this.graph`

.
If a behavior is added in wrapped graph class, I need to add that method to my class as well in order to be able to utilize it.

(And if the wrapped graph class has no copy method, that's a show stopper, I think.)

Or, no, I could write that myself, I assume.

... if it has an

`allVertices()`

and `edgesFrom(vertex)`

methods.
which I assume when creating the transpose, so that's OK.

Yes, that sounds reasonable - just wrap each method of the underlying library and make it update both versions of the graph. The alternative is that storage is abstracted away (so you could back it by a single graph or both the graph and its transpose) and I'm not sure if that would be nice to work with

Btw, and this is totally related, do you have a good name for a function with type

`(a -> b) -> Foo a -> b`

?
It looks like

`fromFoo . fmap`

Yeah. It isn't though. :-) It's closer to composition of the first argument with

`extract`

(only it's not extract).
I want to call it lift, but typically as I understand it, lifting is just another word for fmapping.

I'd expect you to have

Lifting is basically fmapping, e.g.

`extract . fmap === & . extract`

;) (if extract is the same thing as fromJust etc.)Lifting is basically fmapping, e.g.

`liftFoo2 :: (a -> b -> c) -> Foo a -> Foo b -> Foo c`

. How come you want to combine lift/fmap and extract into a named function?
The reason why you want to combine them might reveal a name from your domain that you could use is my reasoning

@Zalastax Because I like the way it reads. To me, it's more declarative. I'm changing a function, instead of unpacking a value and apply a function to that value.

"declarative" for lack of a better word.

So, in this case, it could be

`notReallyLift Graph.isEmpty`

and that will work on my data type which maintains the transpose. The alternative would be `extract >>> Graph.isEmpty`

, which, just doesn't look as nice to me. :-)
Fully applied, it looks like

`notReallyLift Graph.isEmpty g`

, compared to `Graph.isEmpty $ extract g`

or `extract >>> Graph.isEmpty $ g`

. I really prefer the first.
But I don't know. For functions with one more arguments it becomes a bit of a tie.