# Detecting properly nested parenthesis using functional programming

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

-
Jamal, if I were to open up a new question with the updated info would it not be flagged as a duplicate since the question is essentially the same? And on the other hand, would I have the option unaccepting his answer until the problem is resolved? – Alexander Ryan Baggett Sep 2 '14 at 1:33
Regarding the incorrect result, you should ask about it on SO if you'd like it fixed. – Jamal Sep 2 '14 at 1:35
While I appreciate the response Jamal, you have not answered either of the questions I just asked. – Alexander Ryan Baggett Sep 2 '14 at 1:36
So, if my code is ready to go, i.e. no bugs then I post to Code Review where the effeciency and design decisions could be examined, but if it is getting the code to do as it is intended, then I should take it to stackoverflow. Okay I feel I understand now. I was not aware of the need stop updates to questions. I will create a stackoverflow question and link to it from here if that's okay. – Alexander Ryan Baggett Sep 2 '14 at 1:44

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 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

-
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. – Alexander Ryan Baggett Sep 2 '14 at 1:08
@AlexanderRyanBaggett thank you :) a good follow-up exercise is to determine if a string consisting of the characters (, ), [, ], {, and } is properly nested. – mjolka Sep 2 '14 at 1:12
I have posted an update, I am very close, but still not quite there. – Alexander Ryan Baggett Sep 2 '14 at 1:26
You can simplify that wrapper slightly by using List.ofSeq parens. – svick Sep 2 '14 at 8:52
@svick thank you, I'll update the post :) – mjolka Sep 2 '14 at 11:12

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

-