vector-builder (empty) → 0.1

raw patch · 11 files changed

+334/−0 lines, 11 filesdep +basedep +base-preludedep +primitivesetup-changed

Dependencies added: base, base-prelude, primitive, quickcheck-instances, rebase, semigroups, tasty, tasty-hunit, tasty-quickcheck, vector, vector-builder

Files

• LICENSE +22/−0
• Setup.hs +2/−0
• library/VectorBuilder/Builder.hs +10/−0
• library/VectorBuilder/MVector.hs +22/−0
• library/VectorBuilder/Private/Action.hs +44/−0
• library/VectorBuilder/Private/Builder.hs +68/−0
• library/VectorBuilder/Private/Prelude.hs +8/−0
• library/VectorBuilder/Vector.hs +17/−0
• tests/Main.hs +21/−0
• tests/Main/Sample.hs +37/−0
• vector-builder.cabal +83/−0

@@ -0,0 +1,22 @@+Copyright (c) 2016, Nikita Volkov++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.

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

@@ -0,0 +1,10 @@+module VectorBuilder.Builder+(+  Builder,+  empty,+  singleton,+  vector,+)+where++import VectorBuilder.Private.Builder

@@ -0,0 +1,22 @@+-- |+-- Extensions to the standard mutable Vector API.+module VectorBuilder.MVector+where++import VectorBuilder.Private.Prelude+import Data.Vector.Mutable+import qualified VectorBuilder.Private.Builder as A+import qualified VectorBuilder.Private.Action as B+++-- |+-- Construct a mutable vector from a builder.+{-# INLINABLE build #-}+build :: A.Builder element -> ST s (MVector s element)+build (A.Builder (B.Action actionFn)) =+  case actionFn 0 of+    (updateFn, size) ->+      do+        vector <- unsafeNew size+        updateFn vector+        return vector

@@ -0,0 +1,44 @@+module VectorBuilder.Private.Action+where++import VectorBuilder.Private.Prelude+import qualified Data.Vector.Mutable as A+import qualified Data.Vector as B+++newtype Action s element result =+  Action (Int -> (A.MVector s element -> ST s result, Int))++instance Functor (Action s element) where+  fmap fn (Action actionFn) =+    Action $ \size ->+    case actionFn size of+      (updateFn, newSize) ->+        (fmap fn . updateFn, newSize)++instance Applicative (Action s element) where+  pure result =+    Action (\size -> (const (pure result), size))+  (<*>) (Action actionFn1) (Action actionFn2) =+    Action actionFn+    where+      actionFn size =+        case actionFn1 size of+          (vectorFn1, size1) ->+            case actionFn2 size1 of+              (vectorFn2, size2) ->+                ((<*>) <$> vectorFn1 <*> vectorFn2, size2)+++snoc :: element -> Action s element ()+snoc element =+  Action (\size -> (\mVector -> A.unsafeWrite mVector size element, succ size))++append :: B.Vector element -> Action s element ()+append appendedVector =+  Action ((,) <$> vectorFn <*> size)+  where+    vectorFn currentSize mVector =+      B.ifoldM' (\_ index element -> A.unsafeWrite mVector (currentSize + index) element) () appendedVector+    size currentSize =+      B.length appendedVector + currentSize

@@ -0,0 +1,68 @@+module VectorBuilder.Private.Builder+where++import VectorBuilder.Private.Prelude+import qualified VectorBuilder.Private.Action as A+import qualified Data.Vector as B+++-- |+-- An abstraction over the size of a vector for the process of its construction.+-- +-- It postpones the actual construction of a vector until the execution of the builder.+newtype Builder element =+  Builder (forall s. A.Action s element ())++-- |+-- Provides support for /O(1)/ concatenation.+instance Monoid (Builder element) where+  mempty =+    VectorBuilder.Private.Builder.empty+  mappend =+    prepend++-- |+-- Provides support for /O(1)/ concatenation.+instance Semigroup (Builder element) where+  (<>) =+    prepend+++-- * Initialisation++-- |+-- Empty builder.+empty :: Builder element+empty =+  Builder (pure ())++-- |+-- Builder of a single element.+singleton :: element -> Builder element+singleton element =+  Builder (A.snoc element)++-- |+-- Builder from a vector of elements.+vector :: B.Vector element -> Builder element+vector vector =+  Builder (A.append vector)+++-- * Updates++snoc :: element -> Builder element -> Builder element+snoc element (Builder action) =+  Builder (action *> A.snoc element)++cons :: element -> Builder element -> Builder element+cons element (Builder action) =+  Builder (A.snoc element *> action)++prepend :: Builder element -> Builder element -> Builder element+prepend (Builder action1) (Builder action2) =+  Builder (action1 *> action2)++append :: Builder element -> Builder element -> Builder element+append (Builder action1) (Builder action2) =+  Builder (action1 <* action2)

@@ -0,0 +1,8 @@+module VectorBuilder.Private.Prelude+(+  module Exports,+)+where++import BasePrelude as Exports hiding ((<>))+import Data.Semigroup as Exports (Semigroup(..))

@@ -0,0 +1,17 @@+-- |+-- Extensions to the standard immutable Vector API.+module VectorBuilder.Vector+where++import VectorBuilder.Private.Prelude+import Data.Vector+import qualified VectorBuilder.Private.Builder as A+import qualified VectorBuilder.MVector as B+++-- |+-- Construct a vector from a builder.+{-# INLINE build #-}+build :: A.Builder element -> Vector element+build builder =+  runST (B.build builder >>= unsafeFreeze)

@@ -0,0 +1,21 @@+module Main where++import Rebase.Prelude+import Test.Tasty+import Test.Tasty.Runners+import Test.Tasty.HUnit+import Test.Tasty.QuickCheck+import qualified VectorBuilder.Builder as A+import qualified VectorBuilder.Vector as B+import qualified Main.Sample as C+++main =+  defaultMain $+  testGroup "All tests"+  [+    testProperty "" $ \(samples :: [C.Sample Int]) ->+      foldMap C.toVector samples ===+      B.build (foldMap C.toBuilder samples)+  ]+

@@ -0,0 +1,37 @@+module Main.Sample where++import Rebase.Prelude+import Test.QuickCheck.Instances+import qualified VectorBuilder.Builder as A+import qualified Rebase.Data.Vector as B+import qualified Test.Tasty.QuickCheck as C+++data Sample a =+  Empty |+  Singleton a |+  Vector (Vector a)+  deriving (Show)++toBuilder :: Sample a -> A.Builder a+toBuilder =+  \case+    Empty -> A.empty+    Singleton a -> A.singleton a+    Vector a -> A.vector a++toVector :: Sample a -> Vector a+toVector =+  \case+    Empty -> B.empty+    Singleton a -> B.singleton a+    Vector a -> a++instance C.Arbitrary a => C.Arbitrary (Sample a) where+  arbitrary =+    do+      constructorIndex <- C.choose (0 :: Int, 2)+      case constructorIndex of+        0 -> return Empty+        1 -> C.arbitrary >>= return . Singleton+        2 -> C.arbitrary >>= return . Vector

@@ -0,0 +1,83 @@+name:+  vector-builder+version:+  0.1+synopsis:+  Vector builder+description:+  An API for efficient construction of vectors with abstraction over their size.+category:+  Vector+homepage:+  https://github.com/nikita-volkov/vector-builder+bug-reports:+  https://github.com/nikita-volkov/vector-builder/issues +author:+  Nikita Volkov <nikita.y.volkov@mail.ru>+maintainer:+  Nikita Volkov <nikita.y.volkov@mail.ru>+copyright:+  (c) 2016, Nikita Volkov+license:+  MIT+license-file:+  LICENSE+build-type:+  Simple+cabal-version:+  >=1.10+++source-repository head+  type:+    git+  location:+    git://github.com/nikita-volkov/vector-builder.git+++library+  hs-source-dirs:+    library+  default-extensions:+    Arrows, BangPatterns, ConstraintKinds, DataKinds, DefaultSignatures, DeriveDataTypeable, DeriveFoldable, DeriveFunctor, DeriveGeneric, DeriveTraversable, EmptyDataDecls, FlexibleContexts, FlexibleInstances, FunctionalDependencies, GADTs, GeneralizedNewtypeDeriving, LambdaCase, LiberalTypeSynonyms, MagicHash, MultiParamTypeClasses, MultiWayIf, NoImplicitPrelude, NoMonomorphismRestriction, OverloadedStrings, PatternGuards, ParallelListComp, QuasiQuotes, RankNTypes, RecordWildCards, ScopedTypeVariables, StandaloneDeriving, TemplateHaskell, TupleSections, TypeFamilies, TypeOperators, UnboxedTuples+  default-language:+    Haskell2010+  other-modules:+    VectorBuilder.Private.Prelude+    VectorBuilder.Private.Action+    VectorBuilder.Private.Builder+  exposed-modules:+    VectorBuilder.Builder+    VectorBuilder.MVector+    VectorBuilder.Vector+  build-depends:+    primitive >= 0.6 && < 0.7,+    vector == 0.11.*,+    semigroups >= 0.16 && < 0.20,+    base-prelude < 2,+    base >= 4.6 && < 5+++test-suite tests+  type:+    exitcode-stdio-1.0+  hs-source-dirs:+    tests+  main-is:+    Main.hs+  other-modules:+    Main.Sample+  default-extensions:+    Arrows, BangPatterns, ConstraintKinds, DataKinds, DefaultSignatures, DeriveDataTypeable, DeriveFoldable, DeriveFunctor, DeriveGeneric, DeriveTraversable, EmptyDataDecls, FlexibleContexts, FlexibleInstances, FunctionalDependencies, GADTs, GeneralizedNewtypeDeriving, LambdaCase, LiberalTypeSynonyms, MagicHash, MultiParamTypeClasses, MultiWayIf, NoImplicitPrelude, NoMonomorphismRestriction, OverloadedStrings, PatternGuards, ParallelListComp, QuasiQuotes, RankNTypes, RecordWildCards, ScopedTypeVariables, StandaloneDeriving, TemplateHaskell, TupleSections, TypeFamilies, TypeOperators, UnboxedTuples+  default-language:+    Haskell2010+  build-depends:+    -- testing:+    tasty == 0.11.*,+    tasty-quickcheck == 0.8.*,+    tasty-hunit == 0.9.*,+    quickcheck-instances >= 0.3.11 && < 0.4,+    -- +    vector-builder,+    -- +    rebase