return false from for loop otherwise continue in F#

user_5493548 0
Viewed 188

I was studying F# for professional purposes. I know Python/Django and C#/.NET Core. So I wanted to translate some code that I wrote in Python into F#. I was getting hung up or just plain tired, not sure, thought I could use some collaboration. I wanted to do else continue but found out thats not an option. Original python code:

#!/Users/ryandines/.local/share/virtualenvs/netcoreapp2.0-5nmzfUwt/bin/python

NUMBER_OF_TESTS = input()

INT_MIN = -2**32

def can_represent_bst(pre):
    stack = []
    root = INT_MIN
    for value in pre:
        if value < root:
            return False
        while(stack and stack[-1] < value):
            root = stack.pop()

        stack.append(value)

    return True

for test in range(int(NUMBER_OF_TESTS)):
    node_count = int(input())
    nodes = list(map(int, input().split(' ')))
    print("NODES: " + str(nodes))
    if can_represent_bst(pre=nodes):
        print("YES")
    else:
        print("NO")

And so far this is what I got that compiles and works in F#:

open System
let NumberOfTests = Console.ReadLine() |> int
let root = Int32.MinValue
let seq1 = seq { for i in 0 .. NumberOfTests-1 -> (i, i*i) }

let CanRepresentBST args =
    printfn "Passed args: %s" args
    let result = args.Split ' '
    let IntList = [for i in result -> i |> int32]
    for value in IntList do
        printfn "%d" value

[<EntryPoint>]
let main argv =
    printfn "Hello World from F#!"    
    printfn "Number of tests: %d" NumberOfTests   
    printfn "Int min value: %d" root

    for _ in seq1 do
        let NodeCount = Console.ReadLine()
        let Nodes = Console.ReadLine()
        printfn "NodeCount: %s" NodeCount      
        let _ = CanRepresentBST Nodes
        0 |> ignore

    0

The not done part is this:

    if value < root:
        return False
    while(stack and stack[-1] < value):
        root = stack.pop()

    stack.append(value)

Probably am going to sleep on it but would love if someone did the heavy lifting for me so I can knock it out when I wake up.

f# python
1 Answers

Here's a partial solution (in that it tries to replicate the Python, rather than properly using F#):

open System
let NumberOfTests = Console.ReadLine() |> int

let rec getNewRoot value stack root =
    let mutable newRoot = root
    let mutable acc = stack
    while not (List.isEmpty acc) && (List.head acc) < value do
       newRoot <- List.head acc
       acc <- List.tail acc

    (newRoot, acc)

let CanRepresentBST args baseRoot =
    printfn "Passed args: %s" args
    let intList = args.Split ' ' |> Seq.map int |> Seq.toList
    let rec subfunc rem acc root =
        match rem with
        | [] -> true
        | r :: rs ->
            if r < root then
                false
            else
                let (newRoot, newAcc) = getNewRoot r acc root
                subfunc rs (r :: newAcc) newRoot

    subfunc intList [] baseRoot

printfn "Number of tests: %d" NumberOfTests
let root = Int32.MinValue
printfn "Int min value: %d" root

for _ in 1..NumberOfTests do
    let NodeCount = Console.ReadLine()
    let Nodes = Console.ReadLine()
    printfn "NodeCount: %s" NodeCount
    if CanRepresentBST Nodes root then
        printfn "YES"
    else
        printfn "NO"

I changed this to a fsx interactive script to make it easier to test out (run it with fsi filename.fsx), but I think it should be pretty easy to convert this back to the compiled program.

Note that many (if not most) F# fans would not like this program, due to the getNewRoot function - there's far too much mutability going on in there.

I moved the definition of root to the end of the program and made CanRepresentBST take it as a parameter, to make the function pure - if you're always going to start with MinValue as root, you could declare it at the top of CanRepresentBST. CanRepresentBST now uses a helper subfunction (unhelpfully named subfunc), which takes parameters for the remainder of the input list, the accumulated 'stack' and the current root value. It then recursively processes the input list, returning false as before, true at the end of the list, or processing it as normal with a tail-recursive call.

getNewRoot is used to encapsulate the updating of the root value and adjustment of the accumulated stack.

Note that this is a reasonably close translation of the Python, which is why it bloats out so much. Better would be to go back to the essence of what you're trying to achieve and write something new using what you have in F#. If somebody else wants to post a better version, please do so!

user_67927090
Related