packages feed

reverse-list 0.2.0 → 0.3.0.0

raw patch · 5 files changed

+85/−75 lines, 5 filesdep ~base

Dependency ranges changed: base

Files

LICENSE view
@@ -1,4 +1,4 @@-Copyright Okuno Zankoku (c) 2021+Copyright Marseille Bouchard (c) 2022-2023  All rights reserved. @@ -13,7 +13,7 @@       disclaimer in the documentation and/or other materials provided       with the distribution. -    * Neither the name of Okuno Zankoku nor the names of other+    * Neither the name of Marseille Bouchard nor the names of other       contributors may be used to endorse or promote products derived       from this software without specific prior written permission.
README.md view
@@ -1,24 +1,24 @@ # reverse-list  The key idea of this library is to leverage the type system to control the performance characteristics of list-manipulation code.-It defines the type `RList`, which is a snoc-list rather than a cons-list.+It defines the type `Tsil`, which is a snoc-list rather than a cons-list. It also creates a symmetric module for cons-lists, which focuses on the efficient and safe use of linked lists.  Admittedly, parsing `String`s as in this example is bad for performance anyway, but the potential bugs are the same for any use of lists as accumulators: ```-import qualified Data.List.Snoc as RList+import qualified Data.List.Snoc as Tsil  parseSqlString :: String -> Maybe String parseSqlString str0 = case str0 of   '\'':rest -> loop "" rest   _ -> Nothing   where-  loop :: RList Char -> [Char] -> Maybe [Char]+  loop :: Tsil Char -> String -> Maybe (String, String)   loop acc [] = Nothing-  -- it is impossible to accidentally return the accumulator without reversing-  loop acc "\'" = Just $ Rlist.toList acc-  loop acc ('\'':'\'':rest) = loop (Snoc acc '\'') rest-  loop acc (c:rest) = loop (Snoc acc c) rest+  loop acc ('\'':'\'':rest) = loop (acc `Snoc` '\'') rest+  -- here, it is impossible to accidentally return the accumulator without reversing:+  loop acc ('\'':rest) = Just (Tsil.toList acc, rest)+  loop acc (c:rest) = loop (acc `Snoc` c) rest ```  Currently, we only support the basic introduction/elimination forms (though reasonably ergonomically), and conversions.
reverse-list.cabal view
@@ -1,6 +1,6 @@ cabal-version: 3.0 name: reverse-list-version: 0.2.0+version: 0.3.0.0 synopsis: reversed lists/snoc lists description: The key idea of this library is to leverage the type system to control the performance characteristics of list-manipulation code.   It defines the type `RList`, which is a snoc-list rather than a cons-list.@@ -9,9 +9,9 @@ category: Data homepage: https://github.com/edemko/reverse-list bug-reports: https://github.com/edemko/reverse-list/issues-author: Eric Demko+author: Marseille Bouchard maintainer: zankoku.okuno@gmail.com-copyright: 2021 Eric Demko+copyright: 2022-2023 Marseille Bouchard license: BSD-3-Clause license-file: LICENSE extra-source-files: README.md, CHANGELOG.md@@ -23,9 +23,9 @@     Data.List.Snoc   -- other-modules:   build-depends:-    , base >=4.14.3 && <4.16+    , base >=4.8.2 && <4.17     , containers >=0.6 && <0.7     , contiguous >= 0.6 && <0.7     , deepseq >=1.4 && <1.5   default-language: Haskell2010-  ghc-options: -O2 -Wall -Wunticked-promoted-constructors+  ghc-options: -Wall -Wunticked-promoted-constructors
src/Data/List/Cons.hs view
@@ -5,7 +5,7 @@ -- However, it can also be used in place of the "Prelude" list type: -- -- This module only exports functions that are efficient on linked lists. Many--- functions on that type ('Prelude.last' 'Data.List.isSuffixOf') though+-- functions on that type ('Prelude.last', 'Data.List.isSuffixOf') though -- technically implementable, do not represent the intended use of a linked list -- in terms of performance. --@@ -25,7 +25,7 @@  import Prelude hiding (head,tail) --- | As a counterpart to 'Data.List.Snoc.RList'/'Data.List.Snoc.Tsil'.+-- | As a counterpart to 'Data.List.Snoc.Tsil'. type List = ([])  {-# COMPLETE Nil, Cons #-}@@ -46,7 +46,7 @@  -- | @O(1)@ Append an element. ----- If you are looking for @snoc@, you should use an 'RList', or a finite sequence/queue type.+-- If you are looking for @snoc@, you should use an 'Data.List.Snoc.Tsil', or a finite sequence/queue type. cons :: a -> List a -> List a {-# INLINABLE cons #-} cons = (:)@@ -54,7 +54,7 @@ -- | @O(1)@ Access the first element and trailing portion of the list. -- See also 'head' and 'tail' if you only need one component. ----- If you are looking for @unsnoc@, you should use an 'RList', or a finite sequence/queue type.+-- If you are looking for @unsnoc@, you should use an 'Data.List.Snoc.Tsil', or a finite sequence/queue type. uncons :: List a -> Maybe (a, List a) {-# INLINABLE uncons #-} uncons [] = Nothing@@ -63,12 +63,14 @@ -- | @O(1)@ extract the first element of a list, if it exists. -- See also 'uncons' if you also need 'tail' at the same time. head :: List a -> Maybe a+{-# INLINABLE head #-} head Nil = Nothing head (Cons x _) = Just x  -- | @O(1)@ extract the elements of a list other than the last, if they exist. -- See also 'uncons' if you also need 'head' at the same time. tail :: List a -> Maybe (List a)+{-# INLINABLE tail #-} tail Nil = Nothing tail (Cons _ xs) = Just xs
src/Data/List/Snoc.hs view
@@ -11,12 +11,9 @@ -- We call it an `RList` because this is really just a vanilla list, but where -- the semantics are that the last-added thing (internally cons'ed) is -- understood to be at the \"end\" of the list.------ WARNING: the `Foldable` instance provides a `Foldable.toList`; this simply unwraps the `RList` rather than reversing it.--- If you need to convert from revered semantics to forward semantics, use this module's `toList`. module Data.List.Snoc-  ( RList-  , Tsil+  ( Tsil+  , RList   -- * Introduction and Elimination   , nil   , snoc@@ -57,87 +54,98 @@  -- | This datatype defines snoc-lists: lists with O(1) append and O(n) prepend. -- Underneath the hood, it is just a plain list, but understood as containing its elements in reverse order.-newtype RList a = RList { unRList :: [a] }-  deriving stock (Generic)+--+-- | See? It's \"List\" in reverse?+-- I dunno, I just think 'RList' is an inelegant name, and word-initial @/t͜s/@ is one of my favorite phonemes.+newtype Tsil a = Tsil { unTsil :: [a] }+  deriving stock (Generic,Eq)   deriving newtype (Functor,Applicative)-instance (NFData a) => NFData (RList a)+instance (NFData a) => NFData (Tsil a) -instance (Show a) => Show (RList a) where+instance (Show a) => Show (Tsil a) where   show = show . toList-instance (Read a) => Read (RList a) where+instance (Read a) => Read (Tsil a) where   readsPrec i = (fmap . first) fromList . readsPrec i -instance Semigroup (RList a) where-  (RList a) <> (RList b) = RList (b <> a)-instance Monoid (RList a) where+instance Foldable Tsil where+  {-# INLINABLE foldr #-}+  foldr _ z Nil = z+  foldr f z (xs `Snoc` x) = foldr f (x `f` z) xs++instance Semigroup (Tsil a) where+  (Tsil a) <> (Tsil b) = Tsil (b <> a)+instance Monoid (Tsil a) where   mempty = Nil -instance Alternative RList where+instance Alternative Tsil where   empty = mempty-  (RList a) <|> (RList b) = RList (b <|> a)+  (Tsil a) <|> (Tsil b) = Tsil (b <|> a) --- | See? It's \"List\" in reverse?--- I dunno, I just think 'RList' is an inelegant name, and word-initial @/t͜s/@ is one of my favorite phonemes.-type Tsil = RList+-- | I initially went with this boring name for reverse-lists.+-- However, I genuinely would rather write (and pronounce) 'Tsil'.+{-# DEPRECATED RList "Preferred spelling is `Tsil`" #-}+type RList = Tsil  {-# COMPLETE Nil, Snoc #-}  -- | An empty 'RList', such as 'nil'.-pattern Nil :: RList a-pattern Nil = RList []+pattern Nil :: Tsil a+pattern Nil = Tsil [] --- | The 'RList' consisting of initial and last elements, such as created by 'snoc'.-pattern Snoc :: RList a -> a -> RList a+-- | The 'Tsil' consisting of initial and last elements, such as created by 'snoc'.+pattern Snoc :: Tsil a -> a -> Tsil a pattern Snoc xs x <- (unsnoc -> Just (xs, x))   where Snoc = snoc --- | The empty 'RList'.-nil :: RList a+-- | The empty 'Tsil'.+nil :: Tsil a {-# INLINABLE nil #-}-nil = RList []+nil = Tsil []  -- | @O(1)@ Append an element. -- -- If you are looking for @cons@, you should use a plain list, or a finite sequence/queue type.-snoc :: RList a -> a -> RList a+snoc :: Tsil a -> a -> Tsil a {-# INLINABLE snoc #-}-snoc (RList xs) x = RList (x:xs)+snoc (Tsil xs) x = Tsil (x:xs)  -- | @O(1)@ Access the last element and initial portion of the list. -- See also 'last' and 'init' if you only need one component. -- -- If you are looking for @uncons@, you should use a plain list, or a finite sequence/queue type.-unsnoc :: RList a -> Maybe (RList a, a)+unsnoc :: Tsil a -> Maybe (Tsil a, a) {-# INLINABLE unsnoc #-}-unsnoc (RList []) = Nothing-unsnoc (RList (x:xs)) = Just (RList xs, x)+unsnoc (Tsil []) = Nothing+unsnoc (Tsil (x:xs)) = Just (Tsil xs, x) --- | Create a single-element 'RList'.-singleton :: a -> RList a+-- | Create a single-element 'Tsil'.+singleton :: a -> Tsil a {-# INLINE singleton #-}-singleton = RList . (:[])+singleton = Tsil . (:[]) --- | Test if an 'RList' is empty.-null :: RList a -> Bool+-- | Test if an 'Tsil' is empty.+null :: Tsil a -> Bool {-# INLINE null #-}-null (RList xs) = List.null xs+null (Tsil xs) = List.null xs  -- | @O(1)@ extract the last element of a list, if it exists. -- See also 'unsnoc' if you also need 'init' at the same time.-last :: RList a -> Maybe a+last :: Tsil a -> Maybe a+{-# INLINABLE last #-} last Nil = Nothing last (Snoc _ x) = Just x  -- | @O(1)@ extract the elements of a list other than the last, if they exist. -- See also 'unsnoc' if you also need 'last' at the same time.-init :: RList a -> Maybe (RList a)+init :: Tsil a -> Maybe (Tsil a)+{-# INLINABLE init #-} init Nil = Nothing init (Snoc xs _) = Just xs --- | Remove all 'Nothing's from an 'RList' of 'Maybe's.-catMaybes :: RList (Maybe a) -> RList a+-- | Remove all 'Nothing's from an 'Tsil' of 'Maybe's.+catMaybes :: Tsil (Maybe a) -> Tsil a {-# INLINE catMaybes #-}-catMaybes = RList . Maybe.catMaybes . unRList+catMaybes = Tsil . Maybe.catMaybes . unTsil  -- | @O(n)@ Convert to a plain list, maintaining order. --@@ -145,48 +153,48 @@ -- you're done building your list. -- -- See 'reverseOut' for when order doesn't matter.-toList :: RList a -> [a]+toList :: Tsil a -> [a] {-# INLINE toList #-}-toList (RList xs) = Prelude.reverse xs+toList (Tsil xs) = Prelude.reverse xs  -- | @O(n)@ Convert from a plain list, maintaining order. -- -- This is added for completion's sake, as I'm not sure you'll often need this adapter. -- -- See `toList` for the inverse, or `reverseIn` for when order doesn't matter.-fromList :: [a] -> RList a+fromList :: [a] -> Tsil a {-# INLINE fromList #-}-fromList = RList . Prelude.reverse+fromList = Tsil . Prelude.reverse --- | @O(0)@ Reverse an `RList`, returning a plain cons list.+-- | @O(0)@ Reverse an `Tsil`, returning a plain cons list. -- -- This is here so that when the output list is fed to an order-agnostic -- function, you don't have to pay the cost of reversing the representation. -- -- See 'toList' for when order matters.-reverseOut :: RList a -> [a]+reverseOut :: Tsil a -> [a] {-# INLINE reverseOut #-}-reverseOut = unRList+reverseOut = unTsil  --- | @O(0)@ Reverse a plain cons list, rerutning an `RList`.+-- | @O(0)@ Reverse a plain cons list, rerutning an `Tsil`. -- -- See `reverseOut` for the inverse, and why you might use these.-reverseIn :: [a] -> RList a+reverseIn :: [a] -> Tsil a {-# INLINE reverseIn #-}-reverseIn = RList+reverseIn = Tsil --- | Write the contents of the `RList` into an array, assuming you know the length of the array.+-- | Write the contents of the `Tsil` into an array, assuming you know the length of the array. -- This is useful in the common case of buffering an unknown-length stream before allocating contiguous space for the elements. -- -- If you sepcify to small a langth, the initial part of the array will be uninitialized. -- If you specify to large a length, the initial part of the list will not be written. -- -- If you are unaware of the size of the list, `Arr.fromList . fromList` will do the trick, but will obviously be slower.-toArrayN :: (Contiguous arr, Element arr a) => Int -> RList a -> arr a+toArrayN :: (Contiguous arr, Element arr a) => Int -> Tsil a -> arr a {-# INLINE toArrayN #-} -- use inline instead of inlinable, because inlinable with Contiguous is busted-{-# SPECIALIZE toArrayN :: Int -> RList a -> SmallArray a #-}-toArrayN n (RList xs0) = Arr.create $ do+{-# SPECIALIZE toArrayN :: Int -> Tsil a -> SmallArray a #-}+toArrayN n (Tsil xs0) = Arr.create $ do   mut <- Arr.new n   loop mut (n - 1) xs0   pure mut@@ -198,6 +206,6 @@     loop arr (i - 1) xs  -- | Convert to a set without an intermediate conversion to a cons-list.-toSet :: (Ord a) => RList a -> Set a+toSet :: (Ord a) => Tsil a -> Set a {-# INLINABLE toSet #-}-toSet (RList xs) = Set.fromList xs+toSet (Tsil xs) = Set.fromList xs