Partition with predicate

Question

So I have a list type:

type ConsList<'value> =
    | Cons of head: 'value * tail: ConsList<'value>
    | Empty

And a partition function for it:

let rec partition lst pivot =
    match lst with
    | Empty -> Empty, Empty
    | Cons(hd, tl) ->
        let parts = partition tl pivot

        if hd < pivot then
            Cons(hd, fst parts), snd parts
        else
            fst parts, Cons(hd, snd parts)

But I need to make a function that accepts a predicate and distributes elements according to it into the first or second list. For example, partition (fun elem -> elem % 2 = 0) lst

I ended up with this:

let rec partition predicate lst =
    match lst with
    | Empty -> Empty, Empty
    | Cons(hd, tl) ->
        let parts = partition predicate tl

        match predicate with
        | true -> Cons(hd, fst parts), snd parts
        | false -> fst parts, Cons(hd, snd parts)

But when you try to give it a lambda expression, it fails with [FS0002] This function takes too many arguments, or is used in a context where a function is not expected

Answer 1

I think you just forgot to use hd as the argument to predicate. Try this:

let rec partition predicate lst =
    match lst with
    | Empty -> Empty, Empty
    | Cons(hd, tl) ->
        let parts = partition predicate tl

        match predicate hd with   // <- this is the line I changed
        | true -> Cons(hd, fst parts), snd parts
        | false -> fst parts, Cons(hd, snd parts)

BTW, matching on a bool is overkill. Just use if instead:

        if predicate hd then
            Cons(hd, fst parts), snd parts
        else
            fst parts, Cons(hd, snd parts)

Test case:

let lst = Cons (2, Cons(1, Cons (0, Empty)))
let evens, odds =
    partition (fun elem -> elem % 2 = 0) lst
printfn "%A" evens   // Cons (2, Cons (0, Empty))
printfn "%A" odds    // Cons (1, Empty)