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.