unification-fd 0.10.0.1 → 0.11.0

raw patch · 7 files changed

+408/−121 lines, 7 filesdep ~logictnew-uploaderPVP ok

version bump matches the API change (PVP)

Dependency ranges changed: logict

API changes (from Hackage documentation)

Files

• CHANGELOG +11/−1
• LICENSE +1/−1
• README +0/−57
• README.md +216/−0
• src/Control/Unification/Types.hs +104/−31
• src/Data/Functor/Fixedpoint.hs +46/−15
• unification-fd.cabal +30/−16

@@ -1,3 +1,14 @@+0.11.0 (2021-02-23):+    - Made Unifiable derivable whenever we have a Generic1 instance.+      (h/t/ Roman Cheplyaka)+    - Removed the Alternative/MonadPlus instances for UTerm, because+      they're unlawful.+    - Added NOINLINE for Fix's Eq and Ord instances, to avoid an+      inliner bug affecting GHC 8.0.1 and 8.0.2 (fixed in 8.0.3)+      <https://ghc.haskell.org/trac/ghc/ticket/13081>+    - HOTFIX: added logict < 0.7.1 upper bound to avoid breakage.+      Will add a proper fix in the future. For more details see,+      <https://github.com/Bodigrim/logict/issues/20#issuecomment-774528439> 0.10.0.1 (2015-05-30):     - Moved VERSION to CHANGELOG 0.10.0 (2015-03-29):@@ -10,7 +21,6 @@     - Control.Unification.Types: Completely revamped the old       UnificationFailure data type as the new UFailure data type       and Fallible type class.- 0.9.0 (2014-06-03):     - Control.Unification.Types: changed the fundeps on BindingMonad       and RankedBindingMonad so that things compile under GHC 7.8.2

@@ -10,7 +10,7 @@  === unification-fd license === -Copyright (c) 2007, 2008, 2011, 2012, 2013, 2014, wren gayle romano.+Copyright (c) 2007, 2008, 2011, 2012, 2013, 2014, 2017, 2021, wren gayle romano. ALL RIGHTS RESERVED.  Redistribution and use in source and binary forms, with or without

@@ -1,57 +0,0 @@-unification-fd-==============--This is a simple package and should be easy to install. You should-be able to use one of the following standard methods to install it.--    -- With cabal-install and without the source:-    $> cabal install unification-fd-    -    -- With cabal-install and with the source already:-    $> cd unification-fd-    $> cabal install-    -    -- Without cabal-install, but with the source already:-    $> cd unification-fd-    $> runhaskell Setup.hs configure --user-    $> runhaskell Setup.hs build-    $> runhaskell Setup.hs test-    $> runhaskell Setup.hs haddock --hyperlink-source-    $> runhaskell Setup.hs copy-    $> runhaskell Setup.hs register--The test step is optional and currently does nothing. The Haddock-step is also optional. If you see some stray lines that look like-this:--    mkUsageInfo: internal name? t{tv a7XM}--Feel free to ignore them. They shouldn't cause any problems, even-though they're unsightly. This should be fixed in newer versions-of GHC. For more details, see:--    http://hackage.haskell.org/trac/ghc/ticket/3955--If you get a bunch of type errors about there being no MonadLogic-instance for StateT, this means that your copy of the logict library-is not compiled against the same mtl that we're using. To fix this,-update logict to use the same mtl.---Portability-===========--An attempt has been made to keep this library as portable as possible,-but it does rely on some common language extensions (i.e., ones-implemented by Hugs as well as GHC) as well as a couple which are-only known to be supported by GHC. All required language extensions-are:--    Rank2Types-    MultiParamTypeClasses-    FunctionalDependencies -- Alas, necessary for type inference-    FlexibleContexts       -- Necessary for practical use of MPTCs-    FlexibleInstances      -- Necessary for practical use of MPTCs-    UndecidableInstances   -- Needed for Show instances due to two-level types------------------------------------------------------------- fin.

@@ -0,0 +1,216 @@+unification-fd+==============+[![Hackage version](https://img.shields.io/hackage/v/unification-fd.svg?style=flat)](https://hackage.haskell.org/package/unification-fd) +[![Hackage-Deps](https://img.shields.io/hackage-deps/v/unification-fd.svg?style=flat)](http://packdeps.haskellers.com/specific?package=unification-fd)+[![TravisCI Build Status](https://img.shields.io/travis/wrengr/unification-fd.svg?style=flat)](https://travis-ci.org/wrengr/unification-fd) +[![CircleCI Build Status](https://circleci.com/gh/wrengr/unification-fd.svg?style=shield&circle-token=b57517657c556be6fd8fca92b843f9e4cffaf8d1)](https://circleci.com/gh/wrengr/unification-fd)++The unification-fd package offers generic functions for single-sorted+first-order structural unification (think of programming in Prolog,+or of the metavariables in type inference)[^1][^2]. The library+*is* sufficient for implementing higher-rank type systems à la+Peyton Jones, Vytiniotis, Weirich, Shields, but bear in mind that+unification variables are the metavariables of type inference— not+the type-variables.+++## Install++This is a simple package and should be easy to install. You should+be able to use one of the following standard methods to install it.++    -- With cabal-install and without the source:+    $> cabal install unification-fd+    +    -- With cabal-install and with the source already:+    $> cd unification-fd+    $> cabal install+    +    -- Without cabal-install, but with the source already:+    $> cd unification-fd+    $> runhaskell Setup.hs configure --user+    $> runhaskell Setup.hs build+    $> runhaskell Setup.hs test+    $> runhaskell Setup.hs haddock --hyperlink-source+    $> runhaskell Setup.hs copy+    $> runhaskell Setup.hs register++The test step is optional and currently does nothing. The Haddock+step is also optional. If you see some stray lines that look like+this:++    mkUsageInfo: internal name? t{tv a7XM}++Feel free to ignore them. They shouldn't cause any problems, even+though they're unsightly. This should be fixed in newer versions+of GHC. For more details, see:++    http://hackage.haskell.org/trac/ghc/ticket/3955++If you get a bunch of type errors about there being no `MonadLogic`+instance for `StateT`, this means that your copy of the logict+library is not compiled against the same mtl that we're using. To+fix this, update logict to use the same mtl.+++## Portability++An effort has been made to make the package as portable as possible.+However, because it uses the `ST` monad and the mtl-2 package it+can't be H98 nor H2010. However, it only uses the following common+extensions which should be well supported[^3]:++* Rank2Types+* MultiParamTypeClasses+* FunctionalDependencies - Alas, necessary for type inference+* FlexibleContexts - Necessary for practical use of MPTCs+* FlexibleInstances - Necessary for practical use of MPTCs+* UndecidableInstances - Needed for Show instances due to two-level types+++## Description++The unification API is generic in the type of the structures being+unified and in the implementation of unification variables, following+the two-level types pearl of Sheard (2001). This style mixes well+with Swierstra (2008), though an implementation of the latter is+not included in this package.++That is, all you have to do is define the functor whose fixed-point+is the recursive type you're interested in:++    -- The non-recursive structure of terms+    data S a = ...++    -- The recursive term type+    type PureTerm = Fix S++And then provide an instance for `Unifiable`, where `zipMatch`+performs one level of equality testing for terms and returns the+one-level spine filled with pairs of subterms to be recursively+checked (or `Nothing` if this level doesn't match).++    class (Traversable t) => Unifiable t where+        zipMatch :: t a -> t b -> Maybe (t (a,b))++The choice of which variable implementation to use is defined by+similarly simple classes `Variable` and `BindingMonad`. We store+the variable bindings in a monad, for obvious reasons. In case it's+not obvious, see Dijkstra et al. (2008) for benchmarks demonstrating+the cost of naively applying bindings eagerly.++There are currently two implementations of variables provided: one+based on `STRef`s, and another based on a state monad carrying an+`IntMap`. The former has the benefit of O(1) access time, but the+latter is plenty fast and has the benefit of supporting backtracking.+Backtracking itself is provided by the logict package and is described+in Kiselyov et al. (2005).++In addition to this modularity, unification-fd implements a number+of optimizations over the algorithm presented in Sheard (2001)—+which is also the algorithm presented in Cardelli (1987).++* Their implementation uses path compression, which we retain.+    Though we modify the compression algorithm in order to make+    sharing observable.+* In addition, we perform aggressive opportunistic observable+    sharing, a potentially novel method of introducing even more+    sharing than is provided by the monadic bindings. Basically,+    we make it so that we can use the observable sharing provided+    by the modified path compression as much as possible (without+    introducing any new variables).+* And we remove the notoriously expensive occurs-check, replacing+    it with visited-sets (which detect cyclic terms more lazily and+    without the asymptotic overhead of the occurs-check). A variant+    of unification which retains the occurs-check is also provided,+    in case you really need to fail fast.+* Finally, a highly experimental branch of the API performs *weighted*+    path compression, which is asymptotically optimal. Unfortunately,+    the current implementation is quite a bit uglier than the+    unweighted version, and I haven't had a chance to perform+    benchmarks to see how the constant factors compare. Hence moving+    it to an experimental branch.++These optimizations pass a test suite for detecting obvious errors.+If you find any bugs, do be sure to let me know. Also, if you happen+to have a test suite or benchmark suite for unification on hand,+I'd love to get a copy.+++## Notes and limitations++[^1]: At present the library does not appear amenable for implementing+higher-rank unification itself; i.e., for higher-ranked metavariables,+or higher-ranked logic programming. To be fully general we'd have+to abstract over which structural positions are co/contravariant,+whether the unification variables should be predicative or+impredicative, as well as the isomorphisms of moving quantifiers+around. It's on my todo list, but it's certainly non-trivial. If+you have any suggestions, feel free to contact me.++[^2]: At present it is only suitable for single-sorted (aka untyped)+unification, à la Prolog. In the future I aim to support multi-sorted+(aka typed) unification, however doing so is complicated by the+fact that it can lead to the loss of MGUs; so it will likely be+offered as an alternative to the single-sorted variant, similar to+how the weighted path-compression is currently offered as an+alternative.++[^3]: With the exception of fundeps which are notoriously difficult+to implement. However, they are supported by Hugs and GHC 6.6, so+I don't feel bad about requiring them. Once the API stabilizes a+bit more I plan to release a unification-tf package which uses type+families instead, for those who feel type families are easier to+implement or use. There have been a couple requests for unification-tf,+so I've bumped it up on my todo list.+++## References++<dl>+<dt+    >Luca Cardelli (1987)</dt>+<dd><i>Basic polymorphic typechecking</i>.+    Science of Computer Programming, 8(2): 147–172.</dd>+<dt+    ><a href="http://www.cs.uu.nl/research/techreps/repo/CS-2008/2008-027.pdf"+    >Atze Dijkstra, Arie Middelkoop, S. Doaitse Swierstra (2008)</a></dt>+<dd><i>Efficient Functional Unification and Substitution</i>.+    Technical Report UU-CS-2008-027, Utrecht University.</dd>+<dt+    ><a href="http://research.microsoft.com/en-us/um/people/simonpj/papers/higher-rank/putting.pdf"+    >Simon Peyton Jones, Dimitrios Vytiniotis, Stephanie Weirich, Mark+    Shields (2007)</a></dt>+<dd><i>Practical type inference for arbitrary-rank types</i>.+    JFP 17(1). The online version has some minor corrections/clarifications.</dd>+<dt+    ><a href="http://www.cs.rutgers.edu/~ccshan/logicprog/LogicT-icfp2005.pdf"+    >Oleg Kiselyov, Chung-chieh Shan, Daniel P. Friedman, and Amr Sabry (2005)</a></dt>+<dd><i>Backtracking, Interleaving, and Terminating Monad Transformers</i>.+    ICFP.</dd>+<dt+    ><a href="http://web.cecs.pdx.edu/~sheard/papers/generic.ps"+    >Tim Sheard (2001)</a></dt>+<dd><i>Generic Unification via Two-Level Types and Parameterized Modules</i>,+    Functional Pearl. ICFP.</dd>+<dt+    ><a href="http://web.cecs.pdx.edu/~sheard/papers/JfpPearl.ps"+    >Tim Sheard and Emir Pasalic (2004)</a></dt>+<dd><i>Two-Level Types and Parameterized Modules</i>.+    JFP 14(5): 547–587.+    This is an expanded version of Sheard (2001) with new examples.</dd>+<dt+    ><a href="http://www.cs.ru.nl/~wouters/Publications/DataTypesALaCarte.pdf"+    >Wouter Swierstra (2008)</a></dt>+<dd><i>Data types à la carte</i>,+    Functional Pearl. JFP 18: 423–436.</dd>+</dl>+++## Links++* [Website](http://cl.indiana.edu/~wren/)+* [Blog](http://winterkoninkje.dreamwidth.org/)+* [Twitter](https://twitter.com/wrengr)+* [Hackage](http://hackage.haskell.org/package/unification-fd)+* [GitHub](https://github.com/wrengr/unification-fd)

@@ -2,6 +2,16 @@ {-# LANGUAGE FlexibleContexts, UndecidableInstances #-} -- Required for cleaning up Haddock messages for GHC 7.10 {-# LANGUAGE CPP #-}+-- For the generic Unifiable instances. N.B., while the lower bound+-- for 'Generic1' stuff is nominally base-4.6.0, those early versions+-- lack a 'Traversable' instance, making them useless for us. Thus,+-- the actual lower bound is GHC-8.0.2 aka base-4.9.1.0.+#if MIN_VERSION_base(4,9,1)+{-# LANGUAGE TypeOperators+           , ScopedTypeVariables+           , DefaultSignatures+           #-}+#endif -- Required more generally {-# LANGUAGE MultiParamTypeClasses            , FunctionalDependencies@@ -17,10 +27,10 @@ #endif  -------------------------------------------------------------------                                                  ~ 2015.03.29+--                                                  ~ 2017.06.21 -- | -- Module      :  Control.Unification.Types--- Copyright   :  Copyright (c) 2007--2015 wren gayle romano+-- Copyright   :  Copyright (c) 2007--2017 wren gayle romano -- License     :  BSD -- Maintainer  :  wren@community.haskell.org -- Stability   :  experimental@@ -50,17 +60,20 @@ import Prelude hiding (mapM, sequence, foldr, foldr1, foldl, foldl1)  import Data.Word               (Word8)-import Data.Functor.Fixedpoint (Fix(..))+import Data.Functor.Fixedpoint (Fix(..), unFix)+#if __GLASGOW_HASKELL__ < 810 import Data.Monoid             ((<>))-#if __GLASGOW_HASKELL__ < 710-import Data.Foldable           (Foldable(..)) #endif import Data.Traversable        (Traversable(..)) #if __GLASGOW_HASKELL__ < 710+import Data.Foldable           (Foldable(..)) import Control.Applicative     (Applicative(..), (<$>)) #endif-import Control.Applicative     (Alternative(..))-import Control.Monad           (MonadPlus(..))+#if MIN_VERSION_base(4,9,1)+-- for the generic Unifiable instances+import GHC.Generics+#endif+ ---------------------------------------------------------------- ---------------------------------------------------------------- @@ -101,8 +114,10 @@     traverse f (UVar  v) = UVar  <$> f v     traverse f (UTerm t) = UTerm <$> traverse (traverse f) t --- Does this even make sense for UTerm? It'd mean (a->b) is a--- variable type...+-- Does this even make sense for UTerm? Having variables of function+-- type for @(<*>)@ is very strange; but even if we rephrase things+-- with 'liftA2', we'd still be forming new variables as a function+-- of two old variables, which is still odd... instance (Functor t) => Applicative (UTerm t) where     pure                  = UVar     UVar  a  <*> UVar  b  = UVar  (a b)@@ -117,15 +132,24 @@     UVar  v >>= f = f v     UTerm t >>= f = UTerm ((>>= f) <$> t) --- This really doesn't make sense for UTerm...+{-+-- TODO: how to fill in the missing cases to make these work? In+-- full generality we'd need @Monoid v@ and for it to be a two-sided+-- action over @Alternative t@. instance (Alternative t) => Alternative (UTerm t) where-    empty   = UTerm empty-    a <|> b = UTerm (pure a <|> pure b)+    empty               = UTerm empty+    UVar  x <|> UVar  y =+    UVar  x <|> UTerm b =+    UTerm a <|> UVar  y =+    UTerm a <|> UTerm b = UTerm (a <|> b) --- This really doesn't make sense for UTerm... instance (Functor t, MonadPlus t) => MonadPlus (UTerm t) where-    mzero       = UTerm mzero-    a `mplus` b = UTerm (return a `mplus` return b)+    mzero                   = UTerm mzero+    UVar  x `mplus` UVar  y =+    UVar  x `mplus` UTerm b =+    UTerm a `mplus` UVar  y =+    UTerm a `mplus` UTerm b = UTerm (a `mplus` b)+-}  -- There's also MonadTrans, MonadWriter, MonadReader, MonadState, -- MonadError, MonadCont; which make even less sense for us. See@@ -177,7 +201,7 @@     -- should express the same context as if we had performed the     -- occurs-check, in order for error messages to be intelligable.     occursFailure :: v -> UTerm t v -> a-    +     -- | The top-most level of the terms do not match (according     -- to 'zipMatch'). In logic programming this should simply be     -- treated as unification failure; in type checking this should@@ -230,21 +254,21 @@ instance (Functor t) => Functor (UFailure t) where     fmap f (OccursFailure v t) =         OccursFailure (f v) (fmap f t)-    +     fmap f (MismatchFailure tl tr) =         MismatchFailure (fmap f <$> tl) (fmap f <$> tr)  instance (Foldable t) => Foldable (UFailure t) where     foldMap f (OccursFailure v t) =         f v <> foldMap f t-    +     foldMap f (MismatchFailure tl tr) =         foldMap (foldMap f) tl <> foldMap (foldMap f) tr  instance (Traversable t) => Traversable (UFailure t) where     traverse f (OccursFailure v t) =         OccursFailure <$> f v <*> traverse f t-    +     traverse f (MismatchFailure tl tr) =         MismatchFailure <$> traverse (traverse f) tl                         <*> traverse (traverse f) tr@@ -255,8 +279,11 @@ -- @Traversable@ constraint is there because we also require terms -- to be functors and require the distributivity of 'sequence' or -- 'mapM'.+--+-- /Updated: 0.11/ This class can now be derived so long as you+-- have a 'Generic1' instance. class (Traversable t) => Unifiable t where-    +     -- | Perform one level of equality testing for terms. If the     -- term constructors are unequal then return @Nothing@; if they     -- are equal, then return the one-level spine filled with@@ -264,14 +291,21 @@     -- checked.     zipMatch :: t a -> t a -> Maybe (t (Either a (a,a))) +#if MIN_VERSION_base(4,9,1)+    default zipMatch+      :: (Generic1 t, Unifiable (Rep1 t))+      => t a -> t a -> Maybe (t (Either a (a,a)))+    zipMatch a b = to1 <$> zipMatch (from1 a) (from1 b)+#endif + -- | An implementation of unification variables. The 'Eq' requirement -- is to determine whether two variables are equal /as variables/, -- without considering what they are bound to. We use 'Eq' rather -- than having our own @eqVar@ method so that clients can make use -- of library functions which commonly assume 'Eq'. class (Eq v) => Variable v where-    +     -- | Return a unique identifier for this variable, in order to     -- support the use of visited-sets instead of occurs-checks.     -- This function must satisfy the following coherence law with@@ -296,25 +330,22 @@ class (Unifiable t, Variable v, Applicative m, Monad m) =>     BindingMonad t v m | m t -> v, v m -> t     where-    +     -- | Given a variable pointing to @UTerm t v@, return the     -- term it's bound to, or @Nothing@ if the variable is unbound.     lookupVar :: v -> m (Maybe (UTerm t v))-    -    +     -- | Generate a new free variable guaranteed to be fresh in     -- @m@.     freeVar :: m v-    -    +     -- | Generate a new variable (fresh in @m@) bound to the given     -- term. The default implementation is:     --     -- > newVar t = do { v <- freeVar ; bindVar v t ; return v }     newVar :: UTerm t v -> m v     newVar t = do { v <- freeVar ; bindVar v t ; return v }-    -    +     -- | Bind a variable to a term, overriding any previous binding.     bindVar :: v -> UTerm t v -> m () @@ -357,20 +388,62 @@ class (BindingMonad t v m) =>     RankedBindingMonad t v m | m t -> v, v m -> t     where-    +     -- | Given a variable pointing to @UTerm t v@, return its     -- rank and the term it's bound to.     lookupRankVar :: v -> m (Rank t v)-    +     -- | Increase the rank of a variable by one.     incrementRank :: v -> m ()-    +     -- | Bind a variable to a term and increment the rank at the     -- same time. The default implementation is:     --     -- > incrementBindVar t v = do { incrementRank v ; bindVar v t }     incrementBindVar :: v -> UTerm t v -> m ()     incrementBindVar v t = do { incrementRank v ; bindVar v t }++----------------------------------------------------------------+-- Generic 'Unifiable' instances.++#if MIN_VERSION_base(4,9,1)+instance Unifiable V1 where+    zipMatch a _ = Just $ Left <$> a++instance Unifiable U1 where+    zipMatch a _ = Just $ Left <$> a++instance Unifiable Par1 where+    zipMatch (Par1 a) (Par1 b) = Just . Par1 $ Right (a,b)++instance Unifiable f => Unifiable (Rec1 f) where+    zipMatch (Rec1 a) (Rec1 b) = Rec1 <$> zipMatch a b++instance Eq c => Unifiable (K1 i c) where+    zipMatch (K1 a) (K1 b)+        | a == b    = Just (K1 a)+        | otherwise = Nothing++instance Unifiable f => Unifiable (M1 i c f) where+    zipMatch (M1 a) (M1 b) = M1 <$> zipMatch a b++instance (Unifiable f, Unifiable g) => Unifiable (f :+: g) where+    zipMatch (L1 a) (L1 b) = L1 <$> zipMatch a b+    zipMatch (R1 a) (R1 b) = R1 <$> zipMatch a b+    zipMatch _ _ = Nothing++instance (Unifiable f, Unifiable g) => Unifiable (f :*: g) where+    zipMatch (a1 :*: a2) (b1 :*: b2) =+        (:*:) <$> zipMatch a1 b1 <*> zipMatch a2 b2++instance (Unifiable f, Unifiable g) => Unifiable (f :.: g) where+    zipMatch (Comp1 fga) (Comp1 fgb) =+        Comp1 <$> (traverse step =<< zipMatch fga fgb)+        where+        -- TODO: can we avoid mapping 'Left' all the way down?+        step (Left  gx)       = Just (Left <$> gx)+        step (Right (ga, gb)) = zipMatch ga gb+#endif  ---------------------------------------------------------------- ----------------------------------------------------------- fin.

@@ -2,6 +2,7 @@ {-# LANGUAGE UndecidableInstances #-} -- For 'build' and 'hmap' {-# LANGUAGE Rank2Types #-}+{-# LANGUAGE CPP #-}  -- Unfortunately GHC < 6.10 needs -fglasgow-exts in order to actually -- parse RULES (see -ddump-rules); the -frewrite-rules flag only@@ -18,7 +19,8 @@  -- NOTE #1: on GHC >= 7.8 we need to eta expand rules to avoid a -- warning about the fact that the rule may never fire because (.)--- might inline first...+-- might inline first. On GHC >= 8.0 it's even more aggressive about+-- these warnings.  {-# OPTIONS_GHC -Wall -fwarn-tabs #-} ----------------------------------------------------------------@@ -52,7 +54,7 @@ module Data.Functor.Fixedpoint     (     -- * Fixed point operator for functors-      Fix(..)+      Fix(..), unFix     -- * Maps     , hmap,  hmapM     , ymap,  ymapM@@ -84,8 +86,15 @@ -- and operations over them without the type checker complaining -- about infinite types. The 'Show' instance doesn't print the -- constructors, for legibility.-newtype Fix f = Fix { unFix :: f (Fix f) }+newtype Fix f = Fix (f (Fix f)) +-- Must not phrase this as a record field, or else we can't give+-- it an inline pragma, which in turn means some of the rules will+-- complain about it being inlined too soon.+unFix :: Fix f -> f (Fix f)+unFix (Fix f) = f+{-# INLINE [0] unFix #-}+ -- This requires UndecidableInstances because the context is larger -- than the head and so GHC can't guarantee that the instance safely -- terminates. It is in fact safe, however.@@ -95,6 +104,12 @@ instance (Eq (f (Fix f))) => Eq (Fix f) where     Fix x == Fix y  =  x == y     Fix x /= Fix y  =  x /= y+-- BUGFIX: Inlining causes a code explosion on GHC 8.0.1 and 8.0.2, but+-- will be fixed in 8.0.3. <https://ghc.haskell.org/trac/ghc/ticket/13081>+#if __GLASGOW_HASKELL__ == 800+    {-# NOINLINE (==) #-}+    {-# NOINLINE (/=) #-}+#endif  instance (Ord (f (Fix f))) => Ord (Fix f) where     Fix x `compare` Fix y  =  x `compare` y@@ -104,6 +119,17 @@     Fix x <  Fix y         =  x <  y     Fix x `max` Fix y      =  Fix (max x y)     Fix x `min` Fix y      =  Fix (min x y)+-- BUGFIX: Inlining causes a code explosion on GHC 8.0.1 and 8.0.2, but+-- will be fixed in 8.0.3. <https://ghc.haskell.org/trac/ghc/ticket/13081>+#if __GLASGOW_HASKELL__ == 800+    {-# NOINLINE compare #-}+    {-# NOINLINE (>) #-}+    {-# NOINLINE (>=) #-}+    {-# NOINLINE (<=) #-}+    {-# NOINLINE (<) #-}+    {-# NOINLINE max #-}+    {-# NOINLINE min #-}+#endif  ---------------------------------------------------------------- @@ -115,8 +141,9 @@     -- == cata (Fix . eps) -- But the anamorphism is a better producer.  {-# RULES-"hmap id"-        hmap id = id+-- Alas, rule won't fire because 'id' may inline too early.+-- "hmap id"+--        hmap id = id  -- cf., NOTE #1 "hmap-compose"@@ -133,8 +160,9 @@ hmapM eps = anaM (eps . unFix)  {-# RULES-"hmapM return"-    hmapM return = return+-- Alas, rule won't fire because 'return' may inline too early.+-- "hmapM return"+--     hmapM return = return  -- "hmapM-compose" --     forall eps eta.@@ -150,8 +178,9 @@ ymap f = Fix . fmap f . unFix  {-# RULES-"ymap id"-        ymap id = id+-- Alas, rule won't fire because 'id' may inline too early.+-- "ymap id"+--         ymap id = id  -- cf., NOTE #1 "ymap-compose"@@ -167,8 +196,9 @@ ymapM f = liftM Fix . mapM f . unFix  {-# RULES-"ymapM id"-        ymapM return = return+-- Alas, rule won't fire because 'return' may inline too early.+-- "ymapM id"+--         ymapM return = return  -- "ymapM-compose" --     forall f g.@@ -211,7 +241,7 @@ -- cf., NOTE #1 "cata-compose"     forall (eps :: forall a. f a -> g a) phi x.-        cata phi (cata (Fix . eps) x) = cata (phi . eps) x+        cata phi (cata (\y -> Fix (eps y)) x) = cata (phi . eps) x     #-}  -- We can't really use this one because of the implication constraint@@ -235,8 +265,9 @@  -- TODO: other rules for cataM {-# RULES-"cataM-refl"-        cataM (return . Fix) = return+-- Alas, rule won't fire because 'return' may inline too early.+-- "cataM-refl"+--         cataM (return . Fix) = return     #-}  @@ -279,7 +310,7 @@ -- cf., NOTE #1 "ana-compose"     forall (eps :: forall a. f a -> g a) psi x.-        ana (eps . unFix) (ana psi x) = ana (eps . psi) x+        ana (\y -> eps (unFix y)) (ana psi x) = ana (eps . psi) x     #-}  -- We can't really use this because of the implication constraint

@@ -1,19 +1,21 @@ ------------------------------------------------------------------- wren gayle romano <wren@community.haskell.org>   ~ 2015.05.30+-- wren gayle romano <wren@community.haskell.org>   ~ 2021.02.23 ---------------------------------------------------------------- --- By and large Cabal >=1.2 is fine; but >= 1.6 gives tested-with:--- and source-repository:.-Cabal-Version:  >= 1.6+-- Hackage requires us to require Cabal-Version >=1.10; otherwise+-- things should be backwards compatible to >=1.2 (with the exception+-- of the tested-with and source-repository fields which were added+-- in >=1.6).+Cabal-Version:  >= 1.10 Build-Type:     Simple  Name:           unification-fd-Version:        0.10.0.1+Version:        0.11.0 Stability:      experimental-Homepage:       http://code.haskell.org/~wren/+Homepage:       https://wrengr.org/software/hackage.html Author:         wren gayle romano-Maintainer:     wren@community.haskell.org-Copyright:      Copyright (c) 2007--2015 wren gayle romano+Maintainer:     winterkoninkje@gmail.com+Copyright:      Copyright (c) 2007--2021 wren gayle romano License:        BSD3 License-File:   LICENSE @@ -24,13 +26,21 @@ -- No longer compiles with GHC-6.12.1 since Data.Monoid does not -- export (<>) in Control.Unification.Types. The backwards compatibility -- is not considered worth adding CPP noise...+-- Last I checked, it also worked with 7.6.1 and 7.8.2; but I don't+-- have TravisCI enforcing those. Tested-With:-    GHC == 7.6.1, GHC == 7.6.3, GHC == 7.8.2+    GHC == 7.4.2, GHC == 7.6.3, GHC == 7.8.4, GHC == 7.10.3, GHC == 8.0.2,+    GHC == 8.2.1, GHC == 8.2.2,+    GHC == 8.4.1, GHC == 8.4.2, GHC == 8.4.3, GHC == 8.4.4,+    GHC == 8.6.1, GHC == 8.6.2, GHC == 8.6.3, GHC == 8.6.4, GHC == 8.6.5,+    GHC == 8.8.1, GHC == 8.8.2, GHC == 8.8.3, GHC == 8.8.4,+    GHC == 8.10.1, GHC == 8.10.2, GHC == 8.10.3+ Extra-source-files:-    AUTHORS, README, CHANGELOG+    AUTHORS, README.md, CHANGELOG Source-Repository head-    Type:     darcs-    Location: http://community.haskell.org/~wren/unification-fd+    Type:     git+    Location: https://github.com/wrengr/unification-fd  ---------------------------------------------------------------- Flag base4@@ -47,6 +57,8 @@  ---------------------------------------------------------------- Library+    -- With Cabal-Version: >= 1.10, the Default-Language field is now required.+    Default-Language: Haskell98     Hs-Source-Dirs:  src     Exposed-Modules: Data.Functor.Fixedpoint                    , Control.Monad.State.UnificationExtras@@ -59,8 +71,10 @@                    , Control.Unification.Ranked                    , Control.Unification.Ranked.STVar                    , Control.Unification.Ranked.IntVar-    -    Build-Depends:   logict       >= 0.4++                   -- logict 0.7.1 breaks the build (for now); cf.,+                   -- <https://github.com/Bodigrim/logict/issues/20#issuecomment-774528439>+    Build-Depends:   logict       >= 0.4 && < 0.7.1                    -- Require a version of base with Applicative.                    -- We refuse to do without it any longer.                    , base         >= 2.0@@ -69,12 +83,12 @@                    -- StateT. And we want stuff from monads-fd, so                    -- we can't just fail over to the older mtl.                    , mtl          >= 2.0-    +     if flag(base4)         Build-Depends: base >= 4 && < 5     else         Build-Depends: base < 4-    +     if flag(splitBase)         Build-depends: base >= 3.0, containers     else