Должно ли это выражение последовательности быть хвостово-рекурсивным? - PullRequest
Новая
       58

Должно ли это выражение последовательности быть хвостово-рекурсивным?

4 голосов
/ 16 июля 2010

Это выражение F # seq для меня выглядит хвостово-рекурсивным, но я получаю исключения переполнения стека (с включенными хвостовыми вызовами). Кто-нибудь знает, что мне не хватает? 

let buildSecondLevelExpressions expressions =
    let initialState = vector expressions |> randomize
    let rec allSeq state = seq {
        for partial in state do
            if count partial = 1
            then yield Seq.head partial
            if count partial > 1 || (count partial = 1 && depth (Seq.head partial) <= MAX_DEPTH) then
                let allUns = partial
                                |> pick false 1
                                |> Seq.collect (fun (el, rr) -> (createExpUnaries el |> Seq.map (fun bn -> add rr bn)))
                let allBins = partial  // Careful: this case alone produces result recursivley only if |numbers| is even (rightly!).
                                |> pick false 2
                                |> Seq.collect (fun (el, rr) -> (createExpBinaries el |> Seq.map (fun bn -> add rr bn)))
                yield! allSeq (interleave allBins allUns)
    }
    allSeq initialState

Если вам интересно, хотя это не должно быть важно, pick используется для генерации комбинаций элементов в последовательности и interleave чередует элементы из 2 последовательностей. vector является конструктором для ResizeArray.

Ответы [ 3 ]

4 голосов
/ 16 июля 2010

Как указал Гидеон, это не является хвостовой рекурсией, потому что у вас все еще есть другие элементы в списке состояний для обработки.Сделать эту хвостовую рекурсию не так просто, потому что вам нужно очередь элементов, которые должны быть обработаны.

Следующий псевдокод показывает одно из возможных решений.Я добавил work параметр, который хранит оставшуюся работу, которую предстоит сделать.При каждом вызове мы обрабатываем только первый элемент.Все остальные элементы добавляются в очередь.Когда мы заканчиваем, мы выбираем больше работы из очереди: 

let rec allSeq state work = seq { 
    match state with 
    | partial::rest -> 
        // Yield single thing to the result - this is fine
        if count partial = 1 then yield Seq.head partial 
        // Check if we need to make more recursive calls...
        if count partial > 1 || (* ... *) then 
            let allUns, allBins = // ...
            // Tail-recursive call to process the current state. We add 'rest' to 
            // the collected work to be done after the current state is processed
            yield! allSeq (interleave allBins allUns) (rest :: work)
        else
            // No more processing for current state - let's take remaining
            // work from the 'work' list and run it (tail-recursively)
            match work with 
            | state::rest -> yield! allSeq state rest
            | [] -> () //completed
    | _ -> 
        // This is the same thing as in the 'else' clause above. 
        // You could use clever pattern matching to handle both cases at once
        match work with 
        | state::rest -> yield! allSeq state rest
        | [] -> () } //completed
3 голосов
/ 17 июля 2010

Я не могу найти определение того, какие вызовы внутри выражения последовательности находятся в хвостовой позиции в F #, поэтому я настоятельно рекомендую не писать код, который зависит от семантики текущей реализации, т.е. это неопределенное поведение.

Например, попытка перечислить (например, применяя Seq.length) следующую последовательность вызывает переполнение стека: 

let rec xs() = seq { yield! xs() }

но, как отметил Томас, на самом деле работает следующее: 

let rec xs n = seq { yield n; yield! xs(n+1) }

Мой совет - всегда заменять выражения рекурсивной последовательности на Seq.unfold. В этом случае вы, вероятно, захотите накопить работу, которую нужно выполнить (например, когда вы вернетесь в левую ветвь, вы вставите правую ветвь в стек в аккумуляторе).

FWIW, даже справочник по языку F # ошибается. Он дает следующий код для выравнивания дерева: 

type Tree<'a> =
   | Tree of 'a * Tree<'a> * Tree<'a>
   | Leaf of 'a

let rec inorder tree =
    seq {
      match tree with
          | Tree(x, left, right) ->
               yield! inorder left
               yield x
               yield! inorder right
          | Leaf x -> yield x
    }

Их собственный код убивает F # интерактивно с переполнением стека при подаче глубокого дерева слева.

1 голос
/ 16 июля 2010

Это не будет хвостовой рекурсией, потому что вы могли бы вызывать рекурсивно несколько раз.Чтобы перевести на псевдокод: 

allSeq(state)
{
    foreach (partial in state)
    {
        if (...)
        {
            yield ...
        }
        if (...)
        {
            ...
            //this could be reached multiple times
            yield! allSeq(...)
        }
    }
}
...