Use Fix from data-fix package

[phadej]

trafficstars

A proposal to use data-fix's Fix in unification-fd.

data-fix is somewhat widely used, and the next recursion-schemes will move to use it as well. It would be great if unification-fd also moved to use the same type.

There are small changes to instances. I'd like to change UTerm's Show instance to use Show1 type (and maybe Eq and Ord instances, like they are written for Free in https://hackage.haskell.org/package/free-5.1.3/docs/Control-Monad-Free.html#t:Free)

[phadej]

ping

[wrengr]

Sorry for the long delay. I'll review this in more detail shortly

[phadej]

ping. there is conflict now, and I'll fix if this idea is accepted first.

[phadej]

ping

[phadej]

ping again.

[phadej]

This package seems unmaintained. That's pity, it's a very nice package.

[wrengr]

I just took a look at the latest version of data-fix (0.3.4), and most of my historical complaints against the library have been resolved, but there are a few infelicities I'm still concerned with:

• data-fix only supports ghc >= 8.6.1 (September 2018). This isn't unreasonable, and it's something I'm willing to live with.
• data-fix doesn't seem to have direct analogues of several functions. I can always adapt my definitions to use data-fix's datatype instead of my own, but maintaining such extensions does complicate matters (especially if I pursue trying to get the functions incorporated into data-fix).
  • hmapM (which they'd name hoistFixM) — which is certainly an oversight
  • ymap, ymapM, ycata, ycataM — I'm not sure how often users actually want/need these
  • build — see the next bullet point
• My current implementation has several rewrite rules to perform fusion of the various cata/ana functions; whereas data-fix does not. I don't have any good benchmarks laying around to show how much this matters, but since this could cause significant regressions for downstream users it's my primary concern re switching to data-fix.

[wrengr]

I just created a new branch to try switching things over: https://github.com/wrengr/unification-fd/tree/use_datafix So far CI seems to accept it, though I haven't tried testing any programs using the library yet

[phadej]

AFAICT,

hmapM :: (Functor f, Traversable g, Monad m) => (forall a. f a -> m (g a)) -> Fix f -> m (Fix g)
hmapM f = refoldM (return . Fix) (f . unFix)

refoldM is not Fix specific, and more flexible.

--

Re, build. As a user of unification-fd I never cared about these rewrites. Nor unification-fd itself seems to use anything ana or cata. I'd be really surprised if there are users of unification-fd just for Data.FixedPoint as in my experience people rather tend to roll their own newtype Fix than depend on anything.

That said, my personal opinion is that rewrite framework in GHC is not reliable, such fusion is at most "nice to have" but cannot relied upon if fused performance is hard requirement (even list fusion is brittle). Those are not guaranteed optimisations, which don't cause compilation failure (nor even a warning) in case of no success.

[phadej]

Taking a look at build. It seems as working with Mu:

build      :: Functor f => (forall r. (f r -> r) -> r) -> Fix f
newtype Mu f = Mu { unMu :: forall a. (f a -> a) -> a }

{-# RULES
"build/cata" [1]
    forall (phi :: f a -> a) (g :: forall r. (f r -> r) -> r).
        cata phi (build g) = g phi
 -}

foldMu :: (f a -> a) -> Mu f -> a
foldMu f (Mu mk) = mk f

I.e. instead of relying on rewrite rules, users can be explicit by using Mu.

Similarly Nu may be useful when the end of chain is ana.