sorted-list (empty) → 0.1.0.0

raw patch · 4 files changed

+218/−0 lines, 4 filesdep +basesetup-changed

Dependencies added: base

Files

• Data/SortedList.hs +162/−0
• LICENSE +30/−0
• Setup.hs +2/−0
• sorted-list.cabal +24/−0

@@ -0,0 +1,162 @@++-- | This module defines a type for sorted lists, together+--   with several functions to create and use values of that+--   type. Many operations are optimized to take advantage+--   of the list being sorted.+module Data.SortedList (+    -- * Type+    SortedList+    -- * List conversions+  , toSortedList+  , fromSortedList+    -- * Construction+  , singleton+  , repeat+  , replicate+  , iterate+    -- * Deconstruction+  , uncons+    -- * Inserting+  , insert+    -- * Sublists+  , take+  , drop+  , splitAt+  , filter+    -- * Queries+  , elemOrd+    -- * Others+  , nub+  ) where++import Prelude hiding+  ( take, drop, splitAt, filter+  , repeat, replicate, iterate+    )+import qualified Data.List as List+import Data.Monoid ((<>))+import Data.Foldable (toList)++-- | Type of sorted lists. Any (non-bottom) value of this type+--   is a sorted list.+newtype SortedList a = SortedList [a]++instance Show a => Show (SortedList a) where+  show = show . fromSortedList++-- | Decompose a sorted list into its minimal element and the rest.+--   If the list is empty, it returns 'Nothing'.+uncons :: SortedList a -> Maybe (a, SortedList a)+uncons (SortedList []) = Nothing+uncons (SortedList (x:xs)) = Just (x, SortedList xs)++-- | Create a 'SortedList' by sorting a regular list.+toSortedList :: Ord a => [a] -> SortedList a+toSortedList = SortedList . List.sort++-- | Create a list from a 'SortedList'. The returned list+--   is guaranteed to be sorted.+fromSortedList :: SortedList a -> [a]+fromSortedList (SortedList xs) = xs++mergeSortedLists :: Ord a => [a] -> [a] -> [a]+mergeSortedLists xs [] = xs+mergeSortedLists [] ys = ys+mergeSortedLists (x:xs) (y:ys) =+  if x <= y+     then x : mergeSortedLists xs (y:ys)+     else y : mergeSortedLists (x:xs) ys++instance Ord a => Monoid (SortedList a) where+  mempty = SortedList []+  mappend (SortedList xs) (SortedList ys) = SortedList $ mergeSortedLists xs ys++-- | /O(1)/. Create a sorted list with only one element.+singleton :: a -> SortedList a+singleton x = SortedList [x]++-- | An infinite list with all its elements equal to the given+--   argument.+repeat :: a -> SortedList a+repeat = SortedList . List.repeat++-- | Replicate a given number of times a single element.+replicate :: Int -> a -> SortedList a+replicate n = SortedList . List.replicate n++-- | Create a sorted list by repeatedly applying the same+--   function to an element, until the image by that function+--   is stricly less than its argument. In other words:+--+-- > iterate f x = [x, f x, f (f x), ... ]+--+--   With the list ending whenever+--   @f (f (... (f (f x)) ...)) < f (... (f (f x)) ...)@.+--   If this never happens, the list will be infinite.+iterate :: Ord a => (a -> a) -> a -> SortedList a+iterate f x = SortedList $ x : go x (f x)+  where+    go prev fprev =+      if prev <= fprev+         then fprev : go fprev (f fprev)+         else []++-- | /O(n)/. Insert a new element in a sorted list.+insert :: Ord a => a -> SortedList a -> SortedList a+insert x xs = singleton x <> xs++-- | Extract the prefix with the given length from a sorted list.+take :: Int -> SortedList a -> SortedList a+take n = fst . splitAt n++-- | Drop the given number of elements from a sorted list, starting+--   from the smallest and following ascending order.+drop :: Int -> SortedList a -> SortedList a+drop n = snd . splitAt n++-- | Split a sorted list in two sublists, with the first one having+--   length equal to the given argument, except when the length of the+--   list is less than that.+splitAt :: Int -> SortedList a -> (SortedList a, SortedList a)+splitAt n (SortedList xs) =+  let (ys,zs) = List.splitAt n xs+  in  (SortedList ys, SortedList zs)++-- | /O(n)/. Extract the elements of a list that satisfy the predicate.+filter :: (a -> Bool) -> SortedList a -> SortedList a+filter f (SortedList xs) = SortedList $ List.filter f xs++-- | /O(n)/. An efficient implementation of 'elem', using the 'Ord'+--   instance of the elements in a sorted list. It only traverses+--   the whole list if the requested element is greater than all+--   the elements in the sorted list.+elemOrd :: Ord a => a -> SortedList a -> Bool+elemOrd a (SortedList l) = go l+    where+      go (x:xs) =+        case compare a x of+          GT -> go xs+          EQ -> True+          _  -> False+      go _ = False++-- | /O(n)/. Remove duplicate elements from a sorted list.+nub :: Eq a => SortedList a -> SortedList a+nub (SortedList l) = SortedList $ go l+  where+    go (x:y:xs) = if x == y then go (x:xs) else x : go (y:xs)+    go xs = xs++instance Foldable SortedList where+  {-# INLINE foldr #-}+  foldr f e (SortedList xs) = foldr f e xs+  {-# INLINE toList #-}+  toList = fromSortedList+  minimum (SortedList xs) =+    case xs of+      x : _ -> x+      _ -> error "SortedList.minimum: empty list"+  maximum (SortedList xs) =+    case xs of+      [] -> error "SortedList.maximum: empty list"+      _ -> last xs

@@ -0,0 +1,30 @@+Copyright (c) 2015, Daniel Díaz++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 Daniel Díaz 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.

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

@@ -0,0 +1,24 @@+name:                sorted-list+version:             0.1.0.0+synopsis:            Type-enforced sorted lists and related functions.+description:         Type-enforced sorted lists and related functions.+                     .+                     Feel free to try this library, but take in account+                     that it's still in development, so it might lack+                     some features. If you need them, do not hesitate+                     to ask by opening an issue at the bug-tracker.+homepage:            https://github.com/Daniel-Diaz/sorted-list/blob/master/README.md+license:             BSD3+license-file:        LICENSE+author:              Daniel Díaz+maintainer:          dhelta.diaz@gmail.com+bug-reports:         https://github.com/Daniel-Diaz/sorted-list/issues+category:            Data+build-type:          Simple+cabal-version:       >=1.10++library+  exposed-modules:     Data.SortedList+  build-depends:       base == 4.*+  default-language:    Haskell2010+  ghc-options:         -Wall