dmwit / universe Goto Github PK
View Code? Open in Web Editor NEWClasses for types where we know all the values
License: BSD 3-Clause "New" or "Revised" License
Classes for types where we know all the values
License: BSD 3-Clause "New" or "Revised" License
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:
cardinality
has type proxy a -> Integer
. Should it be proxy a -> Natural
instead?
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
.
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...)
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]
.
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
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.
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.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.