F #: Как мне разбить последовательность на последовательность последовательностей

Question

Фон:

У меня есть последовательность смежных данных с отметкой времени. В последовательности данных есть пробелы, в которых данные не являются смежными. Я хочу создать метод для разделения последовательности на последовательность последовательностей, чтобы каждая подпоследовательность содержала непрерывные данные (разбивать входную последовательность в промежутках).

Ограничения:

• Возвращаемое значение должно быть последовательностью последовательностей, чтобы элементы создавались только по мере необходимости (нельзя использовать список / массив / кэширование)
• Решение НЕ должно быть O (n ^ 2), возможно, исключающим шаблон Seq.take - Seq.skip (см. Пост Брайана post)
• Бонусные баллы за функционально идиоматический подход (поскольку я хочу стать более опытным в функциональном программировании), но это не является обязательным требованием.

Подпись метода

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

На первый взгляд, проблема выглядела тривиально для меня, но даже при использовании Seq.pairwise, IEnumerator <_>, последовательных пониманий и операторов yield, решение ускользает от меня. Я уверен, что это потому, что мне все еще не хватает опыта комбинирования F # -идиом или, возможно, потому что есть некоторые языковые конструкции, с которыми я еще не сталкивался.

// 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

Я думаю, что это то, что вы хотите

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))

Спасибо, что задали этот крутой вопрос

Answer 2

Я перевел Haskell Алексея на F #, но это не красиво в F #, и все же один элемент слишком нетерпелив

Я ожидаю, что есть лучший способ, но мне придется попробовать позже.

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 3

Хорошо, попробую еще раз. Достижение оптимального уровня лени в F # оказывается немного сложным ... С другой стороны, это несколько более функционально, чем моя последняя попытка, поскольку в нем не используются ссылки на ячейки.

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 4

(РЕДАКТИРОВАТЬ: Это страдает от проблемы, аналогичной решению Брайана, в том, что итерация внешней последовательности без итерации по каждой внутренней последовательности будет плохо испортить!)

Вот решение, которое вкладывает выражения последовательности. Непривычная природа .NET IEnumerable<T> здесь довольно очевидна, что затрудняет написание идиоматического кода F # для этой проблемы, но, надеюсь, все еще понятно, что происходит.

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 5

Решение на Haskell, потому что я плохо знаю синтаксис F #, но его должно быть достаточно легко перевести:

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

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

В прелюдии есть функция groupBy :: (a -> a -> Bool) -> [a] -> [[a]]:

Функция группы берет список и возвращает список списков так, что конкатенация результата равна аргументу. Более того, каждый подсписок в результате содержит только равные элементы. Например,

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

Это особый случай groupBy, который позволяет программисту предоставлять собственный тест на равенство.

Это не совсем то, что мы хотим, потому что он сравнивает каждый элемент в списке с первым элементом текущей группы, и нам нужно сравнить последовательные элементы. Если бы у нас была такая функция groupBy1, мы могли бы легко написать groupContiguousDataPoints:

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

Итак, давайте напишем это!

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

ОБНОВЛЕНИЕ: похоже, что F # не позволяет вам сопоставлять паттерны на seq, поэтому перевод не так уж и прост. Тем не менее, этот поток в HubFS показывает способ последовательности шаблонных совпадений путем преобразования их в LazyList при необходимости.

UPDATE2: списки на Haskell являются ленивыми и генерируются по мере необходимости, поэтому они соответствуют F # * LazyList (а не seq, потому что сгенерированные данные кэшируются (и сборщик мусора, конечно, если вы больше не держите ссылку на него)).

Answer 6

Вы, кажется, хотите функцию с подписью

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

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

Кэширование значений в коллекцию, которая реализует IEnumerable, вероятно, будет наиболее простым (хотя и не совсем пуристическим, но избегающим многократного повторения ввода. Это потеряет большую часть лени ввода):

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
  }

Альтернативная реализация может передать функцию кэширования (как seq<'a>) функции, чтобы она могла видеть несколько элементов для выбора точек останова.

Answer 7

Хорошо, вот ответ, которым я не недоволен.

(РЕДАКТИРОВАТЬ: я несчастен - это неправильно! Хотя сейчас нет времени пытаться исправить.)

В нем используется немного императивного состояния, но за ним не так уж трудно следовать (при условии, что вы помните, что '!' Является оператором разыменования F #, а не 'нет'). Он настолько ленив, насколько возможно, и принимает seq в качестве входных данных и возвращает seq of seqs в качестве выходных.

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

Ниже приведен код, который делает то, что я думаю, вы хотите. Это не идиоматический F #.

(Это может быть похоже на ответ Брайана, хотя я не могу сказать, потому что я не знаком с семантикой LazyList.)

Но это не совсем соответствует вашей спецификации теста: Seq.length перечисляет весь ввод. Ваш «тестовый код» вызывает Seq.length, а затем вызывает Seq.hd. Это сгенерирует перечислитель дважды, и, поскольку кэширование отсутствует, все будет испорчено. Я не уверен, есть ли какой-нибудь чистый способ разрешить использование нескольких перечислителей без кэширования. Честно говоря, seq<seq<'a>> не может быть лучшей структурой данных для этой проблемы.

В любом случае, вот код:

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