dmwit / universe Goto Github PK

It would be nice to have

cardinality :: Integer
cardinality = genericLength universeF

or something like that which could be overridden for efficiency in the UniverseF typeclass.

Thanks for the upload. Unfortunately, it does not build here

Building universe-0.4.0.4...
Preprocessing library universe-0.4.0.4...
[1 of 8] Compiling Data.Universe.Helpers ( Data/Universe/Helpers.hs, dist-ghc/build/Data/Universe/Helpers.o )
[2 of 8] Compiling Data.Universe    ( Data/Universe.hs, dist-ghc/build/Data/Universe.o )

Data/Universe.hs:144:30:
    Could not deduce (Representable (TracedT s f))
      arising from a use of `tabulate'
    from the context (Representable f,
                      Finite s,
                      Ord s,
                      Finite (Key f),
                      Ord (Key f),
                      Universe a)
      bound by the instance declaration
      at Data/Universe.hs:(142,10)-(143,35)
    Possible fix:
      add an instance declaration for (Representable (TracedT s f))
    In the first argument of `map', namely `tabulate'
    In the expression: map tabulate universe
    In an equation for `universe': universe = map tabulate universe

Data/Universe.hs:144:39:
    Could not deduce (Finite (Key (TracedT s f)))
      arising from a use of `universe'
    from the context (Representable f,
                      Finite s,
                      Ord s,
                      Finite (Key f),
                      Ord (Key f),
                      Universe a)
      bound by the instance declaration
      at Data/Universe.hs:(142,10)-(143,35)
    Possible fix:
      add an instance declaration for (Finite (Key (TracedT s f)))
    In the second argument of `map', namely `universe'
    In the expression: map tabulate universe
    In an equation for `universe': universe = map tabulate universe

Data/Universe.hs:194:31:
    Could not deduce (Representable (TracedT s f))
      arising from a use of `tabulate'
    from the context (Universe (TracedT s f a),
                      Representable f,
                      Finite s,
                      Ord s,
                      Finite (Key f),
                      Ord (Key f),
                      Finite a)
      bound by the instance declaration
      at Data/Universe.hs:(192,10)-(193,33)
    Possible fix:
      add an instance declaration for (Representable (TracedT s f))
    In the first argument of `map', namely `tabulate'
    In the expression: map tabulate universeF
    In an equation for `universeF': universeF = map tabulate universeF

Data/Universe.hs:194:40:
    Could not deduce (Finite (Key (TracedT s f)))
      arising from a use of `universeF'
    from the context (Universe (TracedT s f a),
                      Representable f,
                      Finite s,
                      Ord s,
                      Finite (Key f),
                      Ord (Key f),
                      Finite a)
      bound by the instance declaration
      at Data/Universe.hs:(192,10)-(193,33)
    Possible fix:
      add an instance declaration for (Finite (Key (TracedT s f)))
    In the second argument of `map', namely `universeF'
    In the expression: map tabulate universeF
    In an equation for `universeF': universeF = map tabulate universeF

The versions used in Debian currently are:

Configuring universe-0.4.0.4...
Dependency base ==4.*: using base-4.6.0.1
Dependency comonad-transformers >=0.1 && <4.0: using
comonad-transformers-3.0.1
Dependency containers >=0.1 && <1: using containers-0.5.0.0
Dependency keys >=0.1 && <4: using keys-3.10
Dependency mtl >=1.0 && <2.2: using mtl-2.1.2
Dependency representable-functors >=2.4 && <3.3: using
representable-functors-3.2.0.2
Dependency transformers >=0.2 && <0.4: using transformers-0.3.0.0
Dependency void >=0.1 && <0.7: using void-0.5.11

The extra import is a pain.

Hi,

I've been playing around with some toy code that overlaps with some of the problems this library solves. In looking at it, I had a few questions:

1. cardinality has type proxy a -> Integer. Should it be proxy a -> Natural instead?

2. universe has type [a]. Sometimes you may want the inhabitant at an index i. With the current API, I guess you would do genericIndex universe i. Would it make sense to have some function foo with type Natural -> Maybe a or Natural -> a, too? universe could perhaps have a default implementation in terms of this function, e.g.

   universe = takeWhile isJust $ map foo [1..]

   My feeling is that a class-specific implementation of Natural -> Maybe a could be more performant than genericIndex universe i.

3. Would it make sense to have a function Maybe a -> Natural on Universe or a related class? (For more context, my dissatisfaction with Enum's toEnum and fromEnum using Int led me here...)

4. Finite says

   Creating an instance of this class is a declaration that your universe eventually ends.

   This seems very similar to Bounded. Would it make sense to be able to recover something like a minBound and maxBound with this class? Such that

   minBound == universe `genericIndex` 0
   maxBound == universe `genericIndex` (cardinality (Proxy :: Proxy a))

   Although there is a law about universeF terminating, would such bounds with laws like the above give stronger guarantees about Finite? I worry that universeF versus universe don't tell me very much, since they have the same type [a].

5. Would an Infinite class make sense, e.g.

   class Universe a => Infinite a where
       infinite :: Stream a

   Reading this library, I see Universe could be finite or infinite, based on the [a] API. I see Finite should be finite (although I must trust universeF terminates). Something like infinite with a Stream a-based API could make clear that the Stream returned by infinite does not terminate. There could also be a law

   universe == toList infinite

Thanks for your consideration,
Mark

Hi, I think this project is really great, thank you for all the work you do on it!

I had an idea which I think is worth mentioning. Going with the description of "... for types where we know all the values" I think their is a good case for Finite a => Finite (Equivalence a) (the Equivalence a type being from http://hackage.haskell.org/package/contravariant-1.5/docs/Data-Functor-Contravariant.html#t:Equivalence). But I'm not sure if that is too specific for your library.

For the cardinality I think if you wanted to avoid computing universeF to get the length you could just compute the corresponding Bell number:
https://en.wikipedia.org/wiki/Equivalence_relation#Counting_possible_partitions

To actually generate the list of partitions I've been using:

-- partitions of a set
-- partitions {0..2} = [ [[0],[1],[2]]
--                     , [[0],[2,1]]
--                     , [[2,0],[1]]
--                     , [[1,0],[2]]
--                     , [[2,1,0]]
--                     ]
partitions ∷ (Foldable t) ⇒ t a → [[NonEmpty a]]
partitions = Foldable.foldl (\xs → (xs >>=) . go) [[]]
   where go ∷ a → [NonEmpty a] → [[NonEmpty a]]
         go x []       = [[ x :| [] ]]
         go x (y : ys) = fmap (y :) (go x ys) <> [(x :| NE.toList y) : ys]

And then just in case you are interested here are the helper functions:

-- for each list (which represents an equivalence class), check if both a₁ and a₂ are in it
-- if for any list two are in the same list return true, otherwise false
toEquivalence ∷ (Finite a, Foldable t) ⇒ t (NonEmpty a) → Equivalence a
toEquivalence parts = Equivalence (\a₁ a₂ → any (\xs → (a₁ `elem` xs) && (a₂ `elem` xs)) parts)

fromEquivalence ∷ ∀ a . (Finite a) ⇒ Equivalence a → [NonEmpty a]
fromEquivalence (Equivalence r) = unfoldr go universeF
      where go ∷ [a] → Maybe (NonEmpty a, [a])
            go []       = Nothing
            go (x : xs) = Just (x :| p, np)
                    where (p, np) = List.partition (r x) xs

So then for the Finite instance, you would potentially be able to do something like:

  universeF ∷ [Equivalence a]
  universeF = fmap toEquivalence (partitions universeF)

Fair warning, I haven't written any of this with performance in mind, but I still think the idea is worth mentioning. If you don't see a use for it please close the ticket I would not take offense!

Have a nice day!

Have to wait until mtl supporting transformers-0.5.0.0 is released

Seems there is https://github.com/dmwit/universe/blob/32f1d4cf97a4699f60f2e5ede0415ce7502f3cd6/instances/containers/Data/Universe/Instances/Containers.hs but it's not done. I might need Set instance soon.

What about unordered-containers ? could they live in universe-instances-containers or would you prefer universe-instances-unordered-containers, @dmwit?

Perhaps use CPP instead of src-dir to enable/disable DefaultSignatures.

• Natural
• Proxy (also Tagged)
• NonEmpty a

adding nats, tagged and semigroups instances when necessary

Every finite type can be ordered (somehow). Here's one way to express that:

class (Universe a, Coercible a (Ordered a), Ord (Ordered a)) => Finite a where
  type Ordered a
  type Ordered a = a

  universeS :: Set (Ordered a)
  universeS = fromList (coerce $ universeF @a)

  universeF :: [a]
  universeF = coerce . toList $ universeS @a

Another option would be to allow an arbitrary Iso' between a and a (possibly very different) Ordered a, which might be better if the ordering on Ordered a can't be expressed efficiently by directly comparing elements of a.

class (Universe a, Ord (Ordered a)) => Finite a where
  type Ordered a
  type Ordered a = a

  ordering :: Iso' a (Ordered a)
  default ordering :: Coercible a (Ordered a) => Iso' a (Ordered a)
  ordering = coerced

  universeS :: Set (Ordered a)
  universeS = fromList (map (view ordering) (universeF @a))

  universeF :: [a]
  universeF = universe

-- A default definition of `universe` or `universeF` in terms of `universeF`
universeFfromS :: forall a. Finite a => [a]
universeFfromS = map (view (from ordering)) . toList $ universeS @a

Could you raise the upper bounds to the latest version of all dependencies? Thank!

To a first approximation,

class GUniverse f where
  gUniverse :: [f a]

instance GUniverse U1 where
  gUniverse = [U1]

instance GUniverse V1 where
  gUniverse = []

instance (GUniverse f, GUniverse g) => GUniverse (f :*: g) where
  gUniverse = map (\(x,y) -> x :*: y) $ gUniverse +*+ gUniverse

instance (GUniverse f, GUniverse g) => GUniverse (f :+: g) where
  gUniverse = map L1 gUniverse +++ map R1 gUniverse

instance GUniverse f => GUniverse (M1 i c f) where
  gUniverse = map M1 gUniverse

instance Universe c => GUniverse (K1 i c) where
  gUniverse = map K1 universe

universeGeneric :: (Generic a, GUniverse (Rep a)) => [a]
universeGeneric = map to gUniverse

Therefore, I would suggest hiding the (Finite e, Ord e) => Foldable/Traversable (->) e instances behind a newtype.

Hello again! Thank you all again for this wonderful package and all your hard work on it. I am curious if you would be interested in adding a few more Finite instances to universe-instances-extended for the basic types found in the these package and smash package. The code I have now looks something like this, but if you would be interested in a PR, I would of course try to match your coding style (ditch the unicode, etc. [: ) :

Edit removed the UnicodeSyntax for you @phadej :]

import           Data.Can   (Can (..), can)
import           Data.Smash (Smash (..), smash, toSmash)
import           Data.These (These (..), these)
import           Data.Wedge (Wedge (..), wedge, toWedge)

instance (Universe a, Universe b) => Universe (Smash a b) where
  universe :: [Smash a b]
  universe = fmap toSmash universe

instance (Universe a, Universe b) => Universe (Wedge a b) where
  universe :: [Wedge a b]
  universe = fmap toWedge universe

instance (Universe a, Universe b) => Universe (Can a b) where
  universe :: [Can a b]
  universe = fmap toCan universe
    where
      toCan :: Maybe (These a b) -> Can a b
      toCan = maybe Non (these One Eno Two)

instance (Universe a, Universe b) => Universe (These a b) where
  universe :: [These a b]
  universe = fmap toThese universe
    where
      toThese :: Either (Either a b) (a, b) -> These a b
      toThese = either (either This That) (uncurry These)

Leaving just the Finite instances, which are pretty straight forward.

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

instance (Finite a, Finite b) => Finite (Wedge a b) where
  -- 1 + a + b
  cardinality :: Tagged (Wedge a b) Natural
  cardinality = liftA2 (\a b -> 1 + a + b) (retag (cardinality :: Tagged a Natural)) (retag (cardinality :: Tagged b Natural))
  universeF :: [Wedge a b]
  universeF = fmap toWedge universeF

instance (Finite a, Finite b) => Finite (Can a b) where
  -- 1 + a + b + ab
  cardinality :: Tagged (Can a b) Natural
  cardinality = liftA2 (\a b -> 1 + a + b + a * b) (retag (cardinality :: Tagged a Natural)) (retag (cardinality :: Tagged b Natural))
  universeF :: [Can a b]
  universeF = fmap toCan universeF
    where
      toCan :: Maybe (These a b) -> Can a b
      toCan = maybe Non (these One Eno Two)

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
    where
      toThese :: Either (Either a b) (a, b) -> These a b
      toThese = either (either This That) (uncurry These)

I won't be offended if you aren't interested and close the ticket, but let me know if you are interested and I would be happy to make a PR. Thank you for your time and consideration. Have a great day!

P.S. I have an awesome update in the works for my previous PR (regarding the Equivalence a type [and I've also added Comparison a]), thank you so much for your patience with that!

For some usage patterns it's beneficial to produce universe stream on the fly, without memoising it. As it's a CAF it's get memoised by default:

For example with:

consumerExample :: Property
consumerExample = once $ a .&&. b
  where
    a = (universe !! 10000001) === (5000001 :: Integer)
    b = (universe !! 10000001) === (5000001 :: Integer)

maximal residency get out of hands:

     272,054,848 bytes maximum residency (13 sample(s))

One solution would be to change Universe class to be

class Universe a where
    {-# DEPRECATED universe "Consider using churchUniverse" #-}
    universe = build churchEncoding

    churchUniverse :: forall b. (a -> b -> b) -> b -> b
    churchUniverse = churchUiverseDef

{-# DEPRECATED universeDef "Consider using churchUniverseDef" #-}
universeDef :: (Enum a, Bounded a) => [a]
universeDef = [minBound..maxBound]

churchUniverseDef :: (Enum a, Bounded a) => forall b. (a -> b -> b) -> b -> b
churchUniverseDef c n = foldr c n [minBound..maxBound]

I could try to make this change, if it's a problem you think is worth solving. My gut feeling is that using church encoding is probably the best way to prevent sharing.

just what it says on the tin; it shouldn't do that

There are a^b functions from a to b.

Hi there!

Many thanks for making this library.

I encountered the following issue while experimenting within ghci:

> :set -XTypeApplications
> import Data.Map.Strict (Map)
> import Data.Universe.Class
> take 1 $ universe @(Map Word Word)
*** Exception: stack overflow

The issue seems to be related to the cardinality of the key type, since:

> take 1 $ universe @(Map Word ())
*** Exception: stack overflow 

Additionally:

> cardinality @(Map Word Word)
Tagged

(does not terminate, and CPU spins at 100%)

Perhaps I'm using the library incorrectly?

Using a type with a much smaller cardinality works as I would expect:

> cardinality @(Map Bool Bool)
Tagged 9

Details of my environment:

• universe-base == 1.1.3
• GHC 8.10.7

Let me know if you need me to provide any more details, am happy to help.

Many thanks again!

Jonathan

We get quite a lot of intermediate lists in various ways. as +++ (bs +++ cs), map f as ++ bs, etc. Is there a way to cut down on that? I don't know that GHC's list fusion is a good fit, but maybe we can do something else.

Would be nice to have these packages on stackage. I'm considering using this packages as dependency for lattices, but would like universe -family of packages to be on stackage first.

Could we have instance for Enum a, Bounded a where universe = [minBound..maxBound]?

This works:

data Foo a where 
  MkFoo :: Foo Bool 
data Bar a where
  MkBar :: Int -> Bar Int

deriveUniverseSome ''Foo
deriveUniverseSome ''Bar

But if you replace that MkBar's argument (Int) with Foo a, it will fail:

data Foo a where 
  MkFoo :: Foo Int 
data Bar a where
  MkBar :: Foo a -> Bar a

deriveUniverseSome ''Foo
deriveUniverseSome ''Bar

The compile error being:

    • No instance for (Universe (Foo a0))
        arising from a use of ‘universe’
    • In the second argument of ‘(Data.Universe.Helpers.<+*+>)’, namely
        ‘universe’
      In the second argument of ‘map’, namely
        ‘([MkBar] Data.Universe.Helpers.<+*+> universe)’
      In the expression:
        (map Some) ([MkBar] Data.Universe.Helpers.<+* 
     |
1800 | deriveUniverseSome ''Bar
     | ^^^^^^^^^^^^^^^^^^^^^^^^

I'd think it should be using the SomeUniverse Foo (or Universe (Some Foo)) instance instead?

It looks like everything is failing for uninteresting reasons.

to allow 3.2.