What Is the Name of This Function?

Posted by on in Blogs
There is a function I need. I know how to write it, but I don't know if it has a standard name (like map, fold, etc.). It takes one argument -- a list of something -- and returns a list of 2-tuples of equal length. Each tuple contains one item from the list and the list without that item. It's probably easiest if I show you an example:

> f [1; 2; 3];;
val it : (int * int list) list = [
(1, [2; 3])
(2, [1; 3])
(3, [1; 2])

Here's the implementation I'm using:

let f (items : 'T list) =
let rec implementation (start : 'T list) = function
| [] -> []
| item :: tail -> (item, start @ tail) :: implementation (start @ [ item ]) tail
implementation [] items

Anybody know a standard name for this function?


In case you're curious, the reason I want this is I'm implementing a decision tree. I have a list of functions which are predicates over the domain of my example data. I need to try each function in the list, pick the "best", and then recurse over the rest of the functions. "Best" is usually measured in terms of information gain.

It's never a great idea to do equality comparisons on functions, so it's helpful to transform this list into a list of functions paired with the remaining functions.


Check out more tips and tricks in this development video: