numeros - F#: ¿Cómo puedo dividir una secuencia en una secuencia de secuencias?

secuencia alfanumerica oracle

Question

Fondo:

Tengo una secuencia de datos contiguos, con sello de tiempo. 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 garantizar que los elementos solo se producen según sea necesario (no se puede usar list / array / cacheing)
• La solución NO debe ser O (n ^ 2), probablemente descartando un patrón Seq.take - Seq.skip (véase la publicación de Brian )
• Puntos de bonificación 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 >>)= ... 

A primera vista, el problema me parecía trivial, pero incluso empleando Seq.pairwise, IEnumerator <_>, comprensión de secuencias y declaraciones de rendimiento, la solución se me escapa. 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

Debajo hay un código que hace lo que creo que quieres. No es idiomático F #.

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

Pero no coincide exactamente con la especificación de la prueba: Seq.length enumera toda su entrada. Su "código de prueba" llama a Seq.length y luego llama a Seq.hd Eso generará un enumerador dos veces, y como no hay memoria 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 2

Parece que quieres una función que tenga 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 basada en el resultado de la función.

El almacenamiento en memoria caché de los valores en una colección que implementa IEnumerable probablemente sería el más simple (aunque no exactamente purista, pero evitando repetir la entrada varias veces. 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.

Answer 3

Traduje el Haskell de Alexey 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

Una solución Haskell, porque no sé bien la sintaxis F #, pero debería 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:

La función de grupo toma una lista y devuelve una lista de listas tal que la concatenación del resultado es igual al argumento. Además, cada sublista en el resultado contiene solo elementos iguales. Por ejemplo,

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

Es un caso especial de groupBy, que le permite al programador proporcionar su propia prueba de igualdad.

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 dicho grupo de funcionesBy1, podríamos escribir groupContiguousDataPoints fácilmente:

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

¡Así que vamos a escribirlo!

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: parece que F # no permite que el patrón coincida con el seq , por lo que no es muy fácil de traducir después de todo. Sin embargo, este hilo en HubFS muestra una forma de emparejar secuencias de patrones convirtiéndolos a LazyList cuando sea necesario.

ACTUALIZACIÓN2: las listas de Haskell son flojas y se generan según sea necesario, por lo que corresponden a LazyList F # (no a la seq , porque los datos generados se almacenan en la LazyList caché (y se recogen, por supuesto, si ya no se hace referencia)).

Answer 5

(EDITAR: Esto tiene un problema similar al de la solución de Brian, ¡en eso iterar la secuencia externa sin iterar sobre cada secuencia interna ensuciará las cosas mal!)

Aquí hay una solución que anida las expresiones de secuencia. La naturaleza imperfecta de IEnumerable<T> de .NET 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

De acuerdo, 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 7

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

(EDITAR: No estoy contento, está mal, pero no hay tiempo para intentar arreglarlo ahora).

Utiliza un poco de estado imperativo, pero no es demasiado difícil de seguir (siempre que recuerde 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 8

Creo que esto hace lo que quieres

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 buena pregunta