# Sorting a list into different bags according to predicate

I've just started with F# (I'm coming from a mostly OO background) and I'm looking for

• feedback on the code, particularly: is this the way F# code should be written like?
• have I overlooked an existing library function which would make this easier or could replace it completely?

The goal is:

Take an input list and sort it according to certain conditions into several bags, keeping also those items not fitting any condition. (Which is why groupBy doesn't do the trick, unless I'm overlooking something).

The function:

let sortIntoBags<'T, 'TBag> (predicate: 'TBag*'T->bool) (bags: 'TBag list)
(lst: 'T list)=
let take (lst: 'T list) (bag: 'TBag)=
let isInBag e = predicate (bag, e)
let (inBag, remaining) = lst |> List.partition isInBag
((bag, inBag), remaining)
let (bagSets, leftOver) = bags |> List.mapFold take lst
(bagSets, leftOver)


A simple example for usage is:

> let l= [1..25];;

val l : int list =
[1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20; 21;
22; 23; 24; 25]

> let bags= [2; 3; 5; 7];;
val bags : int list = [2; 3; 5; 7]

> let isDivisorFor (x, y) = 0=y%x ;;
val isDivisorFor : x:int * y:int -> bool

> l |> sortIntoBags isDivisorFor bags;;
val it : (int * int list) list * int list =
([(2, [2; 4; 6; 8; 10; 12; 14; 16; 18; 20; 22; 24]); (3, [3; 9; 15; 21]);
(5, [5; 25]); (7, [7])], [1; 11; 13; 17; 19; 23])

• @graipher why remove the thanks? it's just polite, isn't it? – AModernRonin Sep 8 '18 at 22:05
• how big of a concern is performance? – Maslow Sep 9 '18 at 17:42
• @AModernRonin: While polite it is usually deemed redundant (greetings at the beginning of the questions even more so). You can thank people who provide valuable feedback by upvoting their answers or accepting one answer as the most helpful answer. Have a look here for a list of editing advice on this site and here for the network wide discussion – Graipher Sep 10 '18 at 9:48
• @Maslow: as long as profiling doesn't show up the function as a bottleneck, performance is no big consideration. The question was more about getting feedback as to how idiomatic my code is, from a funcional/F# perspective. – AModernRonin Sep 10 '18 at 17:32

I like your use of List.partition but I have the following suggestion:

If it's possible in the context then avoid making the arguments as a tuple in the predicate. Just declare it as:

let isDivisorFor div x = x % div = 0


NB: I use this version in all versions below

It will IMO make it all more readable:

let sortIntoBags predicate bags lst =
let take lst bag =
let (inBag, remaining) = lst |> List.partition (predicate bag)
((bag, inBag), remaining)
let (bagSets, leftOver) = bags |> List.mapFold take lst
(bagSets, leftOver)


    let (bagSets, leftOver) = bags |> List.mapFold take lst
(bagSets, leftOver)


Here there is no need for the last line. Just return the right side of the first line - making it a little more simple:

let sortIntoBags predicate bags lst =
let take lst bag =
let (inBag, remaining) = lst |> List.partition (predicate bag)
((bag, inBag), remaining)
bags |> List.mapFold take lst


Just for fun, I made a version using recursion:

let sortIntoBags predicate bags data =
let rec part lst bgs result =
match bgs with
| [] -> result |> List.rev, lst
| _ -> let group, remaing = lst |> List.partition (predicate bgs.Head)
part data bags []


Notice that I have the total result as argument to the part function in order to make it tail-recursive.

If you can live with an Option value as the group key, it is fairly simple to use List.groupBy:

let sortIntoBags predicate bags data =
data |> List.groupBy (fun x -> bags |> List.tryFind (fun k -> predicate k x))


... If not it gets a little more complicated and then your own may be a better choise:

let sortIntoBags predicate bags data =
let result = data |> List.groupBy (fun x -> bags |> List.tryFind (fun k -> predicate k x))
(result |> List.where (fun (k, l) -> k.IsSome) |> List.map (fun (k, l) -> k.Value, l), result |> List.where (fun (k, l) -> k.IsNone) |> List.head |> snd)


or with the use of List.partition:

let sortIntoBags predicate bags data =
let result = data |> List.groupBy (fun x -> bags |> List.tryFind (fun k -> predicate k x)) |> List.partition (fun (k, l) -> k.IsSome)
(fst result |> List.map (fun (k, l) -> k.Value, l), (snd result |> List.head |> snd))

• thanks a lot! this was just what I was really looking for when I posted the question here – AModernRonin Sep 20 '18 at 21:22

Here's another (Subjectively better or worse) way to write this, however it does require comparison unlike yours:

let sortIntoBags<'T,'TKey when 'TKey : comparison > (predicate:'TKey*'T -> bool) (bagKeys:'TKey list) (items:'T list) : ('TKey*'T list) list * 'T list =
let bagMap:Map<'TKey,'T list> = bagKeys |> Seq.map(fun k -> k,List.empty) |> Map.ofSeq
items
|> List.rev
|> List.fold(fun (bagMap,unmatched:'T list) (item:'T) ->
match bagMap |> Map.tryFindKey(fun k _ -> predicate(k,item)) with
| Some k -> bagMap |> Map.add k (item::bagMap.[k]), unmatched
| None -> bagMap,item::unmatched

) (bagMap,List.empty)
|> fun (m,x)->
m |> Map.toList, x


and the xunit tests I used to make sure it matched the output

open global.Xunit

[<Fact>]
let originalQuestion2 () =
let l= [1..25]
let bags= [2; 3; 5; 7]
let isDivisorFor (x, y) = 0=y%x
let expected = [(2, [2; 4; 6; 8; 10; 12; 14; 16; 18; 20; 22; 24]); (3, [3; 9; 15; 21]);(5, [5; 25]); (7, [7])], [1; 11; 13; 17; 19; 23]
let actual = l |> BagSort.sortIntoBags isDivisorFor bags
printfn "%A" actual
Console.Error.WriteLine(sprintf "%A" actual)
Trace.WriteLine(sprintf "%A" actual)
Assert.Equal(expected, actual)

[<Fact>]
let originalQuestionUnfolded2 () =
let l= [1..25]
let bags= [2; 3; 5; 7]
let isDivisorFor (x, y) = 0=y%x
let expected =
let a =
[   2, [2; 4; 6; 8; 10; 12; 14; 16; 18; 20; 22; 24]
3, [3; 9; 15; 21]
5, [5; 25]
7, [7]
]
let b = [1; 11; 13; 17; 19; 23]
a,b
let actual = l |> BagSort.sortIntoBags isDivisorFor bags
Assert.Equal(expected, actual)
Assert.Equal((fst expected |> fun x -> x.[0]), fst actual |> fun x -> x.[0])

• Thanks a lot! Would you mind adding a bit of explanation what the advantages/disadvantages of both versions are? – AModernRonin Sep 10 '18 at 17:27
• It's subjective. To me, mine is more readable and simpler. No partition. The fold's function definition is inline, with less type specificity clutter. the idea of a key mapped to the items that match a condition seems a better fit to a Map or Dictionary rather than a list of Key*Value list. Were I not trying to match your output exactly, I'd return a Map. I can't help but think there's a way to bag these with groupBy using Map<Option 'TKey,'TValue list> as the container. I liked your let isInBag e = predicate (bag, e) better than mine, forgot to swap it. – Maslow Sep 10 '18 at 17:39
• Disclaimer: I'm entirely self-taught in functional programming with no one to guide me on idiomaticism or to bounce ideals off of. – Maslow Sep 10 '18 at 17:40
• so, I didn't really get the feedback about how idiomatic or not my code was, but after two days your's is the only answer, so I'll mark it as "the one"... – AModernRonin Sep 11 '18 at 19:48
• Both versions appear idiomatic to me. Subjectively, for no very good reason, I prefer the OP's version as more readable and simpler. And it does not need to reverse the list (I'm assuming that the order of the results is the same without reversing). – Scott Hutchinson Sep 13 '18 at 15:03