Become a member
to unlock all features

Level Up!

Access all courses & lessons on egghead today and lock-in your price for life.


    Find the intersection of sets with Semigroups

    Brian LonsdorfBrian Lonsdorf

    We use semigroups to find the intersection of sets, then expand that to work on as many artists as we'd like. Finally, we use foldable to show a pair of intersection and sum to shed more light on the final result set.



    Become a Member to view code

    You must be a Member to view code

    Access all courses and lessons, track your progress, gain confidence and expertise.

    Become a Member
    and unlock code for this lesson




    we left off with two related lists of artists. When we call Oasis and Blur here, we get the list of artists related to Oasis and the list of artists related to Blur.

    Now, we'd like to take this little piece here and expand it to the rest of our program, and really try to find the commonality between these two lists. We say we're going to combine this list with this list into a unique list.

    If we look at this a little closer, we could say if I have a list of one, two, three, four. This is Ben's. Then we have three, four, five. We want the same elements to cross, which would be three and four.

    There we go into the results. These would be the similar elements in both arrays just like similar artists in these two arrays. What we're looking at here is actually set into section, which is very nicely expressed in semi-group.

    We can write ourselves a little intersection semi-group. We know the laws hold up front because of set theory. However, if you didn't, you could always check like we did before.

    Let's go ahead and define this up here so it's out of the way. We have an intersection. It takes an array. We have the Xs and concat. We want to concat it to...we'll just do structure and assign it to Ys here. This is our basic template.

    We have to expose our axis to get it out of the other object there. Now, we can say if our Xs filter out, if we have any X that's included in the Ys or some Y is equal to X, then that will keep that X. This should work just fine. It should just go through the Xs and find any Y that matches.

    There we go. We can hide a complexity in here, because this is the low level interface that most people won't look at. We could put for loops and make it really optimizes, but we decided to just stick with simple functions here.

    Let's go ahead and take the semi group and put it to use. What we have here is a bunch of names and a bunch of names in a list. Let pull this whole function into it's own little deal. We'll call it how this read. We would say task of artist intersection. That's what we want.

    We'll say artist intersection must be carried because of applicatives here. What we want to do here to give ourselves some room, we could take each of these, just pop them in an intersection, and then concat that with the intersection of the others. Once you combine two intersections, you get a third intersection. We'll want to just pop them out with .Xs off the intersection here.

    Let's give this a shot and see if it works. There it is, our intersection of these two lists here. That's terrific. Let's see if we can if we can do it with diesels and hollies. We get the birds.

    Now, let's see if we can expand this a little bit into three bands. Let's say if I want Oasis, Blur, and Radiohead, I want the intersection of all of those. In order to do this, let's get rid of this applicative work though.

    Instead of three bands, let's just take as many as we want. We'll go ahead and bring in list from immutable EXT. We'll go ahead and install our MPMs dollar mutable extensions, XD, and then mutable. We'll save that.

    While that's going, we'll go over here. Let's rethink this. Instead of taking two name and using applicatives, let's go ahead and take in a list of names. We'll just pop that right into a list. Then, get rid of this. We'll just go ahead and, if we were to map a ridge name and get related, we would end up with a list of tasks.

    We want to flip this around and make a traverse task related there. Now, we have a task of lists. Then we simply map over that to get the artist into session. Of course, this is still in the curried applicative form here. We'll just take our roles.

    Instead of using this semi-group concat, we'll just go ahead and fold map it. We'll take our elves and we'll fold map intersection of that and grab the Xs out.

    Notice, I'm not using the empty value. If I put an intersection of an empty list here to get the empty value start, this would not intersect with anything else. We're going to rely on the intersection not being empty there, or these roles not being empty.

    Let's see if this takes in these names and gets the intersection of all three of these. We'll try Oasis, Blur, and Radiohead. That's Pulp apparently.

    This a little strange just to get that out. Why don't we go ahead and do one last thing? We'll pull in a pair in sum from our little monoid list here. The reason we like to do this is so that we can try to cram more information in here while we fold map.

    Instead of just an intersection, if we remember any pair is also a semi-group, let's go ahead and expand this little function here to put our X in there. We'll put this whole thing in a pair.

    Now that it's in a pair, we could put the sum in, as well, and take the length of the results. Now, we can see how many we're comparing while we get the intersection. It all just works with this fold map and interfaces. Of course, we're not getting another intersection out, we don't have Xs anymore. We get the pair out here.

    Let's go ahead and, after it's done, call two list on our pair because there is a natural transformation from our pair to a list. Let's go ahead and see if this does the trick. Run all three. There we go. We are comparing 60 and we end up with just Pulp out of all those 60 values.

    We can make this a little nicer just to finish this up. We could do a little...a pair is a functor. We can actually call bi-map, which is a bi-functor to run on both values. That way, we can say, "Here's two functions. Get me the Xs off the first, and get me the X out of the second from the sum."

    That way, we have a nice little packaged up result, Pulp, in 60. If we maybe look at Oasis and Beatles, see if there's anything there, we got 40 but we got nothing.

    Hope you found this useful. Off you go to go functional program in the real world.