[Haskell-cafe] Improving *> and >> for Data.Sequence

[Ross Paterson]

On Tue, Nov 18, 2014 at 04:49:23PM -0500, David Feuer wrote:
> I'd like to define (*>) and (>>) for Data.Seq.Seq in a "clever" way,
> like replicate, but I'm a bit stuck. It kind of looks like this is the
> purpose behind the applicativeTree function, which bills itself as a
> generalization of replicateA, but something seems to have gotten stuck
> and the only time I see applicativeTree actually used is to define
> replicateA. With all the fancy nesting, I'm a bit lost as to how to
> go about this, and having only one example doesn't really help. Can
> someone help give me a clue?

I don't think applicativeTree will do the job -- it assumes the argument
is a 2-3 tree (not a finger tree).  The best I can think of is

xs *> ys = replicateSeq (Seq.length xs) ys

-- Concatenate n copies of xs
replicateSeq :: Int -> Seq a -> Seq a
replicateSeq n xs
  | n == 0 = empty
  | even n = nxs
  | otherwise = xs >< nxs
  where nxs = replicateSeq (n `div` 2) (xs >< xs)

I think it's O(log m*(log m + log n)), where m and n are the lengths of
the two sequences, which is certainly an improvement on O(mn).

Another way of doing replicateSeq would be

replicateSeq :: Int -> Seq a -> Seq a
replicateSeq n xs
  | n == 0 = empty
  | even n = half >< half
  | otherwise = xs >< half >< half
  where half = replicateSeq (n `div` 2) xs

I'm not sure which would give the most sharing.