stew/dogs

data structures for pure functional programming in scala

Mike (stew) O'Connor

@stew

got it

and sorry, please bear with me, I'm doing a gajilion things at once, haha

I think that what I'm really hoping is that you have some magical little toy example that is not going to ask someone to go off reading a whole bunch of stuff before they can answer the question "when would I use this" or probably more specifically "can I use this to solve the thing I'm doing right now"

kwim

btw, are you currently actually using this datastructure to do real stuff?

Pablo Francisco Pérez Hidalgo

@pfcoperez

Hi @stew , I perfectly understand how difficult is to maintain these projects, keep working and have some time to sleep ;-)

In relation to the toy, I have a couple of examples within DailyAlgorithm, they are quite self-contained: One is the Kruskal algorithm, the other is an algorithm to find the connected components in a graph. One or both these examples could be isolated into a single project which could use Scala.js to generate a live animation in the browser.
I've done that before, for other algorithms, and it is quite illustrative.

I don't currently use this structure in any project but I've used it to solve some Hackerrank and Codility problems.
I don't think it would be difficult to find projects using it, specially if they require use some sort of clusterization, net optimization, ... I could look around.

C++'s Boost library does provide Disjoint Sets: http://www.boost.org/doc/libs/1_64_0/libs/disjoint_sets/disjoint_sets.html

Pablo Francisco Pérez Hidalgo

@pfcoperez

Hi @stew , At the end of the day it wasn't clear to me if any of the two examples I mentioned matched you idea of a toy to show when you should use Disjoint Sets.

Some simpler examples come to my mind:

Having a list of 1 to 1 friendship connections, find groups of friends is one.

Is this the kind of thing you've in mind?

Pablo Francisco Pérez Hidalgo

@pfcoperez

Hi @stew , did you have the opportunity to take a look at the PR aimed to introduce Disjoint Sets in Dogs? I understand if you couldn't squeeze some time to check it, I was just wondering whether you'd like to change something or get better toy examples examples . It is fine for me if you just couldn't take the time to review it.

Mike (stew) O'Connor

@stew

@pfcoperez I apologize. I finished up my last job on friday, I'm unemployed, i guess as of today. I'm going to start catching up on stuff

I want to get your stuff merged

Pablo Francisco Pérez Hidalgo

@pfcoperez

@stew No need to apologize at all! It is too good you can squeeze any time at all.

I was thinking to remove some nested for-notattions by applying Monad transformers however, as Dogs' collections doesn't come with their transformers counterparts (OptionT, ListT...)

I didn't attempt it. I didn't either to flood the channel with more messages nor the repo with more issues

But I think I'd be nice to add those monad transformers for Dogs' collections, is it something you'd be interested in? I am willing to implement them

Mike (stew) O'Connor

@stew

@pfcoperez does it make sense that the members of the disjoint sets and the labels are the same type or not?

Pablo Francisco Pérez Hidalgo

@pfcoperez

Hi @stew , they should be the same type as labels are representative elements of a disjoint set

Mike (stew) O'Connor

@stew

oh, i see, the label is the element and the entries are paths to other elements

Pablo Francisco Pérez Hidalgo

@pfcoperez

exactly

Pablo Francisco Pérez Hidalgo

@pfcoperez

The "Concept" section of this http://orionsword.no-ip.org/blog/wordpress/?p=246 post have some graphic examples of the implemented optimizations

Mike (stew) O'Connor

@stew

why does find return a new DisjointSets?

Pablo Francisco Pérez Hidalgo

@pfcoperez

Because as it follows the path it changes the visited nodes parent to the root element, that is , the label

Mike (stew) O'Connor

@stew

why would I want that?

Pablo Francisco Pérez Hidalgo

@pfcoperez

That way, next look ups over the returned DS will be O(1)

That's what is called "path compression"

Mike (stew) O'Connor

@stew

this is only used for toSets, which does this for every label, right?

Pablo Francisco Pérez Hidalgo

@pfcoperez

toSets is a helper operation which could be used to get a collection of sets format of the information. find can be used by client code to check , for example if to elements have the same label

toSets is an expensive operation which can be useful to get an easy to use snapshot

this is path compression:

http://orionsword.no-ip.org/blog/wordpress/wp-content/uploads/2012/12/DSets_path_compression1.png

Mike (stew) O'Connor

@stew

Pablo Francisco Pérez Hidalgo

@pfcoperez

I'm leaving the chat room from now (00:40 here in Spain) but I'll answer any question you might have in the morning. Thanks for taking the time to review this .

Mike (stew) O'Connor

@stew

sounds good

so sorry I've sat on this for so long

i'm making some tweaks and I'll have it merged soon

Pablo Francisco Pérez Hidalgo

@pfcoperez

great, that's awesome! No worries at all :smile:

Greg Pfeil

@sellout

@stew How do you feel about me adding a dogs-monocle project/artifact?

Pablo Francisco Pérez Hidalgo

@pfcoperez

Hi @stew , did you find something you don't like in the Disjoint sets implementation? I am open to any suggestion you may have

Greg Pfeil

@sellout

cough @stew – dogs-monocle, do you want it?

Mike (stew) O'Connor

@stew

@sellout sure!

Greg Pfeil

@sellout

👍🏾

Pablo Francisco Pérez Hidalgo

@pfcoperez

Thanks for the merge @stew !

Are you open to more contributions?

Aarsh Shah

@aarshkshah1992

Hi everyone

I am a Scala developer and really want to contribute to DOgs

Looks like a fantastic library and is really aligned to my interests

Is there a wiki / write-up on how to start contributing and bugs/open issues I can work on as a first step ?

etienne

@crakjie

Hi. I was watching the documentation. I think you should remove the warning from the console output, this warn are not helping readability.

Adrian Legaspi

@akilegaspi

Hi everyone, I was wondering how I could make a contribution; I have some ideas up my sleeve like creating concurrent data structures due to the existence of cats-effect and the need for concurrent data structures for some applications.

Any inputs would be nice :)

scalway

@scalway

on website in all examples there is lot of warnings like that:

<console>:10: warning: Unused import
       import dogs._
                   ^
<console>:13: warning: Unused import
       import cats._
                   ^
<console>:19: warning: Unused import
       import dogs.syntax.all._
                              ^

eg: https://stew.github.io/dogs/binaryheap.html

Where communities thrive

People

Repo info

Activity