Detecting properly nested parenthesis using functional programming

Question

So I have this code that is my attempt at a coding test from Codility. While my code produces correct results according to the requirements, (which unfortunately are copyrighted so I don't think I can reproduce them here), but I feel like it could be better organized, and in some places use a more functional approach to solving the problem.

So the basic idea is that it tests if the string if its properly nested parenthesis, or can be split into 2 halves which are properly nested.

let rec isNested (s : System.String) = 
    let s = s.ToCharArray()
    let s = List.ofArray s
    match s with
    | [] -> true //if its empty then its properly nested
    | _ -> 
        match s.Length % 2 with
        //if its even split the list in to 2 halves and test them
        | 0 -> //test form VW

            let len = s.Length
            let half = len / 2
            let mutable firsthalf = []
            let mutable secondhalf = []
            for i in 0..half - 1 do
                firsthalf <- s.[i] :: firsthalf
            for i in half..len - 1 do
                secondhalf <- s.[i] :: secondhalf
            firsthalf <- List.rev firsthalf 
            secondhalf <- List.rev secondhalf
            let VWtest = 
                isNested (new string(Array.ofList (firsthalf))) && isNested (new string(Array.ofList (secondhalf)))
            match VWtest with
            | true -> true
            | false -> 
                match (s.[0], s.[s.Length - 1]) with
                | ('(', ')') -> 
                  //remove the first and last elements  
                    let sublist = 
                        s.Tail
                        |> List.rev
                        |> List.tail
                        |> List.rev 
                    isNested (new string(Array.ofList (sublist)))
                | _ -> false
        | _ -> false //not a string with an even number of chars therefore can't be properly nested

let test = isNested >> Console.WriteLine
//let expect (b : bool) = Console.WriteLine(" expected ", b)
test "()"     // expect true
test ")("     // expect false
test "(())"   // expect true
test "()()"   // expect true
test "()(()"  // expect false
test "(()())" // expect true

Answer 1

The algorithm is overly complicated, and incorrect: for example, it will fail on the input (())().

I feel like it could ... use a more functional approach to solving the problem.

There is a more functional approach, maintaining a count of how many parentheses are open.

Let's start with the function signature

let rec isNested' (parens : char list) (openParens : int) : bool =

And fill in the cases. If there are no parentheses left to process, and no open parentheses, they are properly nested.

    match parens, openParens with
    | [], 0 -> true

If we are processing a (, we increase the open parentheses count

    | '(' :: rest, _ -> isNested' rest (openParens + 1)

I'll leave the other two cases up to you.

For convenience, we add a wrapper for this function

let isNested (parens : string) = isNested' (List.ofSeq parens) 0

Answer 2

Another approach...
Map the characters in the string as having a value of 1 for '(' and -1 for ')'.
Scan to get cumulative sums of the mapped values.
If all the cumulative sums are >= 0 and the last sum is = 0, the nesting is correct.

let isNested (chs : string) = 

    let scores = 
        (chs.ToCharArray())
        |> Seq.map (fun ch -> 
                        match ch with
                        |   '(' -> 1
                        |   ')' -> -1
                        |   _   -> 0)
        |>  Seq.scan (fun counter value -> counter + value) 0 // or |>  Seq.scan (+) 0
        |>  Seq.cache

    scores 
    |> Seq.forall (fun counter -> counter >= 0)
    && 
    scores 
    |> Seq.last = 0