Проблема реализации F # Seq

Я недавно копался в исходном коде F #.

в Seq.fs:

// Binding. 
//
// We use a type defintion to apply a local dynamic optimization. 
// We automatically right-associate binding, i.e. push the continuations to the right.
// That is, bindG (bindG G1 cont1) cont2 --> bindG G1 (cont1 o cont2)
// This makes constructs such as the following linear rather than quadratic:
//
//  let rec rwalk n = { if n > 0 then 
//                         yield! rwalk (n-1)
//                         yield n }

Увидев приведенный выше код, я протестировал два кода:

let rec rwalk n = seq { if n > 0 then 
                         yield n
                         yield! rwalk (n-1)
                      }

и

let rec rwalk n = seq { if n > 0 then 
                         yield! rwalk (n-1)
                         yield n 
                      }

. Я обнаружил, что первый очень быстрый, а второй очень медленный. Если n = 10000, на моем компьютере для генерации этой последовательности требуется 3 секунды, то есть квадратичное время.

Квадратичное время является разумным, например,

seq {yield! {1; 2; ...; n-1}; yield n} переводится в

Seq.append {1; 2; ...; n-1} {n}

Я думаю, эта операция добавления должна занимать линейное время. В первом коде операция добавления выглядит так: seq {yield n; Уступать! {n-1; п-2; ...; 1}} , что требует постоянного времени.

Комментарии в коде говорят, что это линейное (возможно, это линейное время не является линейным). Возможно, это linear относится к использованию настроенной реализации для последовательности, а не выражения вычисления Moand / F # (как указано в спецификации F #, однако в спецификации не упоминается причина для этого ...).

Кто-нибудь может прояснить здесь нечеткость? Большое спасибо!

(ps, поскольку это проблема языкового дизайна и оптимизации, я также добавил тег Haskell, чтобы узнать, есть ли у людей идеи.)