separate.fs

(* First, a few dumb extensions on IEnumerable *)

type System.Collections.Generic.IEnumerable<'a> with
  member xs.ChopHead = (Seq.head xs, Seq.skip 1 xs)
  member xs.Cut f = (Seq.takeWhile f xs, Seq.skipWhile f xs)


(* Given a sequence, I want to partition it according to some fairly complex rules.
   I'm using a pair of sequence expressions depending on what's at the head of the sequence.
   Unfortunately, this code is prohibitively slow for the large inputs I'm sending it.
   When I profile this, 62% of the time is spent in SeqModule.Head and 30% is in SeqModule.IsEmpty.
   I'm not really sure how to improve the performance... *)

let rec Separate level (q:Structure seq) =
  let levelIsBelowOrEqual (s:Structure) =
    match s.Level with 
    | Some x when x = 0 -> true
    | Some x when x <= level -> false 
    | _ -> true
  
  let levelIsBelowOrBlank (s:Structure) =
    match s.Level with 
    | Some x when x >= level -> false
    | _ -> true 

  if Seq.isEmpty q then Seq.empty
  elif level <= 0 then Seq.singleton q else
  match (Seq.head q).Level with
  | Some x when x >= level ->
    seq {
      let first, rest = q.ChopHead
      let children, remainder = rest.Cut levelIsBelowOrEqual
      yield Seq.append (Seq.singleton first) children
      yield! Separate level remainder
    }
  | _ ->
    seq {
      let chunk, remainder = q.Cut levelIsBelowOrBlank
      if Seq.isEmpty chunk then failwithf "Could not cut sequence, breaking recursion: %A" q
      yield chunk
      yield! Separate level remainder
    }