packages feed

lazyset (empty) → 0.1.0.0

raw patch · 10 files changed

+452/−0 lines, 10 filesdep +HUnitdep +basedep +containerssetup-changed

Dependencies added: HUnit, base, containers, data-ordlist, time, timeit

Files

+ Benchmark.hs view
@@ -0,0 +1,25 @@+{-# LANGUAGE BangPatterns #-}
+
+import Prelude hiding (lookup)
+import System.Exit
+import Data.Set.Lazy
+import System.TimeIt
+
+expensive n = let x = sum [1..4*10^5+n] in x-x+n
+
+
+                     
+main = do
+    let evenList = filter even [1..]
+    let r1 = member (2*10^6) $ fromList evenList
+    timeIt $ putStrLn $ "finding one in a million." ++ show r1
+    let set = fromList evenList
+    let r2 = and $ map (\i-> member i set) (take 1000 [2*10^6..])
+    timeIt $ putStrLn $ "finding a thousand in a million " ++ show r2
+    let expensiveSet = fromList $ map expensive [1..]
+    putStrLn "Going through a lazy set one by one. Watch the times to see when a new batch is loaded."
+    sequence $ map (timeIt . print . (`lookup` expensiveSet) ) [1..20]
+    let flatSet = growFromAscList 1.3 $ map expensive [1..]
+    putStrLn "This time the set if flatter."
+    sequence $ map (timeIt . print . (`lookup` flatSet) ) [1..20]    
+    return ()
+ ChangeLog.md view
@@ -0,0 +1,7 @@+# Revision history for lazyset
+
+## 0.1.0.0  -- YYYY-mm-dd
+
+* First version. Released on an unsuspecting world.
+* Import of files from https://github.com/happyherp/littlethings/tree/master/euler
+* making this a cabal-module
+ Data/Map/Lazier.hs view
@@ -0,0 +1,59 @@+{-| 
+Copyright   : (c) Carlos Freund, 2016
+License     : MIT
+Maintainer  : carlosfreund@gmail.com
+Stability   : experimental
+
+A Map that can be created from lazy, ordered, infinite lists. 
+Based on 'Data.Set.Lazy.LazySet'.
+-}
+module Data.Map.Lazier (
+
+    -- * Types 
+    Map,
+    
+    -- * Query 
+    member,
+    lookup,
+    
+    -- * Creation
+    fromList
+    
+    )where 
+
+import qualified Data.Set.Lazy as LS
+import Data.Ord(compare)
+import Prelude hiding(lookup)
+
+-- | A mapping of type 'k' to type 'e'.
+type Map k e = LS.LazySet (MapEntry k e) 
+
+data MapEntry k e = MapEntry k e | JustKey k
+    deriving Show
+
+instance (Eq k) => Eq (MapEntry k e) where
+    a == b = getKey a == getKey b
+
+instance (Ord k) => Ord (MapEntry k e)  where 
+    compare a b = compare (getKey a) (getKey b)    
+    
+getKey :: MapEntry k e -> k
+getKey (MapEntry k e) = k
+getKey (JustKey k) = k    
+
+entryFromTuple :: Ord k => (k,e) -> MapEntry k e
+entryFromTuple (k,e) = MapEntry k e
+    
+-- | Create a new Map from a list of tuples. The list must be sorted by key ascending.     
+fromList :: Ord k => [(k,e)] -> Map k e
+fromList xs = LS.fromList $ map entryFromTuple xs
+
+-- | Check if a key exists in this Map. 
+member :: Ord k => k -> Map k e -> Bool
+member key = LS.member (JustKey key)
+
+-- | Return the value of a given key or 'Nothing'
+lookup :: Ord k => k -> Map k e -> Maybe e
+lookup k map=  case LS.lookup (JustKey k) map of 
+    Just (MapEntry _ e) -> Just e 
+    _ -> Nothing
+ Data/Set/Lazy.hs view
@@ -0,0 +1,120 @@+{-| 
+Module      : LazySet
+Description : A truly lazy Set. 
+Copyright   : (c) Carlos Freund, 2016
+License     : MIT
+Maintainer  : carlosfreund@gmail.com
+Stability   : experimental
+
+A Set that can be created from lazy, ordered, infinite lists. 
+-}
+module Data.Set.Lazy where 
+
+import Prelude hiding(lookup)
+import qualified Data.List as List
+import qualified Data.Set as NSet
+import qualified Data.List.Ordered as OList
+import Data.Maybe (isJust)
+import Data.Ord
+
+    
+data LazySet a = LazySet [NSet.Set a]
+    deriving (Eq, Show)
+    
+-- * Query    
+
+-- | Checks if the value is a member of the 'LazySet'. 
+-- Performance: O(m)=log m  
+--Where m is the position of the element beeing searched for. 
+-- This only applies after the element has been fetched from the underlying list.
+member :: Ord a => a -> LazySet a ->  Bool
+member e set = isJust $ lookup e set             
+    
+-- | Searches for a value in a Set. If it can not be found returns 'Nothing' otherwhise 
+-- Returns 'Just a' if it can find it. The returned value will be the one from the set, not the one that was passed. 
+lookup :: Ord a => a -> LazySet a -> Maybe a
+lookup e (LazySet sets) = findIn sets
+    where findIn [] = Nothing
+          findIn (set:rest) = case NSet.lookupLE e set of 
+            Nothing -> Nothing
+            Just x ->  if (x == e) then Just x else findIn rest  
+
+
+-- | Returns true if the 'LazSet' is empty. 
+null :: LazySet a -> Bool
+null (LazySet (x:xs)) = True
+null _ = False
+
+-- | Returns the size of the set. Do not use this on infinite Sets.
+size :: Ord a => LazySet a -> Int
+size = length . toList 
+
+-- * Combine
+    
+-- | Splits the 'LazySet' into two parts. 
+-- The first containing all consecutive elements of the Set where the predicate applies.
+-- The second contains the (infinite) rest. 
+spanAntitone :: Ord a => (a -> Bool) -> LazySet a -> (LazySet a, LazySet a)
+spanAntitone pred (LazySet sets) = let
+    (lesser, (middle:higher)) = List.span (pred . NSet.findMax) sets
+    (middleLesser, middleHigher) = NSet.spanAntitone pred middle
+    in (LazySet (lesser++[middleLesser]), LazySet (middleHigher:higher))
+    
+-- | Union of two LazySets.     
+union :: Ord a => LazySet a -> LazySet a -> LazySet a
+union s1 s2 = let  
+    in fromList $ OList.union (toList s1) (toList s2)
+
+
+-- * Build
+
+
+-- | Create an 'empty' 'LazySet'.    
+empty :: Ord a => LazySet a    
+empty = fromList []
+    
+  
+-- | Builds a 'LazySet' from an ascending ordered list.
+-- If the list is not ordered an error is thrown. 
+fromAscList :: Ord a => [a] -> LazySet a
+fromAscList = growFromAscList 2.0               
+
+
+-- | Like 'fromAscList' but with a custom growth-factor. 
+growFromAscList :: Ord a => 
+    Float   -- ^ The factor by which the subtrees grow. 
+    --Must be >= 1.0. A growth of 1.0 makes the 'LazySet' behave like a List. 
+    -- The higher it is set, the more it behaves like a 'Data.Set'.
+    -- The downside of a higher growth-factor is that bigger batches are extracted from the source-list at once. 
+    -> [a]  -- ^ An ascending List
+    -> LazySet a     
+growFromAscList growth _ | growth < 1.0 = error "growth must be at least 1" 
+growFromAscList growth xs = LazySet (build 0 growth (checkDir xs))
+    where checkDir (a:b:s)| a > b = error "Elements must be ascending." 
+          checkDir  xs = xs   
+
+-- | Alias for 'fromAscList'.
+fromList :: Ord a => [a] -> LazySet a
+fromList = fromAscList
+          
+-- | Create a 'LazSet' from a descending list.           
+fromDescList :: Ord a => [a] -> LazySet (Down a)
+fromDescList xs = fromAscList (map Down xs)
+    
+-- | Kind of internal. 
+build :: Ord a => Int -- ^ starting-depth 
+    -> Float -- ^ growth-factor
+    -> [a] -- ^Ascending source-list 
+    -> [NSet.Set a]         
+build _ _ [] = []
+build level growth xs = let 
+    (elementsForThisLevel, elementsFurtherDown) = List.splitAt (ceiling $ growth^level) xs
+    in (NSet.fromAscList elementsForThisLevel):(build (level + 1) growth elementsFurtherDown)
+    
+    
+-- * Export
+      
+-- | List with all elements in order.
+toList :: Ord a => LazySet a -> [a]
+toList (LazySet sets) = concat $ map NSet.toAscList sets
+
+ LICENSE view
@@ -0,0 +1,21 @@+MIT License
+
+Copyright (c) 2016 Carlos Freund
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in all
+copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+SOFTWARE.
+ LazyMapTest.hs view
@@ -0,0 +1,20 @@+import Prelude hiding(lookup)
+import Test.HUnit
+import System.Exit
+import Data.Map.Lazier
+
+
+mymap :: Map Int String
+mymap = fromList $ map (\i->(i, show i)) [1..]
+ 
+tests = TestList [
+    TestCase $ assertEqual "Present 1"      (lookup   1 mymap) (Just "1" ),
+    TestCase $ assertEqual "Present 111"    (lookup 111 mymap) (Just "111"),
+    TestCase $ assertEqual "Not Present -1" (lookup(-1) mymap) Nothing 
+    ] 
+    
+      
+main = do
+    result <- runTestTT tests
+    let allpassed = (errors result + failures result) == 0
+    if allpassed then exitSuccess else exitFailure
+ LazySetTest.hs view
@@ -0,0 +1,49 @@+import Test.HUnit
+import System.Exit
+import Data.Set.Lazy
+
+tests = TestList [basic, fizzbuzztest, infinity]
+
+
+
+---- BASIC -----
+
+basic = TestList [noZero, oneToTen, noEleven]
+    where   
+    toTenList = [1..10]
+    toTenSet = fromList toTenList
+
+    noZero   = TestCase $ assertBool "Zero not in there" $not (member 0 toTenSet)
+    oneToTen = TestCase $ assertBool "1 to 10 present in set." $ all (\i -> member i toTenSet) toTenList
+    noEleven = TestCase $ assertBool "11 not in there" $not (member 11 toTenSet)
+    
+    
+----- INFINITY----
+                    
+evenNumberSet = fromList $ filter even [1..]         
+                     
+infinity = TestList [
+    TestCase ( assertBool "Even numbers are in there " 
+        (all (\i -> member i evenNumberSet) [2,4,6,100,10^4])),
+    TestCase ( assertBool "Odd numbers are in there " 
+        (all (\i ->not $ member i evenNumberSet) [1,3,5,99,10^4+1]))
+    ] 
+    
+        
+---  FizzBuzz ---
+
+isFizzBuzz x = x `mod` 7 == 0 || '7' `elem` show x       
+
+fizzbuzzes = fromList $ filter isFizzBuzz [1..]
+
+fizzbuzztest = TestList[
+    TestCase ( assertBool "fizzes" 
+        (all (\i ->       member i fizzbuzzes) [7,14,21,70,71,77])),
+    TestCase ( assertBool "does not fizz" 
+        (all (\i -> not $ member i fizzbuzzes) [1,2,3,8,9,10,16,22,100]))    ]
+        
+                     
+main = do
+    result <- runTestTT tests
+    let allpassed = (errors result + failures result) == 0
+    if allpassed then exitSuccess else exitFailure
+ README.md view
@@ -0,0 +1,55 @@+# lazyset
+A Lazy Set and Map implemented in Haskell. 
+
+
+Allows efficient, lazy lookups on sorted lists. The list may be of ininite size. 
+
+The Source-List must 
++ contain elements that implement *Ord* 
++ must be ascending (or descending: see *fromDescList*)
++ either produce an infinite number of elements or terminate
+
+
+##  Set Sample usage
+```haskell
+
+import Data.Set.Lazy
+
+set = fromAscList $ map (*3) [1..]
+
+3 `member` set -> True
+4 `member` set -> False
+```
+
+
+## Map Sample usage
+
+```haskell
+
+import Prelude hiding(lookup)
+import Data.Map.Lazier
+
+
+sqrtmap = fromList $ map (\i->(i, sqrt i)) [1..]
+lookup 2 sqrtmap -> Just 1.4142135623730951
+
+```
+
+# Performance
+
+Elements from the Source-List will be requested in batches of increasing size. By default the batch-size is increases by two. This would lead to batches of *1,2,4,8,16*. This can be changed by using *growFromAscList factor list*. For Example a factor of *1.3* casues the batches to be *1,2,2,3,3,4,5*.
+
+Increasing the growth-factor reduces lookup times but increases the batch-size. When it is set to 1.0 it performs like a list.
+
+
+lookup: O(m) = log m where m is the index of the element in the source-list. 
+
+## Issues
+
+This breaks the set, because the underlying list stops producing elements. 
+```haskell
+
+set = fromList $ filter (<4) [1..]
+5 `member` set
+
+```
+ Setup.hs view
@@ -0,0 +1,2 @@+import Distribution.Simple
+main = defaultMain
+ lazyset.cabal view
@@ -0,0 +1,94 @@+-- Initial lazyset.cabal generated by cabal init.  For further 
+-- documentation, see http://haskell.org/cabal/users-guide/
+
+-- The name of the package.
+name:                lazyset
+
+-- The package version.  See the Haskell package versioning policy (PVP) 
+-- for standards guiding when and how versions should be incremented.
+-- https://wiki.haskell.org/Package_versioning_policy
+-- PVP summary:      +-+------- breaking API changes
+--                   | | +----- non-breaking API additions
+--                   | | | +--- code changes with no API change
+version:             0.1.0.0
+
+-- A short (one-line) description of the package.
+synopsis:            Set and Map from lazy/infinite lists.
+
+-- A longer description of the package.
+description:      A Set and Map implementation that is completly lazy and works for infinite sets and maps.    
+
+-- URL for the project homepage or repository.
+homepage:            https://github.com/happyherp/lazyset
+
+-- The license under which the package is released.
+license:             MIT
+
+-- The file containing the license text.
+license-file:        LICENSE
+
+-- The package author(s).
+author:              Carlos Freund
+
+-- An email address to which users can send suggestions, bug reports, and 
+-- patches.
+maintainer:          carlosfreund@googlemail.com
+
+-- A copyright notice.
+-- copyright:           
+
+category:            Data
+
+build-type:          Simple
+
+-- Extra files to be distributed with the package, such as examples or a 
+-- README.
+extra-source-files:  ChangeLog.md, README.md
+
+-- Constraint on the version of Cabal needed to build this package.
+cabal-version:       >=1.10
+
+source-repository head
+  type:     git
+  location: https://github.com/happyherp/lazyset
+  
+
+library
+  -- Modules exported by the library.
+  exposed-modules:     Data.Set.Lazy, Data.Map.Lazier
+  
+  -- Modules included in this library but not exported.
+  -- other-modules:       
+  
+  -- LANGUAGE extensions used by modules in this package.
+  -- other-extensions:    
+  
+  -- Other library packages from which modules are imported.
+  build-depends:       base >=4.9 && <4.10, data-ordlist >=0.4 && <0.5, containers >=0.5.8.1 && <0.6
+  
+  -- Directories containing source files.
+  -- hs-source-dirs:      
+  
+  -- Base language which the package is written in.
+  default-language:    Haskell2010
+  
+  
+Test-Suite settest
+    type:       exitcode-stdio-1.0
+    main-is:    LazySetTest.hs
+    build-depends: base, HUnit, containers, data-ordlist
+    default-language:    Haskell2010
+    
+Test-Suite maptest
+    type:       exitcode-stdio-1.0
+    main-is:    LazyMapTest.hs
+    build-depends: base, HUnit, containers, data-ordlist
+    default-language:    Haskell2010    
+    
+    
+Benchmark bench
+    type:       exitcode-stdio-1.0
+    main-is:    Benchmark.hs
+    build-depends: base, time, containers, data-ordlist, timeit >= 1.0.0.0 && < 1.1
+    default-language:    Haskell2010
+