These are chat archives for got-lambda/expression

1st
Sep 2018
jolod
@jolod
Sep 01 2018 19:08
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?
Pierre Krafft
@Zalastax
Sep 01 2018 19:23
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?
jolod
@jolod
Sep 01 2018 21:10
@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).
Pierre Krafft
@Zalastax
Sep 01 2018 21:13
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
jolod
@jolod
Sep 01 2018 21:14
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.
Pierre Krafft
@Zalastax
Sep 01 2018 21:16
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?
jolod
@jolod
Sep 01 2018 21:21
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; }
jolod
@jolod
Sep 01 2018 21:26
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.
jolod
@jolod
Sep 01 2018 21:31
(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.
Pierre Krafft
@Zalastax
Sep 01 2018 21:34
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
jolod
@jolod
Sep 01 2018 21:36
Btw, and this is totally related, do you have a good name for a function with type (a -> b) -> Foo a -> b?
Pierre Krafft
@Zalastax
Sep 01 2018 21:40
fromMap perhaps?
It looks like fromFoo . fmap
jolod
@jolod
Sep 01 2018 21:44
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.
Pierre Krafft
@Zalastax
Sep 01 2018 21:55
I'd expect you to have 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
jolod
@jolod
Sep 01 2018 22:23
@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. :-)
jolod
@jolod
Sep 01 2018 22:28
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.
jolod
@jolod
Sep 01 2018 22:36
But I don't know. For functions with one more arguments it becomes a bit of a tie.