haskellari / these Goto Github PK

Hi again, I realize you already have a function named toThese unfortunately, so this would be a breaking change, but I do believe what I'm proposing is the proper move all other things considered equal. If you'll notice in similar data types, such as Smash, one has the case-analysis/eliminator smash and then the toSmash and fromSmash functions. Similarly for Wedge, one has the case-analysis/eliminator wedge and then the toWedge and fromWedge. And soon enough there should be the same for Can, they have the case-analysis/eliminator and then once they bring in the These type they could then in theory write the missing toCan and fromCan:

-- Data.Can
toCan ∷ Maybe (These a b) → Can a b
toCan = maybe Non (these One Eno Two)

fromCan ∷ Can a b → Maybe (These a b)
fromCan = can Nothing (Just . This) (Just . That) (curry (Just . uncurry These))

By the way I'm just speculating, I don't speak on behalf of their project, so I hope I'm not giving that impression!
Back on topic, These already has the case-analysis/eliminator of course, and I think it could also use:

-- Data.These
toThese   ∷ Either (Either a b) (a, b) → These a b
toThese   = either (either This That) (uncurry These)

fromThese ∷ These a b                  → Either (Either a b) (a, b)
fromThese = these (Left . Left) (Left . Right) (curry (Right . uncurry (,)))

Now I am aware that the Either makes it so that these functions could be written in multiple ways but my argument is that the case-analysis has always been done in the order in which the data type is defined (c.f. maybe, bool, either, etc.), so it would make sense to use the above definitions because they are in keeping with this tradition because as you know These is defined:

data These a b = This a | That b | These a b

So it makes sense to have a normal form with the sum first and the product after. At any rate, sorry for the rant; it is okay if you don't like my suggestion I won't be offended if you close the ticket and move on, but I decided to share just in case you are interested, in which case let me know if you would like a pull request.

Thank you for your time and consideration. And thanks again for all your hard work on this excellent package!

I'm porting Data.These over to PureScript. I was looking at the code and thought these instances looked strange:

https://github.com/isomorphism/these/blob/3c3dc27b4458c640b777c7f721418cd555a9db67/Data/These.hs#L207-L216

instance Foldable (These a) where
    foldr f z = foldr f z . justThat

instance Traversable (These a) where
    traverse _ (This a) = pure $ This a
    traverse f (That x) = That <$> f x
    traverse f (These a x) = These a <$> f x
    sequenceA (This a) = pure $ This a
    sequenceA (That x) = That <$> x
    sequenceA (These a x) = These a <$> x

Firstly I don't understand why Foldable is only defined for the That case. Seems like it should also have the These case, just because it seems more useful.

But other than intuition, the Foldable instance is not consistent with the Traversable instance. You can observe this:

import Data.These
import Data.Foldable
import Data.Traversable

-- ""
example1 :: String
example1 = foldMap id (These "Hello" "World")

-- "World"
example1 :: String
example1 = foldMapDefault id (These "Hello" "World")

I think a correct instance would look like:

instance Foldable (These a) where
    foldr f z (That x)    = x `f` z
    foldr f z (These _ x) = x `f` z
    foldr _ z _           = z

Control.Monad.join (I take it..) is mentioned in the laws required of Align instances:

• https://github.com/isomorphism/these/blob/master/Data/Align.hs#L95

It seems illegal, since Monad isn't required for Align, and so the semantics are unclear.

(..to say nothing of the Bifunctor law..)

...and wants the type of dictate to be (MonadChronicle c m, Default a) => c -> m a, that is. (Bug reports regarding taste in type classes should be filed against @dmwit rather than these.)

Conversation on IRC starts here and continues here.

For all that I consider the Default class to be rather dubious, after thinking about it this particular scenario does make sense in the context of using MonadChronicle. Not to mention that, as far as I know, making this change is supported by 100% of the people who actually use MonadChronicle. As such, I'm leaning toward making the change in some fashion, though I'd slightly prefer to add a new function rather than change the existing dictate.

It feels a bit silly to add a dependency on another package for just this one thing, but eh, not really a big deal.

I'll do something about this once I've finished self-bikeshedding over the name issue, creating this issue so I don't forget and in case anyone wants to offer opinions.

There are various places in this module where it might be useful to have padding for containers that happen to contain Monoidal values be automatically defaulted by mempty.

I'm particularly thinking of something like:
padZipEmpty :: (Semialign f, Monoid a, Monoid b) => f a -> f b -> f (a,b)
padZipWithEmpty :: (Semialign f, Monoid a, Monoid b) => (a -> b -> c) -> f a -> f b -> f c

Perhaps it might also be worth exposing an explicit default version too:
padZipDef :: (Semialign f) => a -> b -> f a -> f b -> f (a,b)

Let me know what you think. I'm happy to implement this and send a PR if you like the idea.

Instead of the current instances of Align for Map and IntMap, which require fmapping over each map and then using an unsafe unionWith to merge them, the mergeWithKey function should be used:

instance (Ord k) => Align (Map k) where
    nil = Map.empty
    alignWith fn = Map.mergeWithKey (\_ a b -> Just $ fn $ These a b) (fmap (fn . This)) (fmap (fn . That)) -- and similarly for IntMap

mergeWithKey is inlined after the three function arguments are given, thus providing opportunities for optimization; in addition, each subtree in the map is only traversed once instead of twice, and there's no chance of an oops happening.

A common use-case is having default values while zipping (with Align). This way one can provide functions that are analogous to zip and zipWith. E.g., with these definitions:

alignDef :: Align f => a -> b -> f a -> f b -> f (a, b)
alignDef da db = alignWith (fromThese da db)

alignDefWith :: Align f => a -> b -> (a -> b -> c) -> f a -> f b -> f c
alignDefWith da db f = alignWith g
  where
    g = these (flip f db) (f da) f

Then you can write:

> alignDef 0 'x' [1..10] "a"
[(1,'a'),(2,'x'),(3,'x'),(4,'x'),(5,'x'),(6,'x'),(7,'x'),(8,'x'),(9,'x'),(10,'x')]
> alignDefWith 0 0 (+) [1..10] [2, 3]
[3,5,3,4,5,6,7,8,9,10]

Let me know whether you are interested or want to change the naming. Then I can create a pull request.

I was using These to do a relational join on sorted lists:

[(a, b)] -> [(a, c)] -> [(a, These b c)]

But then to do a multi-way join, I needed this:

[[(a, b)]] -> [(a, NonEmpty b)]

Given that the first signature is the 'base case' for the latter, I think a function, something like:

These a a -> NonEmpty a

makes sense.

There's a request to add @chrisdone's shell-conduit package to Stackage, which depends on these. However, these has the following restrictive upper bounds:

• profunctors-4.2.0.1 -- >=3 && <4.1
• semigroupoids-4.2 -- >=1.0 && <4.1

Would it be possible to relax these upper bounds?

In the process of porting Align and its docs to PureScript, I found myself wanting to use the existing language of lax monoidal functors to succinctly specify the laws. It doesn't get all of the laws, but I feel like it should be possible to simplify things a bit this way (at the expense of accessibility for beginners). In any case, it seemed worth discussing more broadly, and hopefully an issue is a decent place for it.

Align looks like a symmetric lax monoidal functor from (*, These) to (*, (,)) with some additional laws. I wonder if the extra laws could be captured using similar language?

Sorry if this is the wrong place or if this is already known, in which case please do close this.

Based on the conversation on pull request #27 I'm wondering if it ever makes sense to leave the These constructors introduced by an Align instance unevaluated, since the reasoning involved isn't specific to HashMap at all.

At very least we should probably use the strict version for Data.Map and Data.IntMap, which have "strict" modules with a shared base type like HashMap does. Pull request #29 from @phadej covers the first, but not the second.

For other types we'd have to seq the results manually, but other than cluttering the code up slightly it seems strictly (heh) better than creating more thunks.

The versions 0.4 and 0.4.1 also need an upper bound on vector <0.11, since that version introduced changes that break these. 0.4.2 already has that bound, but the cabal solver will just choose 0.4 or 0.4.1 if they don't also get the bound. See http://matrix.hackage.haskell.org/package/these

@isomorphism: Can you turn on Travis-CI? The .travis.yaml already exists!

Here's a short guide: http://docs.travis-ci.com/user/getting-started/#To-get-started-with-Travis-CI%3A

these is a wonderful library, but has quite a large dependency footprint. Would you consider publishing a these-core with only the main data type and base-based typeclass instances? these could then depend on these-core, and expose the rest of its machinery.

I'm aware that data-or exists, but it is missing certain instances that a modern Haskeller would expect. I'm trying to get it patched as well, but the maintainer (and the repo!) might be "lost to time". I will update this thread if the data-or situation changes.

If manpower is an issue, I can put in the work myself to create these-core, and then link these to it. Thoughts?

The type of Data.Align.malign could be generalized from

(Align f, Monoid a) => f a -> f a -> f a

to

(Align f, Semigroup a) => f a -> f a -> f a

(This was pointed out by @enobayram on r/haskell)

A downside to this generalization would be the loss of the great mnemonic in the function name ("Monoid-align"). Maybe a renaming to "salign" should even be considered but I don't think that's worth it.

WRT dependencies, the generalization would mean that the previously transitive dependency on the semigroups package (via semigroupoids) would now turn into a direct dependency.

Also in a separate Data.These.Combinators could go combinators which are derivatives, e.g. catThese etc.

This way Data.These interface could stay small.

I find the Align laws are insufficient. The current laws

(`align` nil) = fmap This
(nil `align`) = fmap That
join align = fmap (join These)
align (f <$> x) (g <$> y) = bimap f g <$> align x y
alignWith f a b = f <$> align a b

Do not eliminate this unwanted implementation for [] for Map k.

align x y
   | Map.null y = This <$> x
   | Map.null x = That <$> y
   | otherwise = Map.intersectionWith These x y

(Edited to clarify the relation between this counterexample and argument below)

One idea is to employ Filterable as a superclass, and include a law

align (mapMaybe f x) (mapMaybe g y) = mapMaybe (productMaybe f g)  (align x y)
  where
     productMaybe :: (a -> Maybe a') -> (b -> Maybe b') -> These a b -> Maybe (These a' b')
     productMaybe f g (This a) = This <$> f a
     productMaybe f g (That b) = That <$> g b
     productMaybe f g (These a b) = alignMaybe (f a) (g b)
     
     alignMaybe :: Maybe a -> Maybe b -> Maybe (These a b)

This law eliminates the counterexample above. Also, it matches the explanation given in the doc: Align is lax monoidal functor w.r.t Kleisli Maybe's cartesian monoidal structure.

But there is a problem. [] is not a lawful instance anymore. This is probably unacceptable.

I just wrote this for a project at work. Not sure if other people need this often, but I figured it would be worth considering adding to the package:

theseFromMaybes :: Maybe a -> Maybe b -> Maybe (These a b)
theseFromMaybes Nothing Nothing = Nothing
theseFromMaybes (Just a) Nothing = Just (This a)
theseFromMaybes Nothing (Just b) = Just (That b)
theseFromMaybes (Just a) (Just b) = Just (These a b)

Can it be made lawful directly. Why if not? Add to documentation

Docs for malign promise that it will be deprecated after Semigroup became a superclass of Monoid.

After updating our package set in NixOS to the latest version of vector, we can no longer compile these: http://packdeps.haskellers.com/feed?needle=these.

I could install the library with GHC 9.0.1 for only bumping the upper bound for base. Could you make a revision on Hackage please.

Blocking agda/agda#4955 and haskellari/strict#26.

I'd like to add instances for These for classes from packages: binary, aeson, deepseq and universe. @isomorphism is it ok to add them as dependencies?

Because ReaderT e is pretty much Compose ((->) e), there should be derived Semialign, Zip, Repeat, and Unzip instances for it. Also, even though Compose ((->) e) doesn't have an Align instance, nil = ReaderT (const nil) should be law-abiding.

Additionally, MaybeT m is isomorphic to Compose m Maybe, so it also would get Semialign, Align, Zip, Repeat, and Unzip instances. There might also be a possible law-abiding Unalign instance, but I'm not sure right this moment.

At, the moment, there is a few way to the get the this or that bit of a That or a This (ie These a b -> Maybe a and These a b -> Maybe b) but none of them works for a These : one could expect fromThis (These "a" "b") to return Just "a" but it returns instead Nothing. This somehow makes sense, but is counter intuitive if you see These as a super (Maybe a, Maybe b). Moreover, unless I'm missing something, there is no simple way to get this behavior. The "simplest" I found is to use unalign.

Could you bump the upper bounds (or remove them) to allow newer versions of these packages:

bifunctors: needed (>=0.1 && <4.2), but 4.2.1 found
profunctors: needed (>=3 && <4.1), but 4.4.1 found
semigroupoids: needed (>=1.0 && <4.1), but 4.3 found
semigroups: needed (>=0.8 && <0.16), but 0.16.2.2 found

And no build reports, failed or otherwise.

What's up with that?

Hello!
Thank you all again for all your work on this excellent package.
I wrote instances for universe's Universe and Finite classes for the These a b type.
If you are interested in having support for these instances included then please let me know, I would gladly make a PR.

The code is pretty straight forward.

import Control.Applicative  (liftA2)
import Data.Tagged          (Tagged (..), retag)
import Data.Universe        (Finite (..), Universe (..))
import Numeric.Natural      (Natural)

toThese :: Either (Either a b) (a, b) -> These a b
toThese = either (either This That) (uncurry These)

instance (Universe a, Universe b) => Universe (These a b) where
  universe :: [These a b]
  universe = fmap toThese universe

instance (Finite a, Finite b) => Finite (These a b) where
  -- a + b + ab
  cardinality :: Tagged (These a b) Natural
  cardinality = liftA2 (\a b -> a + b + a * b) (retag (cardinality :: Tagged a Natural))
                                               (retag (cardinality :: Tagged b Natural))
  universeF :: [These a b]
  universeF = fmap toThese universeF

If you are not comfortable with the name toThese then it can simply be inlined to avoid giving it a name, or I am open to suggestions for a different name :)

Here are some example usages in GHCi:

λ> mapM_ print (universeF @ (These () Bool))
This ()
That False
That True
These () False
These () True
λ> cardinality @ (These () Bool)
Tagged 5

If you are not interested then I won't take offense and please close the ticket; any feedback is certainly welcomed. Thank you for your time and consideration.

Hi
I think a mergeTheseWith function would be usefull. It would be either

mergeTheseWith :: (a -> b) -> (b -> b -> b) -> These a  a -> a
mergeTheseWith f op t = mergeThese op $ mapThese f f t)

or more generic

mergeTheseWith :: (a -> c) -> (b -> c) -> (c -> c -> c) -> These a b -> c
mergeTheseWith l r op t = mergethese op $ map These l r t

If you like the idea, I'm happy to send a pull request.

http://hackage.haskell.org/package/data-or

What's the same and what's different etc.

I'll do it myself if someone isn't faster. Please contribute!

NonEmptyMap is in http://hackage.haskell.org/package/non-empty/docs/Data-NonEmpty-Map.html, and hopefully soon in containers itself via haskell/containers#616 if I may self-plug. We cannot zip two non empty maps because if they have no keys in common we must end up with an empty map. Put in SQL terms, we only have "outer join", not "inner join".

ChronicleT seems like it can be made a valid MonadWriter, without relying on the underlying monad.

If it is not, it should be documented.

My personal intuition suggests that most instances should be "strict in the leaves, lazy in the spine" like the [] instance. However, most of them seem to be lazy all over the place.

NB: Data.Sequence.Seq actually needs its unzip to be lazy in the leaves in order to be lazy in the spine. If it tried to be strict in the leaves but lazy in the spine, it would end up being strict in part of the spine, which would break the abstraction barrier. sigh.

Hi, thank you for your very useful package and all the hard work you put into it. I have minor suggestion to add an equivalence relation (Equivalence from Data.Functor.Contravariant)

import Data.Functor.Contravariant (Equivalence (..))

eqThese :: Equivalence (These a b)
eqThese = Equivalence equivalence
  where
    equivalence :: These a b -> These a b -> Bool
    equivalence (This  _  ) (This  _  ) = True
    equivalence (That    _) (That    _) = True
    equivalence (These _ _) (These _ _) = True
    equivalence _           _           = False

I've made similar equivalence relations for other types (e.g. such as Smash, Can, Wedge, and have found them quite useful [1]). If you are interested I can make a pull request. If you don't see the need to add this for what ever reason I won't take offense.

Please let me know what you think. I hope you have a great day!

[1] emilypi/smash#23

Edit removed UnicodeSyntax and updated naming convention to match the one now used by smash.

http://matrix.hackage.haskell.org/package/these

• Should we make revisions constraining base to exclude broken builds
• Do we care about GHC-7.0 support?

http://hackage.haskell.org/package/these-0.4.2/docs/Data-Align.html:

 join align = fmap (join These)

whereas

align :: f a -> f b -> f (These a b)

join is known as an operation for monads: Monad m => m m a -> m a.

I don't understand how this applies to align.

Could you please clarify this?

Consider the following data type:

-- | Either a, or b, or both a and b
data SearchResult a b = Scanned a | Found b | ScannedAndFound a b

-- | Accumulate 'a's from left to right, until one 'b' is found
instance Semigroup a => Semigroup (SearchResult a b) where
  ScannedAndFound a b <> _ = ScannedAndFound a b
  Found b <> _ = Found b
  Scanned a <> Scanned a' = Scanned (a <> a')
  Scanned a <> Found b = ScannedAndFound a b
  Scanned a <> ScannedAndFound a' b = ScannedAndFound (a <> a') b

The type definition is identical to These, but the Semigroup semantics differ. Do you think it could/should be integrated to these library, e.g. as a newtype over These ?

Rationale: as the name suggests, this type is useful in search algorithms to return both the search result and a semigroup of traversed items.

https://github.com/isomorphism/these/blob/5cdee44edb3321e2b270a18e545cdd089321c253/these/src/Data/These.hs#L258

I was puzzled to see that This a <*> This b == This a and not This $ a <> b, but These a f <> These b x = These (a <> b) $ f x. Wouldn't it be more symmetric if This would also use the semigroup, or if These wouldn't? Also confusingly, This a <*> This b /= This a <> This b.

I can't really find an Applicative or Monad law this is breaking, or a proof that all laws hold (quite a bit of work with so many cases). But still I find it a noteworthy unexpected feature that might be good to document. What's the reason for this particular instance?

I committed the change to the these.cabal, but as I'm not a Hackage maintainer, cannot do the upload / revision. Tests pass ok.

There is no reference to Foldable in the default definitions, so is there a more fundamental reason?

The reason I ask is because I have a data type that appears to fit the Crosswalk shape, but its Foldable instance is, frankly, not meaningful, and I would prefer not to implement it. However, I wonder if this also makes the Crosswalk instance bogus.

Reflex provides a function Data.Map.Misc.diffMap :: (Ord k, Eq v) => Map k v -> Map k v -> Map k (Maybe v) which compares two Maps and returns a Map with all the updates.

Looking at its source, there is nothing Map-specific going on, and it could be generalised (using Filterable from witherable) to:

diffAlign :: (Semialign f, Filterable f, Eq a) => f a -> f a -> f (Maybe a)

I want to write this and upload it somewhere. Reflex also provides a diffMapNoEq variant that assumes anything present in the second Map is an update. There is a third unwritten variant that is left-biased, and I'd like to write both of these too. Neither filterable nor semialign depend on each other, but filterables dependency footprint is small (it would add one transitive dependency: base-orphans).

Would you accept a PR to add these functions and a dependency on filterable, or should I stand up a semialign-diff package?

It occurred to me that Align is a significant use case--possibly the most significant use case--for These, but nothing in the package description and almost nothing outside of Data.Align even mentions it.

Considering that variants on the question "how to zip with padding" come up semi-regularly on SO etc., this should probably be rectified so that Align gets more visibility.

The law labeled "functoriality" in the Semialign class is a free theorem.

Here is the law as written:

f1, f2 :: Semialign f => (a -> c) -> (b -> d) -> f a -> f b -> f (These c d)
f1 f g x y = align (f <$> x) (g <$> y)
f2 f g x y = bimap f g <$> align x y

-- "Functoriality"
-- f1 = f2

Uncurry the arguments:

f1, f2 :: Semialign f => (a -> c) -> (b -> d) -> (f a, f b) -> f (These c d)
f1 f g (x, y) = align (f <$> x) (g <$> y)
f2 f g (x, y) = bimap f g <$> align x y

Eta reduce:

f1, f2 :: Semialign f => (a -> c) -> (b -> d) -> (f a, f b) -> f (These c d)
f1 f g = uncurry align . bimap (fmap f) (fmap g)
f2 f g = fmap (bimap f g) . uncurry align

Explicitly write composite functors:

bimapBiff :: (Bifunctor t, Functor f, Functor g) => (a -> c) -> (b -> d) -> t (f a) (g b) -> t (f c) (g d)
bimapBiff f g = bimap (fmap f) (fmap g)

bimapTannen :: (Bifunctor t, Functor f) => (a -> c) -> (b -> d) -> f (t a b) -> f (t c d)
bimapTannen f g = fmap (bimap f g)

f1, f2 :: Semialign f => (a -> c) -> (b -> d) -> (f a, f b) -> f (These c d)
f1 f g = uncurry align . bimapBiff f g
f2 f g = bimapTannen f g . uncurry align

In other words, the law simply demands that align :: Biff (,) f f a b -> Tannen f These a b is a natural transformation between the bifunctors Biff (,) f f and Tannen f These.

This is a free theorem: every parametrically polymorphic function of the type foo :: forall a b. T a b -> U a b, where T and U are bifunctors, is a natural transformation between those bifunctors.

Like any other free theorem, it can be violated by doing naughty stuff with partiality and laziness in Haskell, but if we ignore those pathological cases the law is inviolable.

these-1.1.1 is failing to compile (as a dependency) on CentOS images using ghc-8.8.3 (and otherwise using a freeze file that matches stackage 16.5) with

Building library for these-1.1.1..

src/Data/Functor/These.hs:13:0: error:
     error: missing binary operator before token "("
     #elif MIN_VERSION_transformers(0,5,0)
     ^
   |
13 | #elif MIN_VERSION_transformers(0,5,0)
   | ^

which might possibly be related to the tooling available on that platform.

The only thing I can think of is maybe the empty newline on the previous line is rejected, somehow 🤷‍♂️