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

[David Feuer]

Many thanks. I don't *think* it's ever been as bad as O(mn) (I'm pretty
sure it's no worse than O(m log m log n) and it may well be better), but
it's certainly not great for time and it's definitely not great for space.
I believe both of your versions are essentially based on fast
exponentiation, which was going to be my fall-back position barring
something more magically good taking advantage of the tree structure
somehow. I know there are some fancy versions of fast exponentiation to
minimize multiplications, but any version thereof would be better than the
current approach.

On Wed, Nov 19, 2014 at 11:45 AM, Ross Paterson <R.Paterson at city.ac.uk>
wrote:

> 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.
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20141119/82024515/attachment.html>