reverse-list (empty) → 0.2.0

raw patch · 6 files changed

+382/−0 lines, 6 filesdep +basedep +containersdep +contiguous

Dependencies added: base, containers, contiguous, deepseq

Files

CHANGELOG.md +14/−0
LICENSE +30/−0
README.md +26/−0
reverse-list.cabal +31/−0
src/Data/List/Cons.hs +78/−0
src/Data/List/Snoc.hs +203/−0

+ CHANGELOG.md view

@@ -0,0 +1,14 @@+# Revision history for reverse-list++## 0.2.0 -- 2022-01-27++* Remove `Foldable` instance until I determine the correct semantics.+* Add `init`, `last`.+* Add `Data.List.Cons` module and `Tsil` synonym for "symmetry".+* Rename `Data.List.RList` to `Data.List.Snoc`+* `RList.{safeLast,safeInit}`+* `RList.toSet`++## 0.1.0 -- 2021-12-27++* First version. Released on an unsuspecting world.

+ LICENSE view

@@ -0,0 +1,30 @@+Copyright Okuno Zankoku (c) 2021++All rights reserved.++Redistribution and use in source and binary forms, with or without+modification, are permitted provided that the following conditions are met:++    * Redistributions of source code must retain the above copyright+      notice, this list of conditions and the following disclaimer.++    * Redistributions in binary form must reproduce the above+      copyright notice, this list of conditions and the following+      disclaimer in the documentation and/or other materials provided+      with the distribution.++    * Neither the name of Okuno Zankoku nor the names of other+      contributors may be used to endorse or promote products derived+      from this software without specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

+ README.md view

@@ -0,0 +1,26 @@+# 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 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++parseSqlString :: String -> Maybe String+parseSqlString str0 = case str0 of+  '\'':rest -> loop "" rest+  _ -> Nothing+  where+  loop :: RList Char -> [Char] -> Maybe [Char]+  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+```++Currently, we only support the basic introduction/elimination forms (though reasonably ergonomically), and conversions.+Additional functions should certainly be exposed, after due consideration is given to their semantics, including performance.+If you run into anything you think deserved to be exported, open an issue or a pull request and I'll be happy to get it done.

+ reverse-list.cabal view

@@ -0,0 +1,31 @@+cabal-version: 3.0+name: reverse-list+version: 0.2.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.+  It also creates a symmetric module for cons-lists, which focuses on the efficient and safe use of linked lists.+  See README.md for more information.+category: Data+homepage: https://github.com/edemko/reverse-list+bug-reports: https://github.com/edemko/reverse-list/issues+author: Eric Demko+maintainer: zankoku.okuno@gmail.com+copyright: 2021 Eric Demko+license: BSD-3-Clause+license-file: LICENSE+extra-source-files: README.md, CHANGELOG.md++library+  hs-source-dirs: src+  exposed-modules:+    Data.List.Cons+    Data.List.Snoc+  -- other-modules:+  build-depends:+    , base >=4.14.3 && <4.16+    , 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

+ src/Data/List/Cons.hs view

@@ -0,0 +1,78 @@+{-# LANGUAGE PatternSynonyms #-}+{-# LANGUAGE ViewPatterns #-}++-- | This module exists primarily for symmetry with "Data.List.Snoc"+-- 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+-- technically implementable, do not represent the intended use of a linked list+-- in terms of performance.+--+-- Additionally, this module does not export any partial functions: 'head' and+-- 'tail' return their results under a 'Maybe'.+module Data.List.Cons+  ( List+  , pattern Nil+  , pattern Cons+  , nil+  , cons+  , uncons+  , singleton+  , head+  , tail+  ) where++import Prelude hiding (head,tail)++-- | As a counterpart to 'Data.List.Snoc.RList'/'Data.List.Snoc.Tsil'.+type List = ([])++{-# COMPLETE Nil, Cons #-}++-- | An empty 'List', such as 'nil'.+pattern Nil :: List a+pattern Nil = []++-- | The 'List' consisting of head and tail elements, such as created by 'cons'.+pattern Cons :: a -> List a -> List a+pattern Cons x xs <- (uncons -> Just (x, xs))+  where Cons = cons++-- | The empty 'List'.+nil :: List a+{-# INLINABLE nil #-}+nil = []++-- | @O(1)@ Append an element.+--+-- If you are looking for @snoc@, you should use an 'RList', or a finite sequence/queue type.+cons :: a -> List a -> List a+{-# INLINABLE cons #-}+cons = (:)++-- | @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.+uncons :: List a -> Maybe (a, List a)+{-# INLINABLE uncons #-}+uncons [] = Nothing+uncons (x:xs) = Just (x, xs)++-- | @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+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)+tail Nil = Nothing+tail (Cons _ xs) = Just xs++-- | Create a single-element 'List'.+singleton :: a -> List a+{-# INLINE singleton #-}+singleton = (:[])

+ src/Data/List/Snoc.hs view

@@ -0,0 +1,203 @@+{-# LANGUAGE DeriveGeneric #-}+{-# LANGUAGE DerivingStrategies #-}+{-# LANGUAGE GeneralizedNewtypeDeriving #-}+{-# LANGUAGE PatternSynonyms #-}+{-# LANGUAGE ViewPatterns #-}+++-- | Snoc-lists: lists where prepending is linear-time, but _appending_ is constant-time.+-- Useful for describing zippers and functional queues/buffers more naturally and safely.+--+-- 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+  -- * Introduction and Elimination+  , nil+  , snoc+  , singleton+  , unsnoc+  -- ** Patterns+  , pattern Nil+  , pattern Snoc+  -- * Queries+  , null+  , init+  , last+  -- * Traversal+  , catMaybes+  -- * Conversion+  , toList+  , fromList+  , reverseIn+  , reverseOut+  , toArrayN+  , toSet+  ) where++import Prelude hiding (null,init,last,reverse)++import Control.Applicative(Alternative(..))+import Control.DeepSeq (NFData)+import Data.Bifunctor (first)+import Data.Primitive.Contiguous (Contiguous, Element, SmallArray)+import Data.Set (Set)+import GHC.Generics (Generic)++import qualified Data.List as List+import qualified Data.Maybe as Maybe+import qualified Data.Primitive.Contiguous as Arr+import qualified Data.Set as Set+import qualified Prelude++-- | 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)+  deriving newtype (Functor,Applicative)+instance (NFData a) => NFData (RList a)++instance (Show a) => Show (RList a) where+  show = show . toList+instance (Read a) => Read (RList 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+  mempty = Nil++instance Alternative RList where+  empty = mempty+  (RList a) <|> (RList b) = RList (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++{-# COMPLETE Nil, Snoc #-}++-- | An empty 'RList', such as 'nil'.+pattern Nil :: RList a+pattern Nil = RList []++-- | The 'RList' consisting of initial and last elements, such as created by 'snoc'.+pattern Snoc :: RList a -> a -> RList a+pattern Snoc xs x <- (unsnoc -> Just (xs, x))+  where Snoc = snoc++-- | The empty 'RList'.+nil :: RList a+{-# INLINABLE nil #-}+nil = RList []++-- | @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+{-# INLINABLE snoc #-}+snoc (RList xs) x = RList (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)+{-# INLINABLE unsnoc #-}+unsnoc (RList []) = Nothing+unsnoc (RList (x:xs)) = Just (RList xs, x)++-- | Create a single-element 'RList'.+singleton :: a -> RList a+{-# INLINE singleton #-}+singleton = RList . (:[])++-- | Test if an 'RList' is empty.+null :: RList a -> Bool+{-# INLINE null #-}+null (RList 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 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 Nil = Nothing+init (Snoc xs _) = Just xs++-- | Remove all 'Nothing's from an 'RList' of 'Maybe's.+catMaybes :: RList (Maybe a) -> RList a+{-# INLINE catMaybes #-}+catMaybes = RList . Maybe.catMaybes . unRList++-- | @O(n)@ Convert to a plain list, maintaining order.+--+-- This is here so that you can escape back out to normal cons-list land once+-- you're done building your list.+--+-- See 'reverseOut' for when order doesn't matter.+toList :: RList a -> [a]+{-# INLINE toList #-}+toList (RList 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+{-# INLINE fromList #-}+fromList = RList . Prelude.reverse++-- | @O(0)@ Reverse an `RList`, 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]+{-# INLINE reverseOut #-}+reverseOut = unRList+++-- | @O(0)@ Reverse a plain cons list, rerutning an `RList`.+--+-- See `reverseOut` for the inverse, and why you might use these.+reverseIn :: [a] -> RList a+{-# INLINE reverseIn #-}+reverseIn = RList++-- | Write the contents of the `RList` 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+{-# 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+  mut <- Arr.new n+  loop mut (n - 1) xs0+  pure mut+  where+  loop _ (-1) _ = pure ()+  loop _ _ [] = pure ()+  loop arr i (x:xs) = do+    Arr.write arr i x+    loop arr (i - 1) xs++-- | Convert to a set without an intermediate conversion to a cons-list.+toSet :: (Ord a) => RList a -> Set a+{-# INLINABLE toSet #-}+toSet (RList xs) = Set.fromList xs