universe 0.2 → 0.3

raw patch · 5 files changed

+93/−26 lines, 5 files

Files

• Data/Universe.hs +1/−14
• Data/Universe/Helpers.hs +42/−10
• defsigs/Data/Universe/Class.hs +23/−0
• nodefsigs/Data/Universe/Class.hs +17/−0
• universe.cabal +10/−2

@@ -11,6 +11,7 @@ import Data.Monoid import Data.Ratio import Data.Universe.Helpers+import Data.Universe.Class import Data.Void import Data.Word @@ -23,20 +24,6 @@ import Data.Functor.Representable import Data.Key (Key) import qualified Data.Functor.Product as Functor---- | Creating an instance of this class is a declaration that your type is--- recursively enumerable (and that 'universe' is that enumeration). In--- particular, you promise that any finite inhabitant has a finite index in--- 'universe', and that no inhabitant appears at two different finite indices.-class Universe a where universe :: [a]---- | Creating an instance of this class is a declaration that your 'universe'--- eventually ends. Minimal definition: no methods defined. By default,--- @universeF = universe@, but for some types (like 'Either') the 'universeF'--- method may have a more intuitive ordering.-class Universe a => Finite a where-	universeF :: [a]-	universeF = universe  instance Universe ()       where universe = universeDef instance Universe Bool     where universe = universeDef

@@ -7,6 +7,9 @@  import Data.List +-- WHEN EDITING THIS DEFINITION:+-- edit ../../defsigs/Data/Universe/Class.hs:universe in tandem!+ -- | For many types, the 'universe' should be @[minBound .. maxBound]@; -- 'universeDef' makes it easy to make such types an instance of 'Universe' via -- the snippet@@ -17,24 +20,53 @@  -- | Fair n-way interleaving: given a finite number of (possibly infinite) -- lists, produce a single list such that whenever @v@ has finite index in one--- of the input lists, @v@ also has finite index in the output list.+-- of the input lists, @v@ also has finite index in the output list. No list's+-- elements occur more frequently (on average) than another's. interleave :: [[a]] -> [a] interleave = concat . transpose +-- | Unfair n-way interleaving: given a possibly infinite number of (possibly+-- infinite) lists, produce a single list such that whenever @v@ has finite+-- index in an input list at finite index, @v@ also has finite index in the+-- output list. Elements from lists at lower index occur more frequently, but+-- not exponentially so.+diagonal :: [[a]] -> [a]+diagonal xss = go ([], xss) where+	go (b, []  ) = interleave b+	go (b, e:es) = [h | h:_ <- b] ++ go (e:[t | _:t <- b],es)+ -- | Fair 2-way interleaving. (+++) :: [a] -> [a] -> [a] xs +++ ys = interleave [xs,ys] --- | Fair 2-way Cartesian product: given two (possibly infinite) lists, produce--- a single list such that whenever @v@ and @w@ have finite indices in the--- input lists, @(v,w)@ has finite index in the output list.+-- | Slightly unfair 2-way Cartesian product: given two (possibly infinite)+-- lists, produce a single list such that whenever @v@ and @w@ have finite+-- indices in the input lists, @(v,w)@ has finite index in the output list.+-- Lower indices occur as the @fst@ part of the tuple more frequently, but not+-- exponentially so. (+*+) :: [a] -> [b] -> [(a,b)]-(x:xs) +*+ ys = map ((,) x) ys +++ (xs +*+ ys)-[] +*+ ys = []+[] +*+ _  = [] -- special case: don't want to construct an infinite list of empty lists to pass to diagonal+xs +*+ ys = diagonal [[(x, y) | x <- xs] | y <- ys] --- | Fair n-way Cartesian product: given a finite number of (possibly--- infinite) lists, produce a single list such that whenever @vi@ has finite--- index in list i for each i, @[v1, ..., vn]@ has finite index in the output--- list.+-- | Slightly unfair n-way Cartesian product: given a finite number of+-- (possibly infinite) lists, produce a single list such that whenever @vi@ has+-- finite index in list i for each i, @[v1, ..., vn]@ has finite index in the+-- output list. choices :: [[a]] -> [[a]] choices = foldr ((map (uncurry (:)) .) . (+*+)) [[]]++-- | Very unfair 2-way Cartesian product: same guarantee as the slightly unfair+-- one, except that lower indices may occur as the @fst@ part of the tuple+-- exponentially more frequently. This mainly exists as a specification to test+-- against.+unfairCartesianProduct :: [a] -> [b] -> [(a,b)]+unfairCartesianProduct _  [] = [] -- special case: don't want to walk down xs forever hoping one of them will produce a nonempty thing+unfairCartesianProduct xs ys = go xs ys where+	go (x:xs) ys = map ((,) x) ys +++ go xs ys+	go []     ys = []++-- | Very unfair n-way Cartesian product: same guarantee as the slightly unfair+-- one, but not as good in the same sense that the very unfair 2-way product is+-- worse than the slightly unfair 2-way product. Mainly for testing purposes.+unfairChoices :: [[a]] -> [[a]]+unfairChoices = foldr ((map (uncurry (:)) .) . unfairCartesianProduct) [[]]

@@ -0,0 +1,23 @@+-- WHEN EDITING THIS FILE:+-- edit ../../nodefsigs/Data/Universe.hs in tandem!+{-# LANGUAGE DefaultSignatures #-}+module Data.Universe.Class where++-- | Creating an instance of this class is a declaration that your type is+-- recursively enumerable (and that 'universe' is that enumeration). In+-- particular, you promise that any finite inhabitant has a finite index in+-- 'universe', and that no inhabitant appears at two different finite indices.+class Universe a where+	universe :: [a]+	default universe :: (Enum a, Bounded a) => [a]+	-- WHEN EDITING THIS DEFINITION:+	-- edit ../../Data/Universe/Helpers.hs:universeDef in tandem!+	universe = [minBound .. maxBound]++-- | Creating an instance of this class is a declaration that your 'universe'+-- eventually ends. Minimal definition: no methods defined. By default,+-- @universeF = universe@, but for some types (like 'Either') the 'universeF'+-- method may have a more intuitive ordering.+class Universe a => Finite a where+	universeF :: [a]+	universeF = universe

@@ -0,0 +1,17 @@+-- WHEN EDITING THIS FILE:+-- edit ../../nodefsigs/Data/Universe.hs in tandem!+module Data.Universe.Class where++-- | Creating an instance of this class is a declaration that your type is+-- recursively enumerable (and that 'universe' is that enumeration). In+-- particular, you promise that any finite inhabitant has a finite index in+-- 'universe', and that no inhabitant appears at two different finite indices.+class Universe a where universe :: [a]++-- | Creating an instance of this class is a declaration that your 'universe'+-- eventually ends. Minimal definition: no methods defined. By default,+-- @universeF = universe@, but for some types (like 'Either') the 'universeF'+-- method may have a more intuitive ordering.+class Universe a => Finite a where+	universeF :: [a]+	universeF = universe

@@ -1,5 +1,5 @@ name:                universe-version:             0.2+version:             0.3 synopsis:            Classes for types where we know all the values description:         A small package, in the spirit of data-default, which allows the munging of finite and recursively enumerable types license:             BSD3@@ -9,6 +9,8 @@ copyright:           2013 Daniel Wagner category:            Data build-type:          Simple+extra-source-files:    defsigs/Data/Universe/Class.hs,+                     nodefsigs/Data/Universe/Class.hs cabal-version:       >=1.8 source-repository head     type:            git@@ -16,7 +18,7 @@ source-repository this     type:            git     location:        https://github.com/dmwit/universe-    tag:             0.2+    tag:             0.3  library   exposed-modules:     Data.Universe,@@ -26,6 +28,12 @@                        Data.Universe.Instances.Ord,                        Data.Universe.Instances.Read,                        Data.Universe.Instances.Show+  other-modules:       Data.Universe.Class+  hs-source-dirs:      .+  if impl(ghc >= 7.4)+    hs-source-dirs:      defsigs+  else+    hs-source-dirs:    nodefsigs   build-depends:       base                   >=4   && <5  ,                        comonad-transformers   >=0.1 && <3.1,                        containers             >=0.1 && <1  ,