Friday, September 18, 2009

Sequence of positions in a sequence (F#)

Steve Horsfield's blog had a post on fold functions that cared about the beginning, middle and ends of the sequence they were operating on.  I think there’s a preprocessing step that simplifies the problem – transform the sequence into a seq<Position<'t>>, where Position tells you if the object is at the beginning, middle, or end of the sequence:

type Position<'t> =
| Beginning of 't
| Middle of 't
| End of 't
| Only of 't

let rec sequenceOfPositionsWithLazyList(existing: LazyList<'t>) =
  seq {
    let rec elementsAfterBeginning(s) =
      seq {
        match s with
        | LazyList.Cons(h, LazyList.Nil) -> yield End(h); ()
        | LazyList.Cons(h, t) -> yield Middle(h); yield! elementsAfterBeginning(t)
        | _ -> ()
      }
    match existing with
      | LazyList.Cons(h, LazyList.Nil) -> yield Only(h); ()
      | LazyList.Cons(h, t) -> yield Beginning(h); yield! elementsAfterBeginning(t)
      | LazyList.Nil -> ()
  }
  
let sequenceOfPositions(existing: seq<'t>) = sequenceOfPositionsWithLazyList(LazyList.of_seq existing)
  
printfn "%A" (sequenceOfPositions [1;2;3])
printfn "%A" (sequenceOfPositions [1;3])
printfn "%A" (sequenceOfPositions [1])
printfn "%A" (sequenceOfPositions [])

The output is:

seq [Beginning 1; Middle 2; End 3]
seq [Beginning 1; End 3]
seq [Only 1]
seq []

I think that makes following steps much easier to write.

No comments: