F# Threading Changing State Through Unfold

Question

I'm trying to process a sequence of items whereby the process step relies on some additional cumulative state from the prior items (ordering isn't important).

Essentially:

1. I have a Seq<'A>
2. I have a (Type * int) list referred to as the skip list
3. I have a process step 'A -> (Type * int) list -> 'B option
   • This takes the current skip list

The method in question essentially:

Seq<'A'> -> (Type * int) list -> (Type * int) list

So we take a bunch of input items and an initial skip list and produce a final skip list.

I've basically got the following so far:

sourceItems
|> Seq.map (fun srcItem -> (srcItem, outerSkip))
|> Seq.unfold (fun elem ->
    match elem with
    | SeqEmpty -> None
    | SeqCons((srcItem, skip), tail) -> 
        match process(srcItem, skip) with
        | Some targetItem -> Some((Some targetItem, skip), tail)
        | None -> Some((None, skip), tail |> Seq.map (fun (i, skp) -> (i, (srcItem.GetType(), liD srcItem) :: skp))))

With SeqEmpty and SeqCons being active patterns:

let (|SeqEmpty|SeqCons|) (xs: 'a seq) =
    if Seq.isEmpty xs then SeqEmpty
    else SeqCons(Seq.head xs, Seq.skip 1 xs)

My process so far basically just starts off with the items and adds the initial skip to each, unfolds and maps the remaining seq to have the same item but with the new skip list.

I have a number of problems with this:

1. It's ugly and confusing as all hell
2. I'm sure it's less than performant

Ideally I'd like to avoid the need to map the items to include the initial skip list in the first place, but then I'm not sure how I'd get that into the unfold aside from mapping it into just the first element in the sequence.

---

Possible Alternative Solution

Based on a different approach taken in List processing with intermediate state (Mark's answer)

I've been able to use:

items
|> Seq.fold (fun (skip) srcItem ->
    match process(srcItem, skip) with
    | None -> (srcItem.GetType(), liD srcItem) :: skip
    | Some tgtItem ->
        skip
    ) outerSkip

Which aside from all the stuff needed when there is an item, appears to actually do the trick!

This is significantly simpler than the unfold approach, but I'm a little unclear on exactly how it's working.

I'm assuming that fun (skip) srcItem -> ... is essentially creating a function expecting an additional parameter that through the magic of something (partial application?) I'm able to provide to fold using outerSkip - is this right?

Answer 1

I ended up adopting the fold strategy as mentioned in the question.

The final code is:

let result =
    items
    |> Seq.fold (fun (skip, targetItems), srcItem ->
        match process(srcItem, skip) with
        | None -> ((srcItem.GetType(), getId srcItem) :: skip, targetItems)
        | Some tgtItem -> (skip, tgtItem :: targetItems)) (outerSkip, [])

With result being a tuple ((Type * int) list, obj list) which is exactly what I wanted.

I'm then able to take action on the target items, and to just return the final skip list.

This is a huge improvement over the unfold method I was using previously.