universe-base (empty) → 1.0

raw patch · 5 files changed

+159/−0 lines, 5 filesdep +basesetup-changed

Dependencies added: base

Files

• Data/Universe/Class.hs +30/−0
• Data/Universe/Helpers.hs +69/−0
• LICENSE +30/−0
• Setup.hs +2/−0
• universe-base.cabal +28/−0

@@ -0,0 +1,30 @@+{-# LANGUAGE CPP #-}+#ifdef DEFAULT_SIGNATURES+{-# LANGUAGE DefaultSignatures #-}+#endif+module Data.Universe.Class+	( -- | Bottoms are ignored for this entire module: only fully-defined inhabitants are considered inhabitants.+	  Universe(..)+	, Finite(..)+	) where++import Data.Universe.Helpers++-- | 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]+#ifdef DEFAULT_SIGNATURES+	default universe :: (Enum a, Bounded a) => [a]+	universe = universeDef+#endif++-- | 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,69 @@+module Data.Universe.Helpers (+	-- | This module is for functions that are useful for writing instances,+	-- but not necessarily for using them (and hence are not exported by the+	-- main module to avoid cluttering up the namespace).+	module Data.Universe.Helpers+	) where++import Data.List++-- | For many types, the 'universe' should be @[minBound .. maxBound]@;+-- 'universeDef' makes it easy to make such types an instance of 'Universe' via+-- the snippet+--+-- > instance Universe Foo where universe = universeDef+universeDef :: (Bounded a, Enum a) => [a]+universeDef = [minBound .. maxBound]++-- | 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. 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]++-- | 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)]+[] +*+ _  = [] -- 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]++-- | 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,30 @@+Copyright (c) 2013, Daniel Wagner++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++    * Redistributions of source code must retain the above copyright+      notice, this list of conditions and the following disclaimer.++    * Redistributions in binary form must reproduce the above+      copyright notice, this list of conditions and the following+      disclaimer in the documentation and/or other materials provided+      with the distribution.++    * Neither the name of Daniel Wagner nor the names of other+      contributors may be used to endorse or promote products derived+      from this software without specific prior written permission.++! This software is provided by the copyright holders and contributors+! "as is" and any express or implied warranties, including, but not+! limited to, the implied warranties of merchantability and fitness for+! a particular purpose are disclaimed. In no event shall the copyright+! owner or contributors be liable for any direct, indirect, incidental,+! special, exemplary, or consequential damages (including, but not+! limited to, procurement of substitute goods or services; loss of use,+! data, or profits; or business interruption) however caused and on any+! theory of liability, whether in contract, strict liability, or tort+! (including negligence or otherwise) arising in any way out of the use+! of this software, even if advised of the possibility of such damage.

@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain

@@ -0,0 +1,28 @@+name:                universe-base+version:             1.0+synopsis:            A class for finite and recursively enumerable types and some helper functions for enumerating them+homepage:            https://github.com/dmwit/universe+license:             BSD3+license-file:        LICENSE+author:              Daniel Wagner+maintainer:          me@dmwit.com+copyright:           2014 Daniel Wagner+category:            Data+build-type:          Simple+cabal-version:       >=1.10+source-repository head+    type:            git+    location:        https://github.com/dmwit/universe+source-repository this+    type:            git+    location:        https://github.com/dmwit/universe+    tag:             1.0++library+  exposed-modules:     Data.Universe.Class, Data.Universe.Helpers+  other-extensions:    CPP+  build-depends:       base >=4 && <5+  default-language:    Haskell2010+  if impl(ghc >= 7.4)+    cpp-options:       -DDEFAULT_SIGNATURES+    other-extensions:  DefaultSignatures