Add Bifunctor instance for PolyDiff

[jonathanlking]

The following Bifunctor instance would be very handy:

instance Bifunctor PolyDiff where
  bimap f _ (First a) = First (f a)
  bimap _ g (Second b) = Second (g b)
  bimap f g (Both a b) = Both (f a) (g b)

I appreciate supporting base >= 3 && <= 6 makes things slightly more complicated, as Bifunctor is only available since base-4.8.0.0. The two options I can think of are using a CPP macro, or increasing the minimum bounds of base.

I'm happy to open a PR with either approach (or something else!).

[ddssff]

I think we can abandon base older than 4.8.0.0. If someone complains I'll welcome a PR with ifdefs.

[ddssff]

Have you noticed any slowness in the diff function? I may have seen this when running in the browser via ghcjs.

[jonathanlking]

Have you noticed any slowness in the diff function? I may have seen this when running in the browser via ghcjs.

We're only using the getGroupedDiff function (on GHC 8.8.4 targeting x86) and it's only used as part of tests.
I haven't noticed it being particularly slow, but that said these tests are not something that we've profiled, as they're fast enough.

[ddssff]

I can do the CPP.

[Bodigrim]

@ddssff did you test it with GHC 9.6? I suspect instance Functor is missing.

[ddssff]

I don't have access to ghc-9.6. Stuck on 8.10.

[Bodigrim]

Sorry, I’m AFK until the next week. If you wish, once back home, I can generate a GitHub Actions CI setup with haskell-ci covering a range of GHCs up to 9.6.

[Bodigrim]

@ddssff could you possibly make a release some time soon?

[ddssff]

Hackage upload? Will do.

[Bodigrim]

Yes, please.

[ddssff]

Does O(ND) in the title refer to time or space complexity?

[Bodigrim]

Time is O(ND) and space is O(D^2).

I'm not sure "O(ND)" is terribly helpful as a top-level package description without explaining what D refers to. It might be helpful to bring Cabal "description:" field in line with the module header:

Diff/Diff.cabal

Lines 3 to 4 in 026aef2

	synopsis: O(ND) diff algorithm in haskell.
	description: Implementation of the standard diff algorithm, and utilities for pretty printing.

Diff/src/Data/Algorithm/Diff.hs

Lines 10 to 14 in 026aef2

	-- This is an implementation of the diff algorithm as described in
	-- \"An \( O(ND) \) Difference Algorithm and Its Variations (1986)\"
	-- <http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.4.6927>.
	-- For inputs of size \( O(N) \) with the number of differences \( D \)
	-- it has \( O(ND) \) time and \( O(D^2) \) space complexity.

[ddssff]

How about this:

synopsis:            Diff algorithm in pure Haskell
description:         Implementation of the standard diff algorithm, and utilities for pretty printing.  Time complexity is proportional to N (input length) & D (number of differences).  Space complexity is D^2.

[Bodigrim]

Thanks for a quick turnaround with a release, really much appreciated.

How about this:

Looks great! And today I learned that one can edit package description via revision :)

[ddssff]

I'm thinking of removing 'getContextDiffOld' - I can't see how it could be useful to anyone.

…

On Sun, Oct 22, 2023 at 2:56 PM ˌbodʲɪˈɡrʲim ***@***.***> wrote: Thanks for a quick turnaround with a release, really much appreciated. How about this: Looks great! And today I learned that one can edit package description via revision :) — Reply to this email directly, view it on GitHub <#2 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AA6M6SNQYYBIVRRKD5SFC23YAWI7LAVCNFSM6AAAAAARTL44PKVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMYTONZUGIYDSNRYGA> . You are receiving this because you were mentioned.Message ID: ***@***.***>

[Bodigrim]

I'm thinking of removing 'getContextDiffOld' - I can't see how it could be useful to anyone.

Makes sense to me.