Последовательность списка в F #?

Question

я должен написать функцию, которая начала от бесконечной последовательности и возвращается, как это:

входной sq0 = {x0, x1, x2, x3, ... хп}

выходная последовательность -> {[ x0], [x0; x1], [x0; x1; x2] [x0; x1; x2; x3] ...}

Вы можете мне помочь?

я попытался это

let rec pref sq = seq { 
    yield [Seq.nth 0 sq] 
    let x1 = Seq.nth 1 sq 
    yield [x1] @ [x0] 
    yield! pref Seq.skip 2 sq 
} 

Answer 1

Вы можете использовать функцию Seq.scan:

let createSeq s = 
    s 
    |> Seq.scan (fun x y -> x @ [y]) [] 
    |> Seq.skip 1 

Answer 2

Это работает довольно хорошо, но, вероятно, может быть более эффективным:

let input = 
    Seq.initInfinite (fun i -> sprintf "x%i" i) 

let output = 
    input 
    |> Seq.mapi (fun i _ -> input |> Seq.take (i + 1) |> Seq.toList) 

Answer 3

Там нет ничего неправильно с некоторой изменчивостью.

let gen xs = 
    let ra = ResizeArray() 
    seq{ for x in xs do 
       ra.Add x 
       yield Seq.toList ra } 

gen ["x0";"x1";"x2";"x3";"x4"] 
|> printfn "%A" 

Выход:

seq [["x0"]; ["x0"; "x1"]; ["x0"; "x1"; "x2"]; ["x0"; "x1"; "x2"; "x3"]; ...] 

Answer 4

Если у вас уже есть последовательность элемента accumularte, ответ Густаво не плохо.

В противном случае это рекурсивное определение также может работать.

let rec createSeq = Seq.scan List.append List.empty init 
and  init  = seq {yield [1]; yield! createSeq} 

let l = createSeq |> Seq.take 5 |> Seq.toArray 

Помните, что последовательность представляет собой интерфейс, так что многие профили производительности существует в зависимости от схемы реализации и доступа используется.

Answer 5

Если производительность, что вы после этого, то это то, что вы хотите, как с точки зрения времени, и с точки зрения использования памяти (это похудел версия Seq.scan от компилятора):

let scan z (source : seq<'T>) = 
    seq { let zref : ('T list ref) = ref z 
      yield !zref 
      use ie = source.GetEnumerator() 
      while ie.MoveNext() do 
       zref := ie.Current :: !zref 
       yield !zref } 

let input = Seq.initInfinite (fun i -> sprintf "x%i" i) 

let createSeqCustom s = 
    s 
    |> scan [] 
    |> Seq.skip 1 

> System.GC.Collect() 
> let l = input |> createSeq |> Seq.take 2000 |> Seq.toArray 

Real: 00:00:00.007, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0 

СРАВНЕНИЮ к следующему наивысшему ответу:

let createSeq s = 
    s 
    |> Seq.scan (fun x y -> x @ [y]) [] 
    |> Seq.skip 1 

> System.GC.Collect() 
> let l2 = input |> createSeq |> Seq.take 2000 |> Seq.toArray 

Real: 00:00:00.293, CPU: 00:00:00.296, GC gen0: 6, gen1: 4, gen2: 0 

Важным отличием является сбор мусора. Эта реализация также будет обрабатывать большие последовательности (обратите внимание на 200.000 пунктов принимается):

> System.GC.Collect() 
> let l = input |> createSeqCustom |> Seq.take 200000 |> Seq.toArray 

Real: 00:00:00.406, CPU: 00:00:00.406, GC gen0: 11, gen1: 5, gen2: 0 

В то время как другие реализации запустить из памяти на гораздо меньших ресурсах (обратите внимание на 20000 пунктов принимается):

> let l2 = input |> createSeq |> Seq.take 20000 |> Seq.toArray 

System.OutOfMemoryException: Exception of type 'System.OutOfMemoryException' was thrown. 
Stopped due to error