packages feed

strict-list (empty) → 0.1

raw patch · 6 files changed

+604/−0 lines, 6 filesdep +QuickCheckdep +basedep +quickcheck-instancessetup-changed

Dependencies added: QuickCheck, base, quickcheck-instances, rerebase, semigroupoids, strict-list, tasty, tasty-hunit, tasty-quickcheck

Files

+ LICENSE view
@@ -0,0 +1,22 @@+Copyright (c) 2019, 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.
+ Setup.hs view
@@ -0,0 +1,2 @@+import Distribution.Simple+main = defaultMain
+ library/StrictList.hs view
@@ -0,0 +1,315 @@+{-|+Definitions of strict linked list.++Most basic operations like `fmap`, `filter`, `<*>`+can only be implemented efficiently by producing an intermediate list in reversed order+and then reversing it to the original order.+These intermediate reversed functions are exposed by the API,+because they very well may be useful for efficient implementations of data-structures built on top of list.+E.g., the <http://hackage.haskell.org/package/deque "deque"> package exploits them heavily.++One useful rule of thumb would be that+whenever you see that a function has a reversed counterpart,+that counterpart is faster and hence if you don't care about the order or+intend to revert the list further down the line, you should give preference to that counterpart.+-}+module StrictList where++import StrictList.Prelude hiding (take, drop, takeWhile, dropWhile, reverse)++{-|+Strict linked list.+-}+data List a = Cons !a !(List a) | Nil deriving+  (Eq, Ord, Show, Read, Generic, Generic1, Data, Typeable)++instance IsList (List a) where+  type Item (List a) = a+  fromList = reverse . fromListReversed+  toList = foldr (:) []++instance Semigroup (List a) where+  (<>) = prependReversed . reverse++instance Monoid (List a) where+  mempty = Nil+  mappend = (<>)++instance Functor List where+  fmap f = reverse . mapReversed f++instance Foldable List where+  foldr step init = let+    loop = \ case+      Cons head tail -> step head (loop tail)+      _ -> init+    in loop+  foldl' step init = let+    loop !acc = \ case+      Cons head tail -> loop (step acc head) tail+      _ -> acc+    in loop init++instance Traversable List where+  sequenceA = foldr (liftA2 Cons) (pure Nil)++instance Apply List where+  (<.>) fList aList = apReversed (reverse fList) (reverse aList)++instance Applicative List where+  pure a = Cons a Nil+  (<*>) = (<.>)++instance Alt List where+  (<!>) = mappend++instance Plus List where+  zero = mempty++instance Alternative List where+  empty = zero+  (<|>) = (<!>)++instance Bind List where+  (>>-) ma amb = reverse (explodeReversed amb ma)+  join = reverse . joinReversed++instance Monad List where+  return = pure+  (>>=) = (>>-)++instance MonadPlus List where+  mzero = empty+  mplus = (<|>)++{-|+Reverse the list.+-}+reverse :: List a -> List a+reverse = foldl' (flip Cons) Nil++{-|+Leave only the specified amount of elements.+-}+take :: Int -> List a -> List a+take amount = reverse . takeReversed amount++{-|+Leave only the specified amount of elements, in reverse order.+-}+takeReversed :: Int -> List a -> List a+takeReversed = let+  loop !output !amount = if amount > 0+    then \ case+      Cons head tail -> loop (Cons head output) (pred amount) tail+      _ -> output+    else const output+  in loop Nil++{-|+Leave only the elements after the specified amount of first elements.+-}+drop :: Int -> List a -> List a+drop amount = if amount > 0+  then \ case+    Cons _ tail -> drop (pred amount) tail+    _ -> Nil+  else id++{-|+Leave only the elements satisfying the predicate.+-}+filter :: (a -> Bool) -> List a -> List a+filter predicate = reverse . filterReversed predicate++{-|+Leave only the elements satisfying the predicate,+producing a list in reversed order.+-}+filterReversed :: (a -> Bool) -> List a -> List a+filterReversed predicate = let+  loop !newList = \ case+    Cons head tail -> if predicate head+      then loop (Cons head newList) tail+      else loop newList tail+    Nil -> newList+  in loop Nil++{-|+Leave only the first elements satisfying the predicate.+-}+takeWhile :: (a -> Bool) -> List a -> List a+takeWhile predicate = reverse . takeWhileReversed predicate++{-|+Leave only the first elements satisfying the predicate,+producing a list in reversed order.+-}+takeWhileReversed :: (a -> Bool) -> List a -> List a+takeWhileReversed predicate = let+  loop !newList = \ case+    Cons head tail -> if predicate head+      then loop (Cons head newList) tail+      else newList+    _ -> newList+  in loop Nil++{-|+Drop the first elements satisfying the predicate.+-}+dropWhile :: (a -> Bool) -> List a -> List a+dropWhile predicate = \ case+  Cons head tail -> if predicate head+    then dropWhile predicate tail+    else Cons head tail+  Nil -> Nil++{-|+Same as @(`takeWhile` predicate . `reverse`)@.+E.g., ++>>> takeWhileFromEnding (> 2) (fromList [1,4,2,3,4,5])+fromList [5,4,3]+-}+takeWhileFromEnding :: (a -> Bool) -> List a -> List a+takeWhileFromEnding predicate = foldl'+  (\ newList a -> if predicate a+    then Cons a newList+    else Nil)+  Nil++{-|+Same as @(`dropWhile` predicate . `reverse`)@.+E.g., ++>>> dropWhileFromEnding (> 2) (fromList [1,4,2,3,4,5])+fromList [2,4,1]+-}+dropWhileFromEnding :: (a -> Bool) -> List a -> List a+dropWhileFromEnding predicate = let+  loop confirmed unconfirmed = \ case+    Cons head tail -> if predicate head+      then loop confirmed (Cons head unconfirmed) tail+      else let+        !newConfirmed = Cons head unconfirmed+        in loop newConfirmed newConfirmed tail+    Nil -> confirmed+  in loop Nil Nil++{-|+Get the first element and the remainder of the list if it's not empty.+-}+uncons :: List a -> Maybe (a, List a)+uncons = \ case+  Cons head tail -> Just (head, tail)+  _ -> Nothing++{-|+Get the first element, if list is not empty.+-}+head :: List a -> Maybe a+head = \ case+  Cons head _ -> Just head+  _ -> Nothing++{-|+Get the last element, if list is not empty.+-}+last :: List a -> Maybe a+last = let+  loop !previous = \ case+    Cons head tail -> loop (Just head) tail+    _ -> previous+  in loop Nothing++{-|+Get all elements of the list but the first one.+-}+tail :: List a -> List a+tail = \ case+  Cons _ tail -> tail+  Nil -> Nil++{-|+Get all elements but the last one.+-}+init :: List a -> List a+init = reverse . initReversed++{-|+Get all elements but the last one, producing the results in reverse order.+-}+initReversed :: List a -> List a+initReversed = let+  loop !confirmed !unconfirmed = \ case+    Cons head tail -> loop unconfirmed (Cons head unconfirmed) tail+    _ -> confirmed+  in loop Nil Nil++{-|+Apply the functions in the left list to elements in the right one.+-}+apZipping :: List (a -> b) -> List a -> List b+apZipping left right = apZippingReversed (reverse left) (reverse right)++{-|+Apply the functions in the left list to elements in the right one,+producing a list of results in reversed order.+-}+apZippingReversed :: List (a -> b) -> List a -> List b+apZippingReversed = let+  loop bList = \ case+    Cons f fTail -> \ case+      Cons a aTail -> loop (Cons (f a) bList) fTail aTail+      _ -> bList+    _ -> const bList+  in loop Nil+++-- ** Reversed intermediate functions used in instances+-------------------------++{-|+Construct from a lazy list in reversed order.+-}+fromListReversed :: [a] -> List a+fromListReversed = foldl' (flip Cons) Nil++{-|+Add elements of the left list in reverse order+in the beginning of the right list.+ -}+prependReversed :: List a -> List a -> List a+prependReversed = \ case+  Cons head tail -> prependReversed tail . Cons head+  Nil -> id++{-|+Map producing a list in reversed order.+-}+mapReversed :: (a -> b) -> List a -> List b+mapReversed f = let+  loop !newList = \ case+    Cons head tail -> loop (Cons (f head) newList) tail+    _ -> newList+  in loop Nil++{-|+Apply the functions in the left list to every element in the right one,+producing a list of results in reversed order.+-}+apReversed :: List (a -> b) -> List a -> List b+apReversed fList aList = foldl' (\ z f -> foldl' (\ z a -> Cons (f a) z) z aList) Nil fList++{-|+Use a function to produce a list of lists and then concat them sequentially,+producing the results in reversed order.+-}+explodeReversed :: (a -> List b) -> List a -> List b+explodeReversed amb = foldl' (\ z -> foldl' (flip Cons) z . amb) Nil++{-|+Join (concat) producing results in reversed order.+-}+joinReversed :: List (List a) -> List a+joinReversed = foldl' (foldl' (flip Cons)) Nil
+ library/StrictList/Prelude.hs view
@@ -0,0 +1,88 @@+module StrictList.Prelude+(+  module Exports,+)+where+++-- base+-------------------------+import Control.Applicative as Exports+import Control.Arrow as Exports+import Control.Category as Exports+import Control.Concurrent as Exports+import Control.Exception as Exports+import Control.Monad as Exports hiding (join, fail, mapM_, sequence_, forM_, msum, mapM, sequence, forM)+import Control.Monad.IO.Class as Exports+import Control.Monad.Fail as Exports+import Control.Monad.Fix as Exports hiding (fix)+import Control.Monad.ST as Exports+import Data.Bits as Exports+import Data.Bool as Exports+import Data.Char as Exports+import Data.Coerce as Exports+import Data.Complex as Exports+import Data.Data as Exports+import Data.Dynamic as Exports+import Data.Either as Exports+import Data.Fixed as Exports+import Data.Foldable as Exports hiding (toList)+import Data.Function as Exports hiding (id, (.))+import Data.Functor as Exports+import Data.Functor.Identity as Exports+import Data.Int as Exports+import Data.IORef as Exports+import Data.Ix as Exports+import Data.List as Exports hiding (sortOn, isSubsequenceOf, uncons, concat, foldr, foldl1, maximum, minimum, product, sum, all, and, any, concatMap, elem, foldl, foldr1, notElem, or, find, maximumBy, minimumBy, mapAccumL, mapAccumR, foldl')+import Data.Maybe as Exports+import Data.Monoid as Exports hiding (Last(..), First(..), (<>), Alt)+import Data.Ord as Exports+import Data.Proxy as Exports+import Data.Ratio as Exports+import Data.Semigroup as Exports+import Data.STRef as Exports+import Data.String as Exports+import Data.Traversable as Exports+import Data.Tuple as Exports+import Data.Unique as Exports+import Data.Version as Exports+import Data.Word as Exports+import Debug.Trace as Exports+import Foreign.ForeignPtr as Exports+import Foreign.Ptr as Exports+import Foreign.StablePtr as Exports+import Foreign.Storable as Exports hiding (sizeOf, alignment)+import GHC.Conc as Exports hiding (withMVar, threadWaitWriteSTM, threadWaitWrite, threadWaitReadSTM, threadWaitRead)+import GHC.Exts as Exports (lazy, inline, sortWith, groupWith, IsList(..))+import GHC.Generics as Exports (Generic, Generic1)+import GHC.IO.Exception as Exports+import Numeric as Exports+import Prelude as Exports hiding (fail, concat, foldr, mapM_, sequence_, foldl1, maximum, minimum, product, sum, all, and, any, concatMap, elem, foldl, foldr1, notElem, or, mapM, sequence, id, (.))+import System.Environment as Exports+import System.Exit as Exports+import System.IO as Exports+import System.IO.Error as Exports+import System.IO.Unsafe as Exports+import System.Mem as Exports+import System.Mem.StableName as Exports+import System.Timeout as Exports+import Text.ParserCombinators.ReadP as Exports (ReadP, ReadS, readP_to_S, readS_to_P)+import Text.ParserCombinators.ReadPrec as Exports (ReadPrec, readPrec_to_P, readP_to_Prec, readPrec_to_S, readS_to_Prec)+import Text.Printf as Exports (printf, hPrintf)+import Text.Read as Exports (Read(..), readMaybe, readEither)+import Unsafe.Coerce as Exports++-- semigroupoids+-------------------------+import Data.Semigroupoid as Exports+import Data.Bifunctor.Apply as Exports hiding (first, second)+import Data.Functor.Alt as Exports hiding (($>), many, some, optional)+import Data.Functor.Apply as Exports hiding (($>))+import Data.Functor.Bind as Exports hiding (($>))+import Data.Functor.Extend as Exports+import Data.Functor.Plus as Exports hiding (($>), some, many, optional)+import Data.Semigroup.Bifoldable as Exports+import Data.Semigroup.Bitraversable as Exports+import Data.Semigroup.Foldable as Exports+import Data.Semigroup.Traversable as Exports+import Data.Semigroupoid as Exports
+ strict-list.cabal view
@@ -0,0 +1,46 @@+name: strict-list+version: 0.1+synopsis: Strict linked list+description:+  Implementation of strict linked list with care taken about stack.+homepage: https://github.com/nikita-volkov/strict-list+bug-reports: https://github.com/nikita-volkov/strict-list/issues+author: Nikita Volkov <nikita.y.volkov@mail.ru>+maintainer: Nikita Volkov <nikita.y.volkov@mail.ru>+copyright: (c) 2019, 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/strict-list.git++library+  hs-source-dirs: library+  default-extensions: BangPatterns, DeriveDataTypeable, DeriveGeneric, DeriveFunctor, DeriveTraversable, FlexibleContexts, FlexibleInstances, LambdaCase, NoImplicitPrelude, RankNTypes, ScopedTypeVariables, StandaloneDeriving, TypeApplications, TypeFamilies+  default-language: Haskell2010+  exposed-modules:+    StrictList+  other-modules:+    StrictList.Prelude+  build-depends:+    base >=4.9 && <5,+    semigroupoids >=5.3 && <6++test-suite test+  type: exitcode-stdio-1.0+  hs-source-dirs: test+  default-extensions: BangPatterns, DeriveDataTypeable, DeriveGeneric, DeriveFunctor, DeriveTraversable, FlexibleContexts, FlexibleInstances, LambdaCase, NoImplicitPrelude, RankNTypes, ScopedTypeVariables, StandaloneDeriving, TypeApplications, TypeFamilies+  default-language: Haskell2010+  main-is:+    Main.hs+  build-depends:+    strict-list,+    QuickCheck >=2.8.1 && <3,+    quickcheck-instances >=0.3.11 && <0.4,+    rerebase <2,+    tasty >=0.12 && <2,+    tasty-hunit >=0.9 && <0.11,+    tasty-quickcheck >=0.9 && <0.11
+ test/Main.hs view
@@ -0,0 +1,131 @@+module Main where++import Prelude hiding (reverse, toList, List, filter, take, drop, takeWhile, dropWhile, head, last, tail, init)+import GHC.Exts as Exports (IsList(..))+import Test.QuickCheck.Instances+import Test.Tasty+import Test.Tasty.Runners+import Test.Tasty.HUnit+import Test.Tasty.QuickCheck+import StrictList+import qualified Data.List as Lazy+import qualified Test.QuickCheck as QuickCheck+import qualified Test.QuickCheck.Property as QuickCheck+++main =+  defaultMain $+  testGroup "" $+  [+    testProperty "toList" $ forAll strictAndLazyListGen $ \ (strict, lazy) ->+    toList strict === lazy+    ,+    testProperty "fromList" $ forAll lazyListGen $ \ lazy ->+    toList (fromList @(List Word8) lazy) === lazy+    ,+    testProperty "reverse" $ forAll strictAndLazyListGen $ \ (strict, lazy) ->+    toList (reverse strict) === Lazy.reverse lazy+    ,+    testProperty "take" $ forAll ((,) <$> arbitrary <*> strictAndLazyListGen) $ \ (amount, (strict, lazy)) ->+    toList (take amount strict) === Lazy.take amount lazy+    ,+    testProperty "drop" $ forAll ((,) <$> arbitrary <*> strictAndLazyListGen) $ \ (amount, (strict, lazy)) ->+    toList (drop amount strict) === Lazy.drop amount lazy+    ,+    testProperty "filter" $ forAll ((,) <$> predicateGen <*> strictAndLazyListGen) $ \ (predicate, (strict, lazy)) ->+    toList (filter predicate strict) === Lazy.filter predicate lazy+    ,+    testProperty "filterReversed" $ forAll ((,) <$> predicateGen <*> strictAndLazyListGen) $ \ (predicate, (strict, lazy)) ->+    toList (filterReversed predicate strict) === Lazy.reverse (Lazy.filter predicate lazy)+    ,+    testProperty "takeWhile" $ forAll ((,) <$> predicateGen <*> strictAndLazyListGen) $ \ (predicate, (strict, lazy)) ->+    toList (takeWhile predicate strict) === Lazy.takeWhile predicate lazy+    ,+    testProperty "takeWhileReversed" $ forAll ((,) <$> predicateGen <*> strictAndLazyListGen) $ \ (predicate, (strict, lazy)) ->+    toList (takeWhileReversed predicate strict) === Lazy.reverse (Lazy.takeWhile predicate lazy)+    ,+    testProperty "dropWhile" $ forAll ((,) <$> predicateGen <*> strictAndLazyListGen) $ \ (predicate, (strict, lazy)) ->+    toList (dropWhile predicate strict) === Lazy.dropWhile predicate lazy+    ,+    testProperty "takeWhileFromEnding" $ forAll ((,) <$> predicateGen <*> strictAndLazyListGen) $ \ (predicate, (strict, lazy)) ->+    toList (takeWhileFromEnding predicate strict) === Lazy.takeWhile predicate (Lazy.reverse lazy)+    ,+    testProperty "dropWhileFromEnding" $ forAll ((,) <$> predicateGen <*> strictAndLazyListGen) $ \ (predicate, (strict, lazy)) ->+    toList (dropWhileFromEnding predicate strict) === Lazy.dropWhile predicate (Lazy.reverse lazy)+    ,+    testProperty "head" $ forAll strictAndLazyListGen $ \ (strict, lazy) ->+    head strict === listToMaybe lazy+    ,+    testProperty "last" $ forAll strictAndLazyListGen $ \ (strict, lazy) ->+    last strict === listToMaybe (Lazy.reverse lazy)+    ,+    testProperty "tail" $ forAll strictAndLazyListGen $ \ (strict, lazy) ->+    toList (tail strict) === Lazy.drop 1 lazy+    ,+    testProperty "init" $ forAll strictAndLazyListGen $ \ (strict, lazy) ->+    toList (init strict) === Lazy.take (Lazy.length lazy - 1) lazy+    ,+    testProperty "initReversed" $ forAll strictAndLazyListGen $ \ (strict, lazy) ->+    toList (initReversed strict) === Lazy.reverse (Lazy.take (Lazy.length lazy - 1) lazy)+    ,+    testProperty "fromListReversed" $ forAll strictAndLazyListGen $ \ (strict, lazy) ->+    toList (fromListReversed lazy) === Lazy.reverse lazy+    ,+    testProperty "prependReversed" $ forAll ((,) <$> strictAndLazyListGen <*> strictAndLazyListGen) $ \ ((strict1, lazy1), (strict2, lazy2)) ->+    toList (prependReversed strict1 strict2) === Lazy.reverse lazy1 <> lazy2+    ,+    testProperty "mapReversed" $ forAll ((,) <$> predicateGen <*> strictAndLazyListGen) $ \ (mapper, (strict, lazy)) ->+    toList (mapReversed mapper strict) === Lazy.reverse (fmap mapper lazy)+    ,+    testProperty "apReversed" $ forAll ((,) <$> strictAndLazyListGen <*> strictAndLazyListGen) $ \ ((strict1, lazy1), (strict2, lazy2)) ->+    toList (apReversed (fmap (,) strict1) strict2) === Lazy.reverse ((,) <$> lazy1 <*> lazy2)+    ,+    testProperty "apZippingReversed" $ forAll ((,) <$> strictAndLazyListGen <*> strictAndLazyListGen) $ \ ((strict1, lazy1), (strict2, lazy2)) ->+    toList (apZippingReversed (fmap (,) strict1) strict2) === Lazy.reverse (Lazy.zip lazy1 lazy2)+    ,+    testProperty "explodeReversed" $ forAll ((,) <$> strictAndLazyKleisliGen <*> strictAndLazyListGen) $ \ ((strictK, lazyK), (strict, lazy)) ->+    toList (explodeReversed strictK strict) === Lazy.reverse (lazy >>= lazyK)+    ,+    testProperty "fmap" $ forAll ((,) <$> predicateGen <*> strictAndLazyListGen) $ \ (mapper, (strict, lazy)) ->+    toList (fmap mapper strict) === fmap mapper lazy+    ,+    testProperty "<*>" $ forAll ((,) <$> strictAndLazyListGen <*> strictAndLazyListGen) $ \ ((strict1, lazy1), (strict2, lazy2)) ->+    toList ((,) <$> strict1 <*> strict2) === ((,) <$> lazy1 <*> lazy2)+    ,+    testProperty "<>" $ forAll ((,) <$> strictAndLazyListGen <*> strictAndLazyListGen) $ \ ((strict1, lazy1), (strict2, lazy2)) ->+    toList (strict1 <> strict2) === (lazy1 <> lazy2)+    ,+    testProperty "<|>" $ forAll ((,) <$> strictAndLazyListGen <*> strictAndLazyListGen) $ \ ((strict1, lazy1), (strict2, lazy2)) ->+    toList (strict1 <|> strict2) === (lazy1 <|> lazy2)+    ,+    testProperty ">>=" $ forAll ((,) <$> strictAndLazyKleisliGen <*> strictAndLazyListGen) $ \ ((strictK, lazyK), (strict, lazy)) ->+    toList (strict >>= strictK) === (lazy >>= lazyK)+  ]+  where+    lazyListGen = arbitrary @[Word8]+    strictAndLazyListGen = do+      lazy <- lazyListGen+      return (foldr Cons Nil lazy, lazy)+    predicateGen = do+      op <- elements [(>), (>=), (==), (<=), (<)]+      x <- arbitrary @Word8+      return (op x)+    strictAndLazyKleisliGen = do+      lazy <- lazyListGen+      let+        lazyK = \ x -> join (replicate (fromIntegral x) lazy)+        strictK = foldr Cons Nil . lazyK+        in return (strictK, lazyK)++-- * Workarounds to satisfy QuickCheck's requirements,+-- when we need to generate a predicate.+-------------------------++instance Show (Word8 -> Bool) where+  show _ = "(Word8 -> Bool) function"++instance Show (Word8 -> List Word8) where+  show _ = "(Word8 -> List Word8) function"++instance Show (Word8 -> [Word8]) where+  show _ = "(Word8 -> [Word8]) function"