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

• Alexander Ryan Baggett: ah, I learn something new everyday. That is a much more efficient way of viewing the problem. I had a hard time understanding what the pattern ')' :: rest meant in the past. So I get now that you are matching the ')' as being the head of the list and giving the tail of the list an alias called rest that you can use later. I have a few books on F# but never has it been so illustrated so clearly. Thanks.
• mjolka: @AlexanderRyanBaggett thank you :) a good follow-up exercise is to determine if a string consisting of the characters (, ), [, ], {, and } is properly nested.
• Alexander Ryan Baggett: I have posted an update, I am very close, but still not quite there.
• svick: You can simplify that wrapper slightly by using List.ofSeq parens.

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