collate (empty) → 0.1.0.0
raw patch · 5 files changed
+512/−0 lines, 5 filesdep +QuickCheckdep +basedep +collate
Dependencies added: QuickCheck, base, collate, containers, lens, primitive, test-framework, test-framework-quickcheck2, transformers, vector
Files
- CHANGELOG.md +4/−0
- LICENSE +202/−0
- collate.cabal +65/−0
- src/Data/Collate.hs +197/−0
- test/CollateTest.hs +44/−0
+ CHANGELOG.md view
@@ -0,0 +1,4 @@+# 0.1.0.0++Initial version.+
+ LICENSE view
@@ -0,0 +1,202 @@++ Apache License+ Version 2.0, January 2004+ http://www.apache.org/licenses/++ TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION++ 1. Definitions.++ "License" shall mean the terms and conditions for use, reproduction,+ and distribution as defined by Sections 1 through 9 of this document.++ "Licensor" shall mean the copyright owner or entity authorized by+ the copyright owner that is granting the License.++ "Legal Entity" shall mean the union of the acting entity and all+ other entities that control, are controlled by, or are under common+ control with that entity. For the purposes of this definition,+ "control" means (i) the power, direct or indirect, to cause the+ direction or management of such entity, whether by contract or+ otherwise, or (ii) ownership of fifty percent (50%) or more of the+ outstanding shares, or (iii) beneficial ownership of such entity.++ "You" (or "Your") shall mean an individual or Legal Entity+ exercising permissions granted by this License.++ "Source" form shall mean the preferred form for making modifications,+ including but not limited to software source code, documentation+ source, and configuration files.++ "Object" form shall mean any form resulting from mechanical+ transformation or translation of a Source form, including but+ not limited to compiled object code, generated documentation,+ and conversions to other media types.++ "Work" shall mean the work of authorship, whether in Source or+ Object form, made available under the License, as indicated by a+ copyright notice that is included in or attached to the work+ (an example is provided in the Appendix below).++ "Derivative Works" shall mean any work, whether in Source or Object+ form, that is based on (or derived from) the Work and for which the+ editorial revisions, annotations, elaborations, or other modifications+ represent, as a whole, an original work of authorship. For the purposes+ of this License, Derivative Works shall not include works that remain+ separable from, or merely link (or bind by name) to the interfaces of,+ the Work and Derivative Works thereof.++ "Contribution" shall mean any work of authorship, including+ the original version of the Work and any modifications or additions+ to that Work or Derivative Works thereof, that is intentionally+ submitted to Licensor for inclusion in the Work by the copyright owner+ or by an individual or Legal Entity authorized to submit on behalf of+ the copyright owner. For the purposes of this definition, "submitted"+ means any form of electronic, verbal, or written communication sent+ to the Licensor or its representatives, including but not limited to+ communication on electronic mailing lists, source code control systems,+ and issue tracking systems that are managed by, or on behalf of, the+ Licensor for the purpose of discussing and improving the Work, but+ excluding communication that is conspicuously marked or otherwise+ designated in writing by the copyright owner as "Not a Contribution."++ "Contributor" shall mean Licensor and any individual or Legal Entity+ on behalf of whom a Contribution has been received by Licensor and+ subsequently incorporated within the Work.++ 2. Grant of Copyright License. Subject to the terms and conditions of+ this License, each Contributor hereby grants to You a perpetual,+ worldwide, non-exclusive, no-charge, royalty-free, irrevocable+ copyright license to reproduce, prepare Derivative Works of,+ publicly display, publicly perform, sublicense, and distribute the+ Work and such Derivative Works in Source or Object form.++ 3. Grant of Patent License. Subject to the terms and conditions of+ this License, each Contributor hereby grants to You a perpetual,+ worldwide, non-exclusive, no-charge, royalty-free, irrevocable+ (except as stated in this section) patent license to make, have made,+ use, offer to sell, sell, import, and otherwise transfer the Work,+ where such license applies only to those patent claims licensable+ by such Contributor that are necessarily infringed by their+ Contribution(s) alone or by combination of their Contribution(s)+ with the Work to which such Contribution(s) was submitted. If You+ institute patent litigation against any entity (including a+ cross-claim or counterclaim in a lawsuit) alleging that the Work+ or a Contribution incorporated within the Work constitutes direct+ or contributory patent infringement, then any patent licenses+ granted to You under this License for that Work shall terminate+ as of the date such litigation is filed.++ 4. Redistribution. You may reproduce and distribute copies of the+ Work or Derivative Works thereof in any medium, with or without+ modifications, and in Source or Object form, provided that You+ meet the following conditions:++ (a) You must give any other recipients of the Work or+ Derivative Works a copy of this License; and++ (b) You must cause any modified files to carry prominent notices+ stating that You changed the files; and++ (c) You must retain, in the Source form of any Derivative Works+ that You distribute, all copyright, patent, trademark, and+ attribution notices from the Source form of the Work,+ excluding those notices that do not pertain to any part of+ the Derivative Works; and++ (d) If the Work includes a "NOTICE" text file as part of its+ distribution, then any Derivative Works that You distribute must+ include a readable copy of the attribution notices contained+ within such NOTICE file, excluding those notices that do not+ pertain to any part of the Derivative Works, in at least one+ of the following places: within a NOTICE text file distributed+ as part of the Derivative Works; within the Source form or+ documentation, if provided along with the Derivative Works; or,+ within a display generated by the Derivative Works, if and+ wherever such third-party notices normally appear. The contents+ of the NOTICE file are for informational purposes only and+ do not modify the License. You may add Your own attribution+ notices within Derivative Works that You distribute, alongside+ or as an addendum to the NOTICE text from the Work, provided+ that such additional attribution notices cannot be construed+ as modifying the License.++ You may add Your own copyright statement to Your modifications and+ may provide additional or different license terms and conditions+ for use, reproduction, or distribution of Your modifications, or+ for any such Derivative Works as a whole, provided Your use,+ reproduction, and distribution of the Work otherwise complies with+ the conditions stated in this License.++ 5. Submission of Contributions. Unless You explicitly state otherwise,+ any Contribution intentionally submitted for inclusion in the Work+ by You to the Licensor shall be under the terms and conditions of+ this License, without any additional terms or conditions.+ Notwithstanding the above, nothing herein shall supersede or modify+ the terms of any separate license agreement you may have executed+ with Licensor regarding such Contributions.++ 6. Trademarks. This License does not grant permission to use the trade+ names, trademarks, service marks, or product names of the Licensor,+ except as required for reasonable and customary use in describing the+ origin of the Work and reproducing the content of the NOTICE file.++ 7. Disclaimer of Warranty. Unless required by applicable law or+ agreed to in writing, Licensor provides the Work (and each+ Contributor provides its Contributions) on an "AS IS" BASIS,+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or+ implied, including, without limitation, any warranties or conditions+ of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A+ PARTICULAR PURPOSE. You are solely responsible for determining the+ appropriateness of using or redistributing the Work and assume any+ risks associated with Your exercise of permissions under this License.++ 8. Limitation of Liability. In no event and under no legal theory,+ whether in tort (including negligence), contract, or otherwise,+ unless required by applicable law (such as deliberate and grossly+ negligent acts) or agreed to in writing, shall any Contributor be+ liable to You for damages, including any direct, indirect, special,+ incidental, or consequential damages of any character arising as a+ result of this License or out of the use or inability to use the+ Work (including but not limited to damages for loss of goodwill,+ work stoppage, computer failure or malfunction, or any and all+ other commercial damages or losses), even if such Contributor+ has been advised of the possibility of such damages.++ 9. Accepting Warranty or Additional Liability. While redistributing+ the Work or Derivative Works thereof, You may choose to offer,+ and charge a fee for, acceptance of support, warranty, indemnity,+ or other liability obligations and/or rights consistent with this+ License. However, in accepting such obligations, You may act only+ on Your own behalf and on Your sole responsibility, not on behalf+ of any other Contributor, and only if You agree to indemnify,+ defend, and hold each Contributor harmless for any liability+ incurred by, or claims asserted against, such Contributor by reason+ of your accepting any such warranty or additional liability.++ END OF TERMS AND CONDITIONS++ APPENDIX: How to apply the Apache License to your work.++ To apply the Apache License to your work, attach the following+ boilerplate notice, with the fields enclosed by brackets "[]"+ replaced with your own identifying information. (Don't include+ the brackets!) The text should be enclosed in the appropriate+ comment syntax for the file format. We also recommend that a+ file or class name and description of purpose be included on the+ same "printed page" as the copyright notice for easier+ identification within third-party archives.++ Copyright [yyyy] [name of copyright owner]++ Licensed under the Apache License, Version 2.0 (the "License");+ you may not use this file except in compliance with the License.+ You may obtain a copy of the License at++ http://www.apache.org/licenses/LICENSE-2.0++ Unless required by applicable law or agreed to in writing, software+ distributed under the License is distributed on an "AS IS" BASIS,+ WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.+ See the License for the specific language governing permissions and+ limitations under the License.
+ collate.cabal view
@@ -0,0 +1,65 @@+cabal-version: 1.12++-- This file has been generated from package.yaml by hpack version 0.33.0.+--+-- see: https://github.com/sol/hpack+--+-- hash: f67c86447a0c790d436c240b556273efdde3c5e0647dadec0b6598803cd7af4d++name: collate+version: 0.1.0.0+synopsis: An Applicative Functor for extracting parts of a stream of values+description: This provides a way to build up a computation that accesses many different+ indices (possibly out-of-order) of a large stream of values, and run it in a+ single scan over the stream. In essence, this implements a hash-join.+category: Algorithms+homepage: https://github.com/google/hs-collate#readme+bug-reports: https://github.com/google/hs-collate/issues+author: Andrew Pritchard <awpr@google.com>+maintainer: Andrew Pritchard <awpr@google.com>+copyright: 2018-2021 Google LLC+license: Apache-2.0+license-file: LICENSE+build-type: Simple+extra-source-files:+ CHANGELOG.md++source-repository head+ type: git+ location: https://github.com/google/hs-collate++library+ exposed-modules:+ Data.Collate+ other-modules:+ Paths_collate+ hs-source-dirs:+ src+ build-depends:+ base >=4.12 && <4.16+ , containers >=0.1 && <0.7+ , lens >=3.0 && <5.1+ , primitive >=0.6 && <0.8+ , transformers >=0.2 && <0.6+ , vector >=0.5 && <0.13+ default-language: Haskell2010++test-suite Collate-test+ type: exitcode-stdio-1.0+ main-is: CollateTest.hs+ other-modules:+ Paths_collate+ hs-source-dirs:+ test+ build-depends:+ QuickCheck+ , base >=4.12 && <4.16+ , collate+ , containers >=0.1 && <0.7+ , lens >=3.0 && <5.1+ , primitive >=0.6 && <0.8+ , test-framework+ , test-framework-quickcheck2+ , transformers >=0.2 && <0.6+ , vector >=0.5 && <0.13+ default-language: Haskell2010
+ src/Data/Collate.hs view
@@ -0,0 +1,197 @@+-- Copyright 2018-2021 Google LLC+--+-- Licensed under the Apache License, Version 2.0 (the "License");+-- you may not use this file except in compliance with the License.+-- You may obtain a copy of the License at+--+-- http://www.apache.org/licenses/LICENSE-2.0+--+-- Unless required by applicable law or agreed to in writing, software+-- distributed under the License is distributed on an "AS IS" BASIS,+-- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.+-- See the License for the specific language governing permissions and+-- limitations under the License.++{-# LANGUAGE RankNTypes #-}++-- | An Applicative Functor for extracting parts of a stream of values.+--+-- Basic usage involves building up a computation from calls to the 'sample'+-- function, then running the computation against a 'Foldable' of inputs.+-- Operationally, this makes one pass over the input in order, extracting each+-- of the values specified by calls to 'sample', then constructs the result+-- according to the Applicative structure.+--+-- Because this is written against 'ST', we can run 'Collate's purely, or+-- convert them to 'IO' as if by 'Control.Monad.ST.stToIO', and run them with+-- actual I/O interspersed. This means a 'Collate' can be driven by a+-- streaming abstraction such as+-- <https://hackage.haskell.org/package/conduit conduit> or+-- <https://hackage.haskell.org/package/pipes pipes>.+--+-- Finally, although 'Collate' itself doesn't admit any reasonable 'Monad'+-- implementation, it can be used with+-- <https://hackage.haskell.org/package/free free> to describe multi-pass+-- algorithms over (repeatable) streams. To implement 'Control.Monad.join',+-- we'd potentially need to look over the whole stream of inputs to be able to+-- construct the inner 'Collate' and determine which inputs it needs to+-- inspect. So, we'd need to make multiple passes. If we extended the type to+-- support multiple passes and gave it a 'Monad' instance that implemented+-- ('>>=') by making two passes, then the 'Applicative' instance would also be+-- required to make two passes for ('<*>'), because of the law that @('<*>') =+-- 'Control.Monad.ap'@ for any 'Monad'.++module Data.Collate+ ( -- * Types+ Collate(..), Collator(..)+ -- * Constructon+ , sample, bulkSample+ -- * Elimination+ , collate, collateOf+ -- ** Lower-level elimination APIs+ , withCollator, feedCollatorOf, feedCollator+ ) where++import Control.Arrow (first)+import Control.Monad (void)+import Control.Monad.ST (ST, runST)+import Control.Monad.Trans.Class (lift)+import Control.Monad.Trans.State.Strict+ ( StateT, get, modify, execStateT+ )+import Data.Functor.Const (Const(..))+import qualified Data.IntMap as IM+import Data.STRef (newSTRef, readSTRef, writeSTRef)++import Control.Lens+ ( Traversing', Sequenced+ , forMOf_, folded, traversed, ifoldMapOf, itraverseOf, taking+ )+import Control.Monad.Primitive (PrimMonad, PrimState, liftPrim)+import qualified Data.Vector.Mutable as V++-- | An collection of "callbacks" for extracting things from a stream of values.+--+-- This is generated by 'Collate', and holds many partially-applied+-- 'writeSTRef's, so that once they've all been called, some larger value can+-- be extracted.+newtype Collator m c = Collator+ { getCollator :: IM.IntMap (c -> ST (PrimState m) ())+ }++-- | 'Collator's can be combined by merging the contained maps.+instance Semigroup (Collator m c) where+ Collator l <> Collator r = Collator $ IM.unionWith (\x y c -> x c >> y c) l r++-- | An empty 'Collator' is just an empty map.+instance Monoid (Collator m c) where+ mempty = Collator IM.empty++-- | @Collate c a@ is a strategy for extracting an @a@ from a sequence of @c@s+-- in a single streaming pass over the input, even when lookups are specified+-- in arbitrary order.+--+-- Operationally, we build up a collection of mutable references, construct a+-- 'Collator' that describes how to fill all of them, construct an action that+-- will read the mutable references and return the ultimate result, iterate+-- over the input sequence to fill the mutable references, and finally run the+-- action to get the result.+newtype Collate c a = Collate+ { unCollate :: forall s. ST s (ST s a, Collator (ST s) c)+ }++instance Functor (Collate c) where+ fmap f (Collate go) = Collate $ fmap (first (fmap f)) go++instance Applicative (Collate c) where+ pure x = Collate $ return (return x, mempty)+ Collate goF <*> Collate goX = Collate $ do+ (mf, sf) <- goF+ (mx, sx) <- goX+ return (mf <*> mx, sf <> sx)++-- | Run a 'Collate' by providing an action in any 'PrimMonad' to drive the+-- 'Collator' it generates.+withCollator :: PrimMonad m => Collate c a -> (Collator m c -> m ()) -> m a+withCollator (Collate go) k = do+ (stA, Collator samples) <- liftPrim go+ -- Repack the Collator because 'm' might be different from 'ST (PrimState m)'.+ k (Collator samples)+ liftPrim stA++-- | Drive a 'Collator' with any 'Control.Lens.Fold' over the input type it+-- expects.+--+-- The 'Int' parameter is the index of the first item in the+-- 'Control.Lens.Fold' (so that you can supply the input in multiple chunks).+--+-- @+-- feedCollatorOf+-- :: PrimMonad m+-- => Fold s c -> Int -> Collator m c -> s -> m Int+-- @+feedCollatorOf+ :: forall m s c+ . PrimMonad m+ => Traversing' (->) (Const (Sequenced () (StateT Int (ST (PrimState m))))) s c+ -> Int -> Collator m c -> s -> m Int+feedCollatorOf l i0 (Collator samplers) s = liftPrim $ flip execStateT i0 $+ forMOf_ (taking n l) s $ \c -> do+ i <- get+ modify (+1)+ lift $ IM.findWithDefault (const (return ())) i samplers c+ where+ n = case IM.maxViewWithKey samplers of+ Nothing -> 0+ Just ((k, _), _) -> max 0 (k - i0 + 1)++-- | Drive a 'Collator' with any 'Foldable' containing its input type.+--+-- See 'feedCollatorOf'.+feedCollator+ :: forall m f c+ . (PrimMonad m, Foldable f)+ => Int -> Collator m c -> f c -> m Int+feedCollator = feedCollatorOf folded++-- | Run a 'Collate' on any 'Foldable'.+collate :: Foldable f => Collate c a -> f c -> a+collate = collateOf folded++-- | Run a 'Collate' on any 'Fold'.+--+-- The type signature looks complicated because we expand @Fold@ to avoid+-- incurring a dependency on @lens@, but it's effectively just:+--+-- @+-- collateOf :: Fold s c -> Collate c a -> s -> a+-- @+collateOf+ :: ( forall s0+ . Traversing' (->) (Const (Sequenced () (StateT Int (ST s0)))) s c+ )+ -> Collate c a -> s -> a+collateOf l c f = runST $ withCollator c $ \m -> void $ feedCollatorOf l 0 m f++-- | Construct a primitive 'Collate' that strictly extracts the result of a+-- function from the input at the given index.+sample :: Int -> (c -> a) -> Collate c a+sample i f = Collate $ do+ ref <- newSTRef (error "sample: Internal error: unfulfilled promise")+ return+ ( readSTRef ref+ , Collator $ IM.fromList [(i, \c -> writeSTRef ref $! f c)]+ )++-- | Construct a primitive 'Collate' that strictly extracts the result of a+-- function from many different indices.+bulkSample :: Traversable t => t Int -> (c -> a) -> Collate c (t a)+bulkSample t f = Collate $ do+ -- TODO(awpr): it's possible to combine length and collator construction into+ -- one traversal of @t@, but it's annoying to do.+ vec <- V.new (length t)+ let collator = ifoldMapOf traversed+ (\ iVec iInp -> Collator $+ IM.singleton iInp (\c -> V.write vec iVec $! f c))+ t+ return (itraverseOf traversed (\i _ -> V.read vec i) t, collator)
+ test/CollateTest.hs view
@@ -0,0 +1,44 @@+-- Copyright 2018-2021 Google LLC+--+-- Licensed under the Apache License, Version 2.0 (the "License");+-- you may not use this file except in compliance with the License.+-- You may obtain a copy of the License at+--+-- http://www.apache.org/licenses/LICENSE-2.0+--+-- Unless required by applicable law or agreed to in writing, software+-- distributed under the License is distributed on an "AS IS" BASIS,+-- WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.+-- See the License for the specific language governing permissions and+-- limitations under the License.++{-# LANGUAGE ScopedTypeVariables #-}++module Main(main) where++import qualified Data.List.NonEmpty as NE++import Test.Framework.Providers.QuickCheck2 (testProperty)+import Test.QuickCheck ((===), arbitrary, forAll)+import Test.Framework(defaultMain)++import Data.Collate++main :: IO ()+main = defaultMain+ [ testProperty "sample equivalent to indexing" $+ forAll ((NE.:|) <$> arbitrary <*> arbitrary) $+ \ (xs :: NE.NonEmpty Int) i0 ->+ let n = length xs+ i = i0 `mod` n+ in xs NE.!! i === collate (sample i id) xs+ , testProperty "bulkSample equivalent to indexing" $+ forAll ((NE.:|) <$> arbitrary <*> arbitrary) $+ \ (xs :: NE.NonEmpty Int) (is0 :: [Int]) ->+ let n = length xs+ is = map (`mod` n) is0+ in map (xs NE.!!) is === collate (bulkSample is id) xs+ , testProperty "not quadratic" $+ collate (bulkSample (replicate 10000 999999) id) [0..1000000] ===+ replicate 10000 (999999 :: Integer)+ ]