вернуть false из цикла for, иначе продолжить в F #

Question

Я изучал F # в профессиональных целях. Я знаю Python / Django и C # /. NET Core. Поэтому я хотел перевести некоторый код, написанный на Python, на F #. Я был одержим или просто устал, не уверен, думал, что я мог бы использовать некоторое сотрудничество. Я хотел сделать else continue, но узнал, что это не вариант. Оригинальный код Python:

#!/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")

И до сих пор это то, что я получил, которое компилируется и работает в 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

Недоделанная часть такова:

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

    stack.append(value)

Вероятно, я буду спать на нем, но я бы с удовольствием, если бы кто-то сделал тяжелую работу за меня, чтобы я мог ее выбить, когда проснусь.

Answer 1

Вот частичное решение (в том смысле, что оно пытается воспроизвести Python, а не корректно, используя 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"

Я изменил это на интерактивный скрипт fsx, чтобы упростить его тестирование (запустите его с fsi filename.fsx ), но я думаю, что будет довольно легко преобразовать его обратно в скомпилированную программу .

Обратите внимание, что многим (если не большинству) фанатам F # эта программа не понравится из-за функции getNewRoot - там слишком много изменчивости.

Я перенес определение root в конец программы и заставил CanRepresentBST принять его в качестве параметра, чтобы сделать функцию чистой - если вы всегда собираетесь начинать с MinValue в качестве root, вы можете объявить его сверху CanRepresentBST. CanRepresentBST теперь использует вспомогательную подфункцию (бесполезно называемую subfunc), которая принимает параметры для вспомогательного элемента rem списка ввода, acc umulated 'stack' и текущего корневого значения. Затем он рекурсивно обрабатывает список ввода, возвращая false, как и прежде, true в конце списка, или обрабатывая его как обычно с помощью хвостового рекурсивного вызова.

getNewRoot используется для инкапсуляции обновления корневого значения и корректировки накопленного стека.

Обратите внимание, что это достаточно близкий перевод Python, поэтому он так сильно раздувается. Лучше было бы вернуться к сути того, чего вы пытаетесь достичь, и написать что-то новое, используя то, что у вас есть в F #. Если кто-то хочет опубликовать лучшую версию, сделайте это!