F#: Как я разделяю последовательность на последовательность последовательностей

Я перевел 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

Похоже, вам нужна функция с сигнатурой

(`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> ) в функцию, чтобы она могла видеть несколько элементов для выбора точек останова.

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

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

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

Существует функция groupBy :: (a -> a -> Bool) -> [a] -> [[a]] в Prelude:

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

 группа «Миссисипи» = [«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

UPDATE: похоже, F # не позволяет вам сопоставить шаблон на seq , так что переводить в конце концов не так-то просто. Однако этот поток на HubFS показывает способ сопоставления последовательностей с образцом путем преобразования их в LazyList , когда это необходимо.

ОБНОВЛЕНИЕ2: Списки Haskell ленивы и генерируются по мере необходимости, поэтому они соответствуют F # '

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

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

Он использует немного императивного состояния, но за ним нетрудно следовать (при условии, что вы помните, что '!' - это оператор разыменования F #, а не 'not'). Он настолько ленив, насколько это возможно, и принимает последовательность на входе и возвращает последовательность последовательностей на выходе.

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

"Методы классов File и FileInfo похожи, но отличаются тем, что методы класса File статические , поэтому вам необходимо передать больше параметров, чем для методов экземпляра FileInfo. Это необходимо сделать, потому что он работает с конкретным файлом; например, метод FileInfo.CopyTo () принимает один параметр для пути назначения, который используется для копирования файла, тогда как метод File.Copy () принимает два параметра для исходного и целевого пути. "

http: //www.aspfree.com/c/a/C-Sharp/A-Look-at-C-Sharp-File-and-FileInfo-Classes/1/

http://www.intelliott.com/blog /PermaLink,guid,ce9edbdb-6484-47cd-a5d6-63335adae02b.aspx

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

Вот решение, которое вкладывает выражения последовательности. Неприятный характер .NET IEnumerable здесь довольно очевиден, что немного усложняет написание идиоматического кода 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)

Хорошо, попробую еще раз. Достижение оптимального количества лени в 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()))

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

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

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

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

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