Difficulty with recursive list-splitting function in F#

Question

I'm trying to implement a function used to split a list into two equal-length halves (the problem assumes the list is of even length) in F#. Using the search function yielded a thread that deals with the exact same problem I'm trying to work through now:

Split list into two equal lists in F#

I'm trying to implement the solution given by the user Juliet, who provides a partial answer:

let cut l =
let rec cut = function
    | xs, ([] | [_]) -> xs
    | [], _ -> []
    | x::xs, y::y'::ys -> cut (xs, ys)
cut (l, l)

Which returns the second half of the list. I'm trying to work out a way to return the first half, so I made some modifications:

let rec cut(xs, ys) =
let zs = []
match xs, ys with
    | xs, ([] | [_]) -> (xs, zs)
    | [], _ -> ([], [])
    | x::xs, y1::y2::ys -> 
        x::zs
        cut (xs, ys)

You can probably tell that F# is my first functional programming language, and I'm kinda confused as to how it works, exactly. Pattern-matching is a new thing for me, and I was never very good at recursion to start with.

From what I understand, the way pattern matching works is that it's basically a more versatile version of an if-then-else statement, where the code to the left of the -> is the conditional (the "if" bit), and everything to the right is the block of code to execute if the conditional check passes (the "then" bit).

What I'm not totally sure of is whether you're allowed to do things like this:

| x::xs, y1::y2::ys -> 
        x::zs
        cut (xs, ys)

If pattern matching really does work like if statements, then it should be, since in an if statement it would look something like

 if (x::xs && y1::y2::ys)
       {
         x::zs
         cut (xs, ys)
       }

Anyhow, it doesn't seem like the statement x::zs is allowed, since Visual Studio gives me a warning:

The result of this expression is implicitly ignored. Consider using "ignore" to discard this value explicitly, e.g. 'expr |> ignore', or 'let' to bind the result to a name, e.g. let result = expr'.

I'm not sure what it means by that last part. I thought I had already declared the list as a local variable of the function in the line

let zs = []

All I'm trying to do is take the head of the list xs in each recursive iteration of the cut function and add it to another list zs, which when the base case is reached, would contain every element x passed over (in other words, the first half of the list), then return both xs (which contains the second half of the list) and the list containing the first half, but it doesn't seem like that's allowed?

Wesley Wiser Wesley Wiser · Accepted Answer · 2018-02-09T22:20:25

Anyhow, it doesn't seem like the statement x::zs is allowed, since Visual Studio gives me a warning.

The expression x::zs is allowed, but Visual Studio is trying to tell you that it has no effect. x::zs creates a new list but then immediately discards it (it does not mutate the existing value!).

Based on the rest of the code provided, zs should contain the first half of the list, but zs will only ever contain the empty list [] because that's the only value it is assigned to. In a language like C#, you would simply mutate the list by appending to it but in F# you shouldn't do that. Since you're already using recursion, this is a sign that zs should be a parameter to your recursive function so that you can use the new value later. (I've found that some people understand recursion better if they think of it as a callback. When you recurse, it's like providing parameters to a callback function. Any values you want to accumulate during the recursion process need to be provided as parameters to your function.)

Putting this all together, I think what you want is something like this:

let rec cut(xs, ys, zs) =
    match xs, ys with
    | xs, ([] | [_]) -> (xs, zs)
    | [], _ -> ([], [])
    | x::xs, y1::y2::ys ->
        cut (xs, ys, x::zs)

Typically, you'd hide this function inside a non-recursive function which sets up your arguments correctly:

let cut(xs, ys) =
    let rec impl(xs, ys, zs) =
        match xs, ys with
        | xs, ([] | [_]) -> (xs, zs)
        | [], _ -> ([], [])
        | x::xs, y1::y2::ys ->
            impl (xs, ys, x::zs)
    impl(xs, ys, [])

Note: There's no need to use ,s to seperate arguments in F#. When you do this, you are actually declaring that a function has a single argument consisting of a tuple. This is not usually what you want and it prevents currying the function. All you need to use to separate arguments is whitespace:

let cut xs ys =
    let rec impl xs ys zs =
        match xs, ys with
        | xs, ([] | [_]) -> (xs, zs)
        | [], _ -> ([], [])
        | x::xs, y1::y2::ys ->
            impl xs ys (x::zs)
    impl xs ys []

Difficulty with recursive list-splitting function in F#

2 Answers