GroupBy key a sequence of ordered key values

I have a sorted (by key) sequence of key value pairs:

< (1,"A"),(1,"C"),(1,"G"),(1,"B"),(2,"D"),(2,"F"),(3,"E") >

And I have to produce a sequence of tuples like this:

< (1,< "A","C","G","B" >),(2, <"D","F">),(3, <"E">) >

Where the second element of the tuple is a sequence with the values corresponding to the key.

I am working on haskell, under the hood I have a Seq that is a Vector, but a pseudocode solution is OK.

I have this algorithm that will run in parallel in $$O(\lg n)$$, but cost of work is too high (more than $$O(n)$$):

comb :: Seq s => ((a, s b) -> (a, s b) -> Bool) -> s (a, s b) -> s (a, s b) -> s (a, s b)
comb f sl sr | lengthS sr == 0 = sl
| lengthS sl == 0 = sr
| f (nthS sl ((lengthS sl) - 1)) (nthS sr 0) =  let
(cl, vl) = (nthS sl ((lengthS sl) - 1))
(cr, vr) = (nthS sr 0)
union = singletonS (cr, appendS vl vr)
in appendS (appendS (takeS ((lengthS sl) - 1) sl) union) (dropS 1 sr)
| otherwise = appendS sl sr

groupDyC :: Seq s => ((a, s b) -> (a, s b) -> Bool) -> s (a, b) -> s (a, s b)
groupDyC f seq = reduceS (comb (f)) emptyS (mapS (\x -> singletonS x) (mapS (\(c, v) -> (c, singletonS v)) seq))

Where lengthA, nthS are $$O(1)$$ and appendS is linear to the size of both sequences.

My problem is that the solution has to have work in $$O(n)$$ and parallel cost (S) $$O(lg n)$$. How could I create an algorithm that runs on that cost with these operations: Thank you very much.

• What's your question? I don't see a question here. We are a question-and-answer site, so we ask you to articulate a specific question. Is there a reason to believe your requirements are achievable? Did you see this question asked somewhere as an exercise, for example? What's the computation model? Can we index into the sequence in $O(1)$ time? Please note that coding questions are off-topic here, so asking us for a solution in Haskell is out of scope for this site, but if you're asking about general algorithms, that is on-topic here.
– D.W.
Jul 2 '21 at 8:02
• @D.W. I tried my best to create a question that is more easily answered. Is the question now ok? Jul 2 '21 at 17:13

The boundary indices tell you how big each group is (by subtracting adjacent boundaries). Now, you just have to construct the output groups. For each group, do a tabulate, where you offset the index by the boundary. Specifically, the $$i$$th element of the $$j$$th group is input[boundary[j] + i].
In total, that's $$O(n)$$ work for the filter and maps/tabulates. The parallel time is dominated by the filter, costing $$O(\log n)$$.
• how do I find the boundry in $O(1)$ if I have to check every entry until I find the entry where the keys didn't match? In other words, if the entire list has a single key, does the algorithm run in parallel in O(log n)? Jul 15 '21 at 0:43