Как я могу сделать эту функцию F # хвостовой рекурсивной во всех случаях? - PullRequest
Новая
       40

Как я могу сделать эту функцию F # хвостовой рекурсивной во всех случаях?

0 голосов
/ 23 декабря 2018

Я пробираюсь через проблему Адвента Кодекса в этом году в F #, чтобы улучшить свои навыки в этом языке.Я придумал следующее решение для День 8, часть 1 : 

namespace AdventOfCode2018.Core

module Day8 =

    let calculatePart1 input = 
        let rec take numberToTake numberTaken taken remaining =
            if numberTaken = numberToTake || List.isEmpty remaining then
                taken, remaining
            else
                take numberToTake (numberTaken + 1) 
                    (List.head remaining :: taken) (List.tail remaining)

        let rec calculate input sum depth maxDepth =
            let quantityOfChildNodes, quantityOfMetadata, remaining = 
                match input with
                | qc :: qm :: tl -> qc, qm, tl
                | _ -> 0, 0, []
            let input, sum = 
                match quantityOfChildNodes with 
                | 0 -> remaining, sum
                | q -> calculate remaining sum 1 q
            let metadata, remaining = take quantityOfMetadata 0 [] input
            let sum = sum + List.sum metadata
            if depth = maxDepth then remaining, sum
            else calculate remaining sum (depth + 1) maxDepth

        calculate input 0 0 1 |> snd

Мой код дает правильное решение проблемы и, кажется, работает достаточно быстро (13 мс с использованием моей головоломкивход на машине i7).Однако при отладке кода я заметил, что он не является хвостово-рекурсивным.Первый рекурсивный вызов в calculate генерирует новый кадр стека.Второго рекурсивного вызова в конце функции нет.Я уверен, что возможно написать первый вызов, чтобы он был хвостово-рекурсивным, но я не уверен, как.

...