Ocaml: Sorting a list into equivalence classes

Question

I recently started learning ocaml and am having trouble figuring out a problem.

Goal:

Given a list of integers and a function, sort the integers into equivalence classes based on the given function as lists inside another list. The order of the equivalence lists must be the same as the order given in the original list.

Update: I have decided to try and get it working without library function.

This is my code so far. It compiles but does not run. Any help with syntax would be appreciated.

let buckets f lst =
  let rec helpfunction f lst newlist = 
     match lst with
      | [] ->newlist
      | h::t -> match newlist with
             | [] -> helpfunction f lst [h]@newlist
             | [a]::_ -> if f h a 
                  then helpfunction f t [a::h]@newlist
                  else helpfunction f t ([a]::[h]@mylist

IMPORTANT: this is a homework question, so I am not looking for the code pasted for me. Im trying to logic through it on my home with a bit of help with the overall thought-process and syntax. Once I get it working I would to work on making it more efficient

Answer 1

Well, let's try to solve the task without doing it actually :)

Roughly speaking, the algorithm looks as follows:

1. Take the integer x from the source list

2. If the target list of lists (each of them contains integers of the same equivalence class) contains the list of the appropriate equivalence class add x to this list

3. Otherwise, create a new equivalence class list containing a single value ([x]) and add it to the target list

4. Repeat 1-3 for the other integers in the target list.

(1), (3) and (4) seems to be quite trivial to implement.

The challenges are how to implement (2) and how to do it efficiently :)

"Target list contains the list that..." can be rephrased as "there exists a list lst in a target list such as..." - this gives us a strong hint that List.exists can be somehow used here. What to test is also more or less clear: each member of the same equivalence class list are equivalent by definition, so we can take just the head and compare it with x using p.

The question is how to add an integer to a list within another list. Lists are immutable, so we cannot just drop it there... But we can take the target list and transform, or fold it into another one. I bet you got the hint: List.fold_left is another piece of the puzzle.

So, summarizing all this we can come to the following "more precise" algorithm

1. Start from the empty target list res

2. Take an integer x from the source list l

3. Use List.exists to check if there is a list lst in res such as for its head h p x h = true

4. If yes, use List.fold_left to transform the current res into a new one, where lst replaced with x::lst and all other equivalence class lists are copied as is

5. If no, introduce a new equivalence class (add [x] to res)

6. Repeat 2-5 for the next integer in the source list until it is empty.

The implementation that (almost) literally follows this algorithm is relatively simple. But it will be not very efficient because exists and fold will iterate over the same list twice doing literally the same check. With some tweaks, it should be possible to make it in a single run, but this non-efficient one should be good enough as the starting point...

Answer 2

What you are trying is to take each element in the input and then insert it somewhere in the result list of lists. Let me propose a different approach.

You start with an 'a list of input and an empty 'a list list of the result you construct.

If the input is empty your result is complete and you return it.

Otherwise split the input into head and tail (the pattern matching does that already). Next partition the input list into items that are equivalent to the head and those that are not. Recurse with the second list as new input and (first list :: result) as new result.