Случайная рекурсия, разрывая стек с помощью Seq.append, без использования `rec` - PullRequest
Новая
       42

Случайная рекурсия, разрывая стек с помощью Seq.append, без использования `rec`

0 голосов
/ 07 июня 2018

У меня был код, который ждал, чтобы взорвать что-то скрывающееся вокруг.Использование F # 4.1 Result похоже на это: 

module Result =
    let unwindSeq (sourceSeq: #seq<Result<_, _>>) =
        sourceSeq
        |> Seq.fold (fun state res -> 
            match state with
            | Error e -> Error e
            | Ok innerResult ->
                match res with
                | Ok suc -> 
                    Seq.singleton suc
                    |> Seq.append innerResult
                    |> Ok
                | Error e -> Error e) (Ok Seq.empty)

Очевидным узким местом здесь является Seq.singleton, добавленное к Seq.append.Я понимаю, что это медленно (и плохо написано), но почему оно должно взорвать стек? Я не думаю, что Seq.append по своей природе рекурсивен ... 

// blows up stack, StackOverflowException
Seq.init 1000000 Result.Ok
|> Result.unwindSeq
|> printfn "%A"

И, кроме того, чтобы развернуть последовательность Result, я исправил эту функцию, используя простой try-catch-reraise, но это также кажется подпарам.Любые идеи о том, как сделать это более идиоматически, без принудительной оценки последовательности или взрыва стека?

Не очень идеальное раскручивание (это также приводит к типу результат-сбой), но по крайней мере без предварительного-оценка последовательности: 

let unwindSeqWith throwArgument (sourceSeq: #seq<Result<_, 'a -> 'b>>) =
    try 
        sourceSeq
        |> Seq.map (throwOrReturnWith throwArgument)
        |> Ok
    with
    | e -> 
        (fun _ -> raise e)
        |> Error

1 Ответ

0 голосов
/ 07 июня 2018

Я полагаю, что идиоматический способ сложения последовательности Result с так, как вы предлагаете, будет: 

let unwindSeq<'a,'b> =
    Seq.fold<Result<'a,'b>, Result<'a seq, 'b>> 
        (fun acc cur -> acc |> Result.bind (fun a -> cur |> Result.bind (Seq.singleton >> Seq.append a >> Ok))) 
        (Ok Seq.empty)

Не то чтобы это будет немного быстрее, чем ваша текущая реализация, он просто использует Result.bind чтобы сделать большую часть работы.Я считаю, что стек переполнен, потому что рекурсивная функция где-то в библиотеке F #, вероятно, в модуле Seq.Моим лучшим доказательством этого является то, что материализация последовательности в List сначала, кажется, заставляет ее работать, как в следующем примере: 

let results = 
    Seq.init 2000000 (fun i -> if i <= 1000000 then Result.Ok i else Error "too big") 
    |> Seq.toList

results
|> unwindSeq
|> printfn "%A"

Однако, это может не сработать в вашем производственном сценарии, если последовательностьслишком велик, чтобы материализоваться в памяти.

...