F #: ¿Cómo dividir una secuencia en una secuencia de secuencias

Question

Antecedentes:

tengo una secuencia de datos contiguos, con fecha y hora. La secuencia de datos tiene lagunas en donde los datos no son contiguos. Quiero crear un método para dividir la secuencia en una secuencia de secuencias para que cada subsecuencia contenga datos contiguos (divida la secuencia de entrada en los espacios).

restricciones:

• El valor de retorno debe ser una secuencia de secuencias para asegurar que elementos se producen sólo cuando sea necesario (no se puede utilizar la lista/matriz/cacheing)
• La solución no debe ser O (n^2), probablemente descartando un patrón Seq.take - Seq.skip (Brian's post)
• Puntos extra para un enfoque funcionalmente idiomático (ya que quiero ser más competente en programación funcional), pero no es un requisito.

firma del método

let groupContiguousDataPoints (timeBetweenContiguousDataPoints : TimeSpan) (dataPointsWithHoles : seq<DateTime * float>) : (seq<seq< DateTime * float >>)= ... 

En vista de ello el problema parecía trivial para mí, pero incluso empleando Seq.pairwise, IEnumerator < _>, por comprensión de la secuencia y las declaraciones de rendimiento, las soluciones elude yo. Estoy seguro de que esto se debe a que todavía carezco de experiencia con la combinación de los valores F # -idioms, o posiblemente porque hay algunas construcciones lingüísticas a las que aún no he estado expuesto.

// Test data 
let numbers = {1.0..1000.0} 
let baseTime = DateTime.Now 
let contiguousTimeStamps = seq { for n in numbers ->baseTime.AddMinutes(n)} 

let dataWithOccationalHoles = Seq.zip contiguousTimeStamps numbers |> Seq.filter (fun (dateTime, num) -> num % 77.0 <> 0.0) // Has a gap in the data every 77 items 

let timeBetweenContiguousValues = (new TimeSpan(0,1,0)) 

dataWithOccationalHoles |> groupContiguousDataPoints timeBetweenContiguousValues |> Seq.iteri (fun i sequence -> printfn "Group %d has %d data-points: Head: %f" i (Seq.length sequence) (snd(Seq.hd sequence))) 

Answer 1

parece que quieres una función que tiene la firma

(`a -> bool) -> seq<'a> -> seq<seq<'a>> 

es decir, una función y una secuencia, luego divida la secuencia de entrada en una secuencia de secuencias en función del resultado de la función.

Almacenamiento en caché de los valores en una colección que implementa IEnumerable probablemente sería más simple (aunque no exactamente purista, pero evitando la iteración de la entrada en múltiples ocasiones se perderá gran parte de la pereza de la entrada.):

 
let groupBy (fun: 'a -> bool) (input: seq) = 
    seq { 
    let cache = ref (new System.Collections.Generic.List()) 
    for e in input do 
     (!cache).Add(e) 
     if not (fun e) then 
     yield !cache 
     cache := new System.Collections.Generic.List() 
    if cache.Length > 0 then 
    yield !cache 
    } 

Una implementación alternativa podría pasar la colección de caché (como seq<'a>) a la función para que pueda ver múltiples elementos para elegir los puntos de ruptura.

solución

Answer 2

Un Haskell, porque no sé F # sintaxis bien, pero debe ser lo suficientemente fácil de traducir:

type TimeStamp = Integer -- ticks 
type TimeSpan = Integer -- difference between TimeStamps 

groupContiguousDataPoints :: TimeSpan -> [(TimeStamp, a)] -> [[(TimeStamp, a)]] 

hay una función groupBy :: (a -> a -> Bool) -> [a] -> [[a]] en el preludio:

The group function takes a list and returns a list of lists such that the concatenation of the result is equal to the argument. Moreover, each sublist in the result contains only equal elements. For example,

group "Mississippi" = ["M","i","ss","i","ss","i","pp","i"] 

It is a special case of groupBy, which allows the programmer to supply their own equality test.

No es exactamente lo que queremos, porque compara cada elemento de la lista con el primer elemento del grupo actual, y tenemos que comparar elementos consecutivos.Si tuviéramos una función tal groupBy1, podríamos escribir fácilmente groupContiguousDataPoints:

groupContiguousDataPoints maxTimeDiff list = groupBy1 (\(t1, _) (t2, _) -> t2 - t1 <= maxTimeDiff) list 

Así que vamos a escribir!

groupBy1 :: (a -> a -> Bool) -> [a] -> [[a]] 
groupBy1 _ []   = [[]] 
groupBy1 _ [x]   = [[x]] 
groupBy1 comp (x : xs@(y : _)) 
    | comp x y = (x : firstGroup) : otherGroups 
    | otherwise = [x] : groups 
    where groups@(firstGroup : otherGroups) = groupBy1 comp xs 

ACTUALIZACIÓN: se ve como F # no le permite el ajuste de patrones en seq, por lo que no es demasiado fácil de traducir después de todo. Sin embargo, this thread on HubFS muestra una forma de emparejar secuencias de patrones convirtiéndolos a LazyList cuando sea necesario.

Update2: Haskell enumera son perezoso y generada cuando se necesita, por lo que se corresponde con F # 's LazyList (no seq, ya que los datos generados se almacenan en caché (y el recolector de basura, por supuesto, si ya no mantiene una referencia a eso)).

Answer 3

He traducido Alexey's Haskell a F #, pero no es bonito en F #, y sigue siendo un elemento demasiado ansioso.

Espero que haya una mejor manera, pero tendré que volver a intentarlo más tarde.

let N = 20 
let data = // produce some arbitrary data with holes 
    seq { 
     for x in 1..N do 
      if x % 4 <> 0 && x % 7 <> 0 then 
       printfn "producing %d" x 
       yield x 
    } 

let rec GroupBy comp (input:LazyList<'a>) : LazyList<LazyList<'a>> = 
    LazyList.delayed (fun() -> 
    match input with 
    | LazyList.Nil -> LazyList.cons (LazyList.empty()) (LazyList.empty()) 
    | LazyList.Cons(x,LazyList.Nil) -> 
     LazyList.cons (LazyList.cons x (LazyList.empty())) (LazyList.empty()) 
    | LazyList.Cons(x,(LazyList.Cons(y,_) as xs)) -> 
     let groups = GroupBy comp xs 
     if comp x y then 
      LazyList.consf 
       (LazyList.consf x (fun() -> 
        let (LazyList.Cons(firstGroup,_)) = groups 
        firstGroup)) 
       (fun() -> 
        let (LazyList.Cons(_,otherGroups)) = groups 
        otherGroups) 
     else 
      LazyList.cons (LazyList.cons x (LazyList.empty())) groups) 

let result = data |> LazyList.of_seq |> GroupBy (fun x y -> y = x + 1) 
printfn "Consuming..." 
for group in result do 
    printfn "about to do a group" 
    for x in group do 
     printfn " %d" x 

Answer 4

A continuación se muestra un código que hace lo que creo que usted desea. No es idiomático F #.

(Puede ser similar a la respuesta de Brian, aunque no puedo decir porque no estoy familiarizado con la semántica LazyList.)

Pero no coincidir exactamente con su especificación de prueba: enumera Seq.length toda su entrada. Su "código de prueba" llama al Seq.length y luego llama al Seq.hd. Eso generará un enumerador dos veces, y dado que no hay almacenamiento en caché, las cosas se arruinan. No estoy seguro de si hay alguna forma limpia de permitir múltiples enumeradores sin almacenar en caché. Francamente, seq<seq<'a>> puede no ser la mejor estructura de datos para este problema.

De todos modos, aquí está el código:

type State<'a> = Unstarted | InnerOkay of 'a | NeedNewInner of 'a | Finished 

// f() = true means the neighbors should be kept together 
// f() = false means they should be split 
let split_up (f : 'a -> 'a -> bool) (input : seq<'a>) = 
    // simple unfold that assumes f captured a mutable variable 
    let iter f = Seq.unfold (fun _ -> 
     match f() with 
     | Some(x) -> Some(x,()) 
     | None -> None)() 

    seq { 
     let state = ref (Unstarted) 
     use ie = input.GetEnumerator() 

     let innerMoveNext() = 
      match !state with 
      | Unstarted -> 
       if ie.MoveNext() 
       then let cur = ie.Current 
        state := InnerOkay(cur); Some(cur) 
       else state := Finished; None 
      | InnerOkay(last) -> 
       if ie.MoveNext() 
       then let cur = ie.Current 
        if f last cur 
        then state := InnerOkay(cur); Some(cur) 
        else state := NeedNewInner(cur); None 
       else state := Finished; None 
      | NeedNewInner(last) -> state := InnerOkay(last); Some(last) 
      | Finished -> None 

     let outerMoveNext() = 
      match !state with 
      | Unstarted | NeedNewInner(_) -> Some(iter innerMoveNext) 
      | InnerOkay(_) -> failwith "Move to next inner seq when current is active: undefined behavior." 
      | Finished -> None 

     yield! iter outerMoveNext } 


open System 

let groupContigs (contigTime : TimeSpan) (holey : seq<DateTime * int>) = 
    split_up (fun (t1,_) (t2,_) -> (t2 - t1) <= contigTime) holey 


// Test data 
let numbers = {1 .. 15} 
let contiguousTimeStamps = 
    let baseTime = DateTime.Now 
    seq { for n in numbers -> baseTime.AddMinutes(float n)} 

let holeyData = 
    Seq.zip contiguousTimeStamps numbers 
     |> Seq.filter (fun (dateTime, num) -> num % 7 <> 0) 

let grouped_data = groupContigs (new TimeSpan(0,1,0)) holeyData 


printfn "Consuming..." 
for group in grouped_data do 
    printfn "about to do a group" 
    for x in group do 
     printfn " %A" x 

Answer 5

(EDIT:! Este sufre de un problema similar a la solución de Brian, en el que la iteración de la secuencia externa sin iterar sobre cada secuencia interna voluntad echar las cosas mal)

Aquí hay una solución que anida las expresiones de secuencia. La naturaleza imperfecta de .NET IEnumerable<T> es bastante evidente aquí, lo que hace que sea un poco más difícil escribir el código F # idiomático para este problema, pero espero que todavía esté claro lo que está sucediendo.

let groupBy cmp (sq:seq<_>) = 
    let en = sq.GetEnumerator() 
    let rec partitions (first:option<_>) = 
    seq { 
     match first with 
     | Some first' ->    //' 
     (* The following value is always overwritten; 
      it represents the first element of the next subsequence to output, if any *) 
     let next = ref None 

     (* This function generates a subsequence to output, 
      setting next appropriately as it goes *) 
     let rec iter item = 
      seq { 
      yield item 
      if (en.MoveNext()) then 
       let curr = en.Current 
       if (cmp item curr) then 
       yield! iter curr 
       else // consumed one too many - pass it on as the start of the next sequence 
       next := Some curr 
      else 
       next := None 
      } 
     yield iter first' (* ' generate the first sequence *) 
     yield! partitions !next (* recursively generate all remaining sequences *) 
     | None ->() // return an empty sequence if there are no more values 
    } 
    let first = if en.MoveNext() then Some en.Current else None 
    partitions first 

let groupContiguousDataPoints (time:TimeSpan) : (seq<DateTime*_> -> _) = 
    groupBy (fun (t,_) (t',_) -> t' - t <= time) 

Answer 6

Ok, aquí hay una respuesta con la que no estoy contento.

(EDIT: Estoy infeliz - que está mal No hay tiempo para tratar de arreglar este momento sin embargo.)

Se utiliza un poco de estado fundamental, pero no es demasiado difícil de seguir (siempre que recordar que '!' es el operador de desreferencia F #, y no 'no'). Es tan vago como sea posible, y toma un seq como entrada y devuelve un seq de seqs como salida.

let N = 20 
let data = // produce some arbitrary data with holes 
    seq { 
     for x in 1..N do 
      if x % 4 <> 0 && x % 7 <> 0 then 
       printfn "producing %d" x 
       yield x 
    } 
let rec GroupBy comp (input:seq<_>) = seq { 
    let doneWithThisGroup = ref false 
    let areMore = ref true 
    use e = input.GetEnumerator() 
    let Next() = areMore := e.MoveNext(); !areMore 
    // deal with length 0 or 1, seed 'prev' 
    if not(e.MoveNext()) then() else 
    let prev = ref e.Current 
    while !areMore do 
     yield seq { 
      while not(!doneWithThisGroup) do 
       if Next() then 
        let next = e.Current 
        doneWithThisGroup := not(comp !prev next) 
        yield !prev 
        prev := next 
       else 
        // end of list, yield final value 
        yield !prev 
        doneWithThisGroup := true } 
     doneWithThisGroup := false } 
let result = data |> GroupBy (fun x y -> y = x + 1) 
printfn "Consuming..." 
for group in result do 
    printfn "about to do a group" 
    for x in group do 
     printfn " %d" x 

Answer 7

Bien, intentando de nuevo. Lograr la cantidad óptima de pereza resulta ser un poco difícil en F # ... Por el lado positivo, esto es algo más funcional que mi último intento, en el sentido de que no utiliza ninguna celda de ref.

let groupBy cmp (sq:seq<_>) = 
    let en = sq.GetEnumerator() 
    let next() = if en.MoveNext() then Some en.Current else None 
    (* this function returns a pair containing the first sequence and a lazy option indicating the first element in the next sequence (if any) *) 
    let rec seqStartingWith start = 
    match next() with 
    | Some y when cmp start y -> 
     let rest_next = lazy seqStartingWith y // delay evaluation until forced - stores the rest of this sequence and the start of the next one as a pair 
     seq { yield start; yield! fst (Lazy.force rest_next) }, 
      lazy Lazy.force (snd (Lazy.force rest_next)) 
    | next -> seq { yield start }, lazy next 
    let rec iter start = 
    seq { 
     match (Lazy.force start) with 
     | None ->() 
     | Some start -> 
      let (first,next) = seqStartingWith start 
      yield first 
      yield! iter next 
    } 
    Seq.cache (iter (lazy next())) 

Answer 8

creo que esto hace lo que quiere

dataWithOccationalHoles 
|> Seq.pairwise 
|> Seq.map(fun ((time1,elem1),(time2,elem2)) -> if time2-time1 = timeBetweenContiguousValues then 0, ((time1,elem1),(time2,elem2)) else 1, ((time1,elem1),(time2,elem2))) 
|> Seq.scan(fun (indexres,(t1,e1),(t2,e2)) (index,((time1,elem1),(time2,elem2))) -> (index+indexres,(time1,elem1),(time2,elem2)) ) (0,(baseTime,-1.0),(baseTime,-1.0)) 
|> Seq.map(fun (index,(time1,elem1),(time2,elem2)) -> index,(time2,elem2)) 
|> Seq.filter(fun (_,(_,elem)) -> elem <> -1.0) 
|> PSeq.groupBy(fst) 
|> Seq.map(snd>>Seq.map(snd)) 

Gracias por hacer esta pregunta fresca