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