Idiomatic F# for iterating a seq and mapping whenever changes occur on a given selection

Question

I've written a function that takes a sequence and check for every item in that sequence whether the current value a selection (obtained with a selection function) is different (or on the first iteration) from the previous computed value and if that's the case (we considered there is a change), then map the current item and returns a new mapped item along the current item.

If there is no change the sequence keeps returning the current item and the last mapped item detected due to a change.

let differentOrNew option currentValue =
    match option with
    | Some value when currentValue <> value ->
        true
    | Some _ ->
        false
    | None ->
        true

let def<'T> =
    Unchecked.defaultof<'T>

let mapChange selector mapping seq =
    let mutable previous = None
    let mutable change = def

    seq
    |> Seq.map(fun item ->
        let currentValue = selection item
        if differentOrNew previous currentValue then
            previous <- Some currentValue
            change <- mapping item
        item, change)
    |> Seq.map(fun state -> fst state, snd state)

That code works, but it's clearly not the best idiomatic piece of F# code I've ever seen.

I am wondering how to get something more "F#-idiomatic".

Answer 1

I like having a Seq.groupAdjacentBy helper function for this kind of thing. It uses mutation in its own small scope to keep the implementation simple and builds on F#'s own Seq.groupBy. It groups values based on their key according to a key generating function (like your function), but only puts values in the same group if they are adjacent. I like this because it has quite a well defined and understandable meaning so it's easy to re-use elsewhere:

module Seq =
    let groupAdjacentBy f xs =
        let mutable prevKey, i = None, 0
        xs
        |> Seq.groupBy (fun x ->
            let key = f x
            if prevKey <> Some key then
                i <- i + 1
                prevKey <- Some key
            (i, key))
        |> Seq.map (fun ((_, k), v) -> (k, v))

Using this, a function like yours becomes fairly simple to write:

let mapChange selector mapping xs =
    xs
    |> Seq.groupAdjacentBy selector
    |> Seq.collect (fun (_, values) ->
        let values = values |> Seq.toArray
        let mapped = mapping values.[0]
        seq {
            for x in values do
                x, mapped })

let isEven x = x % 2 = 0

mapChange isEven string [1; 3; 2; 3] // seq [(1, "1"); (3, "1"); (2, "2"); (3, "3")]

Note that this uses "unsafe" access of the first item in an array, which would throw an exception for an empty array, but we know that any groups created by the grouping function must have at least one item (just like F#'s Seq.groupBy).

Answer 2

|> Seq.map(fun state -> fst state, snd state)

I think this last operation is unnecessary as it is a map from 'a * 'b to 'a * 'b (fst returns the first element in the tuple and snd the second).

---

If you want to get rid of the mutable variables, you can use Seq.mapFold instead:

let mapChange selector mapping seq = 
    seq
    |> Seq.mapFold (fun (previous, change) item ->
        let currentValue = selector item
        match differentOrNew previous currentValue with
        | true -> 
            let newChange = mapping item
            (item, newChange), (Some currentValue, newChange)
        | false -> 
            (item, change), (previous, change)
    ) (None, def)
    |> (fst)

Answer 3

I ended up doing something like that:

let def<'T> =
    Unchecked.defaultof<'T>

module Seq =

    let mapbi mapping source =
        source
        |> Seq.scan(fun state item -> fst state + 1I, item) (-1I, def)
        |> Seq.skip(1)
        |> Seq.map(fun (bi, item) -> mapping bi item)

    let mapChange selector mapping source =
        source
        |> mapbi (fun bi item -> bi, item)
        |> Seq.scan(fun (previousSelection, previousMappedItem, _) (bi, item) ->
            if bi = 0I then
                (selector item, mapping item, item)
            else
                let currentSelection = selector item
                let mappedItem = mapping item
                if previousSelection <> currentSelection then
                    (currentSelection, mappedItem, item)
                else
                    (previousSelection, previousMappedItem, item)
            ) (def, def, def)
        |> Seq.skip 1
        |> Seq.map(fun (_, mappedItem, item) -> mappedItem, item)

// and its AsyncSeq counterpart
module AsyncSeq =

    let mapbi mapping source =
        source
        |> AsyncSeq.scan(fun state item -> fst state + 1I, item) (-1I, def)
        |> AsyncSeq.skip(1)
        |> AsyncSeq.map(fun (bi, item) -> mapping bi item)

    let mapChange selector mapping source =
        source
        |> mapbi (fun bi item -> bi, item)
        |> AsyncSeq.scan(fun (previousSelection, previousMappedItem, _) (bi, item) ->
            if bi = 0I then
                (selector item, mapping item, item)
            else
                let currentSelection = selector item
                let mappedItem = mapping item
                if previousSelection <> currentSelection then
                    (currentSelection, mappedItem, item)
                else
                    (previousSelection, previousMappedItem, item)
            ) (def, def, def)
        |> AsyncSeq.skip 1
        |> AsyncSeq.map(fun (_, mappedItem, item) -> mappedItem, item)

(Dummy) Example:

[<EntryPoint>]
let main _ =
    Seq.replicate 4 [1 .. 3]
    |> Seq.mapi(fun i s ->
        s |> Seq.map (fun item -> {| SetIndex = i; RecordIndex = item |} ))
    |> Seq.concat
    |> AsyncSeq.ofSeq
    |> AsyncSeq.mapChange
        (fun item -> item.SetIndex)
        (fun item -> List.init (item.SetIndex + 1) (fun _ -> item.SetIndex))
    |> AsyncSeq.iterAsync(fun (mappedItem, item) ->
        async { printfn "%A: %A" item mappedItem })
    |> Async.RunSynchronously
    |> ignore
    0

Output:

{ RecordIndex = 1
  SetIndex = 0 }: [0]
{ RecordIndex = 2
  SetIndex = 0 }: [0]
{ RecordIndex = 3
  SetIndex = 0 }: [0]
{ RecordIndex = 1
  SetIndex = 1 }: [1; 1]
{ RecordIndex = 2
  SetIndex = 1 }: [1; 1]
{ RecordIndex = 3
  SetIndex = 1 }: [1; 1]
{ RecordIndex = 1
  SetIndex = 2 }: [2; 2; 2]
{ RecordIndex = 2
  SetIndex = 2 }: [2; 2; 2]
{ RecordIndex = 3
  SetIndex = 2 }: [2; 2; 2]
{ RecordIndex = 1
  SetIndex = 3 }: [3; 3; 3; 3]
{ RecordIndex = 2
  SetIndex = 3 }: [3; 3; 3; 3]
{ RecordIndex = 3
  SetIndex = 3 }: [3; 3; 3; 3]

Two things that are more idiomatic that my initial piece of code:

• No mutable
• Still work even if the initial sequence is empty
• Still "Stream" everything => memory allocation over long sequence is roughly constant

Not fully satisfied, still kinda too cluttered =|