A custom groupBy function in F#

An exercise in (F#)utility

In an effort to be “less bad” at F#, I wanted to write reimplement the built-in LINQ function groupBy without using for loops, mutable objects, or if-else logic.

Of course if we wanted to use all of these (and it would certainly make sense to do so in other languages) we could solve this problem quite easily.

Below is a reference implementation, written in Python (the only language where I can write syntactically correct code in my head):

def break_into_pieces( list, key_prop )

	unique_prop_keys = {}

	for elem in list:
		if elem.key_prop in unique_prop_keys.keys():
			unique_prop_keys[elem.kep_prop].append( elem )
		else:
			unique_prop_keys[elem.key_prop] = elem

A list of unique property keys

Getting a list of property values for each element in a list is pretty trivial.

let uniqueKeys = lst |> List.map (fun x -> x.Property)

let rec RemoveDups lst =
    match lst with
        | [] -> []
        | h::t -> h::(RemoveDups (List.filter (fun x -> x<>h) t))

Break into groups using a list of unique keys

let rec BreakIntoGroups lst groups =
    match lst, groups with
        | _, [] -> raise (ArgumentException( "At least one group must be specified" ))
        | [], _ -> raise (ArgumentException( "At least one group must be specified" ))
        | li, [grp] -> [(grp, li)]
        | li, (grp_h::grp_t) as group -> let segment = List.filter ( fun x -> x.Group = grp_h ) li in
                                         let remainder = List.filter ( fun x -> not (x.Group = grp_h) ) li in
                                            [(grp_h,segment)] @ (BreakIntoGroups remainder grp_t)

groupBy v 2.0

let groupBy' lst prop_fun =
    let uniqueGroups = lst |> List.map( prop_fun ) |> RemoveDups
    BreakIntoGroups lst uniqueGroups

Putting it all together

let rec RemoveDups lst =
    match lst with
        | [] -> []
        | h::t -> h::(RemoveDups (List.filter (fun x -> x<>h) t))

let rec BreakIntoGroups lst groups =
    match lst, groups with
        | _, [] -> raise (ArgumentException( "At least one group must be specified" ))
        | [], _ -> raise (ArgumentException( "At least one group must be specified" ))
        | li, [grp] -> [(grp, li)]
        | li, (grp_h::grp_t) as group -> let segment = List.filter ( fun x -> x.Group = grp_h ) li in
                                         let remainder = List.filter ( fun x -> not (x.Group = grp_h) ) li in
                                            [(grp_h,segment)] @ (BreakIntoGroups remainder grp_t)

let groupBy' lst prop_fun =
    let uniqueGroups = lst |> List.map( prop_fun ) |> RemoveDups
    BreakIntoGroups lst uniqueGroups