SML set intersection using map, foldr, or foldl functions

Question

I am working on a SML programming assingment for class and stuck on a question. The question is: "Write an ML function that uses map, foldr, or foldl to compute the intersection of a nonempty list of sets.Here you may assume that sets are denoted as lists. For this problem, you may use auxilary named functions (e.g., isMember). Hint: A nonempty list of sets contains at least one set."

This is what I have so far can anyone point me in the right direction I am fairly new to SML?

fun member(x,[]) = false
|   member(x,L) =
        if x=hd(L) then true
        else member(x,tl(L));

fun intersect(L1,L2) = if tl(L1) = [] then L1 
else if member(hd(L1),L2) = true then L1
else intersect(tl(L1),L2);

fun combine(L1) = if tl(L1) = [] then hd(L1)
else
    foldr intersect [] L1;

What I want the code to do is start off by executing the combine function with a lists of lists. It checks if there is only one list (i.e. tl(L1) = []) and if it is true then just print the first list. If its false I want to call the foldr function that then calls the intersect function. In theory during the foldr function I want it to check the first list and second list and only keep what values are the same, then check the next list to those kept values and keeping doing this until it has checked every list. After that is done I want it to print each value that was in each list (i.e. intersection of sets).

I know my member function works and the combine function does what its supposed to do, my QUESTION is, what is wrong with the intersection function and can someone explain what the intersection should be doing?

I obviously don't want the straight up answer, that's not what I am here for. I need help to get on track for the right answer.

Do you have a specific question? What do you expect this code to do and what does it actually do? — David Brown

David Brown David Brown · Accepted Answer · 2011-12-05T15:56:55

Your member and combine functions seem fine, but you need to think through the intersect function more carefully. For starters, if L1 is an empty list, it rases an exception, because tl doesn't operate on empty lists. Think about the three cases you need to worry about:

L1 is nil
hd(L1) is in L2
hd(L1) is not in L2

Figure out what you need to do in each case and go from there.

SML set intersection using map, foldr, or foldl functions

2 Answers