3
\$\begingroup\$

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".

\$\endgroup\$
0
2
\$\begingroup\$

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

\$\endgroup\$
3
  • \$\begingroup\$ nice! Thanks a ton! \$\endgroup\$ Apr 11 '20 at 15:56
  • \$\begingroup\$ One downside of the implementation is the Seq.groupby which may take a good chunk of memory if there is a lot data coming in. \$\endgroup\$ Apr 11 '20 at 16:41
  • \$\begingroup\$ @KerryPerret I hadn't considered that implicit requirement of laziness. Previously I had assumed that Seq.groupBy was lazy and didn't evaluate the whole sequence but I've realised it can't be, because it can't know the contents of the first group without checking all of the elements. However, Seq.groupByAdjacent could potentially be lazy but it would need to be implemented from scratch without using Seq.groupBy. I may do this some time... \$\endgroup\$ Apr 12 '20 at 13:25
2
\$\begingroup\$

|> 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)
\$\endgroup\$
4
  • \$\begingroup\$ Yes you're right, I don't remember why I put |> Seq.map(fun state -> fst state, snd state), guess I was a little bit too tired when I posted that =|. I only have one issue with mapFold implementations tho, is that it actually relies on toArray implementation behind the scene: github.com/fsharp/fsharp/blob/master/src/fsharp/FSharp.Core/… \$\endgroup\$ Apr 10 '20 at 7:36
  • \$\begingroup\$ github.com/dotnet/fsharp/issues/7009 \$\endgroup\$ Apr 11 '20 at 15:56
  • \$\begingroup\$ @KerryPerret: It's maybe a point, but the problem is, that you have to materialize the mapping in order to accumulate the final state. The current implementation do that by first convert the seq to an array. See also the first comment by cartermp. \$\endgroup\$
    – user73941
    Apr 12 '20 at 6:24
  • \$\begingroup\$ I'm aware of that. The issues arises when I'm dealing with a big (huge) chunk of data. \$\endgroup\$ Apr 12 '20 at 12:07
1
\$\begingroup\$

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

\$\endgroup\$
4
  • \$\begingroup\$ I believe you can write the Seq.mapChange using AsyncSeq.mapChange instead of duplicating the code: source |> AsyncSeq.ofSeq |> AsyncSeq.mapChange selector mapping |> AsyncSeq.toBlockingSeq \$\endgroup\$ Apr 12 '20 at 13:42
  • \$\begingroup\$ The problem is the underlying implementation of toBlockingSeq. True, it's actually what I've done in my code. Will update my answer. Thanks for pointing this out. \$\endgroup\$ Apr 12 '20 at 13:53
  • \$\begingroup\$ I'm not sure why that's a problem here. If you know the AsyncSeq doesn't contain any asynchronous work then you know you're not actually blocking threads. \$\endgroup\$ Apr 14 '20 at 10:47
  • \$\begingroup\$ Not saying it's an actual problem here. My point is that it's also pretty cool to have an implementation which is as agnostic as possible so that if someone need to have some async operations it can be useful too. \$\endgroup\$ Apr 14 '20 at 11:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.