HLearn-datastructures 1.0.0 → 1.1.0

raw patch · 3 files changed

+58/−7 lines, 3 filesdep +deepseqdep −HLearn-distributionsdep ~HLearn-algebra

Dependencies added: deepseq

Dependencies removed: HLearn-distributions

Dependency ranges changed: HLearn-algebra

Files

• HLearn-datastructures.cabal +5/−4
• src/Data/Prunable.hs +16/−0
• src/HLearn/DataStructures/SortedVector.hs +37/−3

@@ -1,5 +1,5 @@ Name:                HLearn-datastructures-Version:             1.0.0+Version:             1.1.0 Description:         This package contains commonly used data structures Category:            Data Mining, Machine Learning, Data Structures License:             BSD3@@ -11,14 +11,14 @@  Library     Build-Depends:      -        HLearn-algebra          >= 1.0.2,-        HLearn-distributions    >= 1.0.0,+        HLearn-algebra          >= 1.1.0,+        --HLearn-distributions    >= 1.0.0,         ConstraintKinds         >= 0.1.0,         base                    >= 3 && < 5,          QuickCheck              >= 2.3.1,         MonadRandom             >= 0.1.9,-+        deepseq                 >= 1.3,         vector                  >= 0.10.0,         containers              >= 0.5.0,         list-extras             >= 0.4.1@@ -26,6 +26,7 @@     hs-source-dirs:     src     ghc-options:        -rtsopts -auto-all -caf-all -O2      Exposed-modules:+        Data.Prunable         HLearn.DataStructures.SortedVector         --HLearn.DataStructures.KDTree     Extensions:

@@ -0,0 +1,16 @@+module Data.Prunable+    where++import qualified Data.Foldable as F+import HLearn.Algebra++class Prunable t where+    prunefoldr :: (b -> t a -> IndexType (t a) -> Bool) -> (a -> b -> b) -> b -> t a -> b++class (F.Foldable t) => DualFoldable t where+    dualfoldr :: ((a,a) -> b -> b) -> b -> t a -> t a -> b+    dualfoldr f i t1 t2 = foldr f i [(x,y) | x <- (F.toList t1), y <- (F.toList t2)]++data TreeIndex = TreeLeft | TreeRight+    deriving (Read,Show,Eq,Ord,Bounded,Enum)+

@@ -6,6 +6,7 @@     where      import Control.Applicative+import Control.DeepSeq import qualified Data.Foldable as F import Data.List import Debug.Trace@@ -14,8 +15,8 @@  import qualified Control.ConstraintKinds as CK -import HLearn.Algebra-import HLearn.Models.Distributions+import Data.Prunable+import HLearn.Algebra   ------------------------------------------------------------------------------- -- data types@@ -35,10 +36,14 @@             | a < (vec V.! mid) = go lower (mid-1)             | otherwise         = True -- a==(vec V.! mid)             where mid = floor $ (fromIntegral $ lower+upper)/2+   +instance (NFData a) => NFData (SortedVector a) where+    rnf (SortedVector v) = rnf v      ------------------------------------------------------------------------------- -- Algebra +instance (Ord a) => Abelian (SortedVector a) instance (Ord a) => Monoid (SortedVector a) where     {-# INLINE mempty #-}     mempty = SortedVector $ V.empty@@ -59,6 +64,34 @@  --------------------------------------- +instance ({-Ord (IndexType dp), Ord dp-}) => Index (SortedVector dp) where+    type IndexType (SortedVector dp) = TreeIndex+    type IndexResult (SortedVector dp) = SortedVector dp+    (!) (SortedVector vec) TreeLeft  = SortedVector $ V.take (floor $ (fromIntegral $ V.length $ vec)/2) $ vec+    (!) (SortedVector vec) TreeRight = SortedVector $ V.drop (floor $ (fromIntegral $ V.length $ vec)/2) $ vec++instance Prunable SortedVector where+    prunefoldr p f b v@(SortedVector vec)+        | V.length vec == 1 = f (vec V.! 0) b+        | otherwise = if p b (SortedVector vec) TreeLeft+            then goright +            else prunefoldr p f goright (v ! TreeLeft)++            where +                goright = if p b (SortedVector vec) TreeRight+                    then b+                    else prunefoldr p f b (v ! TreeRight)++search_cata :: (Eq dp) => dp -> dp -> Bool -> Bool+search_cata query dp bool = query==dp || bool++search_prune :: (Ord dp) => dp -> Bool -> SortedVector dp -> TreeIndex -> Bool+search_prune query _ v TreeLeft  = (vector v) V.! (floor $ (fromIntegral $ V.length $ vector v)/2) < query+search_prune query _ v TreeRight = (vector v) V.! (floor $ (fromIntegral $ V.length $ vector v)/2) > query++binarySearch :: (Ord dp) => dp -> SortedVector dp -> Bool+binarySearch query sv = prunefoldr (search_prune query) (search_cata query) False sv+ instance F.Foldable SortedVector where     foldr f b (SortedVector vec) = V.foldr f b vec @@ -73,7 +106,8 @@     (<*>) = undefined  instance CK.Monad SortedVector where-    type MonadConstraint SortedVector a = Ord a+--     type MonadConstraint SortedVector a = Ord a+    return = SortedVector . V.singleton      (>>=) = flip concatMapa  concatMapa :: (Ord a, Ord b) => (a -> SortedVector b) -> SortedVector a -> SortedVector b