subG 0.1.1.1 → 0.2.0.0

raw patch · 4 files changed

+232/−10 lines, 4 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• CHANGELOG.md +7/−2
• Data/MinMax.hs +95/−0
• Data/SubG.hs +127/−5
• subG.cabal +3/−3

@@ -6,8 +6,13 @@  ## 0.1.1.0 -- 2020-10-16 -* First version revised A. Discontinued the support for the GHC-7.8.* series. +* First version revised A. Discontinued the support for the GHC-7.8.* series.  ## 0.1.1.1 -- 2020-10-16 -* First version revised B. Some documentation improvements. +* First version revised B. Some documentation improvements.++## 0.2.0.0 -- 2020-11-17++* Second version. Added new functions to the Data.SubG module. Added a new module Data.MinMax with the functions that allow to find out both minimum and+maximum elements of the Foldable structures.

@@ -0,0 +1,95 @@+-- |+-- Module      :  Data.MinMax+-- Copyright   :  (c) OleksandrZhabenko 2020+-- License     :  MIT+-- Stability   :  Experimental+-- Maintainer  :  olexandr543@yahoo.com+--+-- Functions to find both minimum and maximum elements of the 'F.Foldable' structure of the 'Ord'ered elements.++module Data.MinMax where++import Prelude hiding (drop,take,splitAt)+import Data.Maybe (fromJust)+import Data.SubG+import qualified Data.Foldable as F++-- | Returns a pair where the first element is the minimum element from the two given ones and the second one is the maximum. If the arguments are+-- equal then the tuple contains equal elements.+minmaxP :: (Ord a) => a -> a -> (a,a)+minmaxP x y+ | x < y = (x,y)+ | otherwise = (y,x)++-- | A ternary predicate to check whether the third argument lies between the first two unequal ones or whether they are all equal.+betweenNX :: (Ord a) => a -> a -> a -> Bool+betweenNX x y z+ | x == y = x == z+ | z < k && z > t = True+ | otherwise = False+      where (t,k) = minmaxP x y++-- | Finds out the minimum and maximum values of the finite structure. If the latter one is empty returns 'Nothing', if all the elements are equal+-- (or it has just one) then it returns 'Just' tuple of equal elements.+minMax :: (Ord a, Foldable t) => t a -> Maybe (a, a)+minMax xs+ | F.null xs = Nothing+ | otherwise = Just . F.foldr f (x,x) $ xs+      where x = fromJust . safeHead $ xs+            f z (x,y)+              | z < x = (z,y)+              | z > y = (x,z)+              | otherwise = (x,y)++-- | A generalized variant of the 'minMax' where you can specify your own comparison function.+minMaxBy :: (Ord a, Foldable t) => (a -> a -> Ordering) -> t a -> Maybe (a, a)+minMaxBy g xs+ | F.null xs = Nothing+ | otherwise = Just . F.foldr f (x,x) $ xs+      where x = fromJust . safeHead $ xs+            f z (x,y)+              | g z x == LT = (z,y)+              | g z y == GT = (x,z)+              | otherwise = (x,y)++-- | Given a finite structure with at least 3 elements returns a tuple with the two most minimum elements+-- (the first one is less than the second one) and the maximum element. If the structure has less elements, returns 'Nothing'.+-- All the elements must be pairwise unequal though this is not checked. Uses just two passes through the structure, so may be more efficient than+-- some other approaches.+minMax21 :: (Ord a, Foldable t) => t a -> Maybe ((a,a), a)+minMax21 xs+ | F.length xs < 3 = Nothing+ | otherwise = Just . F.foldr f ((x,x),x) $ xs+      where x = fromJust . safeHead $ xs+            f z ((x,y),t)+              | z > t = ((x,y),z)+              | z < y = if z > x then ((x,z),t) else ((z,x),t)+              | otherwise = ((x,y),t)++-- | Given a finite structure with at least 3 elements returns a tuple with the minimum element+-- and two maximum elements (the first one is less than the second one). If the structure has less elements, returns 'Nothing'.+-- All the elements must be pairwise unequal though this is not checked. Uses just two passes through the structure, so may be more efficient than+-- some other approaches.+minMax12 :: (Ord a, Foldable t) => t a -> Maybe (a, (a,a))+minMax12 xs+ | F.length xs < 3 = Nothing+ | otherwise = Just . F.foldr f (x,(x,x)) $ xs+      where x = fromJust . safeHead $ xs+            f z (x,(y,t))+              | z < x = (z,(y,t))+              | z > y = if z < t then (x,(z,t)) else (x,(t,z))+              | otherwise = (x,(y,t))++-- | Given a finite structure with at least 4 elements returns a tuple with two minimum elements+-- and two maximum elements. If the structure has less elements, returns 'Nothing'.+-- All the elements must be pairwise unequal though this is not checked. Uses just two passes through the structure, so may be more efficient than+-- some other approaches.+minMax22 :: (Ord a, Foldable t) => t a -> Maybe ((a,a), (a,a))+minMax22 xs+ | F.length xs < 4 = Nothing+ | otherwise = Just . F.foldr f ((x,x),(x,x)) $ xs+      where x = fromJust . safeHead $ xs+            f z ((x,y),(t,w))+              | z < y = if z > x then ((x,z),(t,w)) else ((z,x),(t,w))+              | z > t = if z < w then ((x,y),(z,w)) else ((x,y),(w,z))+              | otherwise = ((x,y),(t,w))

@@ -13,19 +13,31 @@ module Data.SubG (   InsertLeft(..)   , subG-  , dropWhile+  , take+  , takeFromEnd+  , reverseTake+  , reverseTakeFromEnd+  , drop+  , dropFromEnd+  , reverseDrop+  , reverseDropFromEnd   , takeWhile+  , dropWhile   , span   , preAppend+  , safeHead+  , safeTail+  , safeInit+  , safeLast ) where -import Prelude hiding (dropWhile, span, takeWhile)+import Prelude hiding (dropWhile, span, takeWhile,drop,take,splitAt) import qualified Data.Foldable as F import Data.Monoid -infixr 1 %@, %^  +infixr 1 %@, %^ --- | Some extension to the 'F.Foldable' and 'Monoid' classes.  +-- | Some extension to the 'F.Foldable' and 'Monoid' classes. class (F.Foldable t, Eq a, Eq (t a)) => InsertLeft t a where   (%@) :: a -> t a -> t a  -- infixr 1   (%^) :: t a -> t (t a) -> t (t a)@@ -52,7 +64,7 @@  -- | Inspired by: Graham Hutton. A tutorial on the universality and expressiveness of fold. /J. Functional Programming/ 9 (4): 355–372, July 1999. -- that is available at the URL: https://www.cs.nott.ac.uk/~pszgmh/fold.pdf.-dropWhile :: (InsertLeft t a, Monoid (t a)) => (a -> Bool) -> t a -> t a        +dropWhile :: (InsertLeft t a, Monoid (t a)) => (a -> Bool) -> t a -> t a dropWhile p = fst . dropWhile' p  -- | Inspired by: Graham Hutton. A tutorial on the universality and expressiveness of fold. /J. Functional Programming/ 9 (4): 355–372, July 1999.@@ -84,3 +96,113 @@ preAppend ts uss tss = mconcat [ts %^ tss, uss] {-# INLINE preAppend #-} +-------------------------------------------------------------------------------------++-- | Inspired by: Graham Hutton. A tutorial on the universality and expressiveness of fold. /J. Functional Programming/ 9 (4): 355–372, July 1999.+-- that is available at the URL: https://www.cs.nott.ac.uk/~pszgmh/fold.pdf.+-- Takes the first argument quantity from the right end of the structure preserving the order.+takeFromEnd :: (Integral b, InsertLeft t a, Monoid (t a)) => b -> t a -> t a+takeFromEnd n = (\(xs,_,_) -> xs) . F.foldr f v+ where v = (mempty,0,n)+       f x (zs,k,n)+        | k < n = (x %@ zs,k + 1,n)+        | otherwise = (zs,k,n)++-- | Inspired by: Graham Hutton. A tutorial on the universality and expressiveness of fold. /J. Functional Programming/ 9 (4): 355–372, July 1999.+-- that is available at the URL: https://www.cs.nott.ac.uk/~pszgmh/fold.pdf.+-- Takes the specified quantity from the right end of the structure and then reverses the result.+reverseTakeFromEnd :: (Integral b, InsertLeft t a, Monoid (t a)) => b -> t a -> t a+reverseTakeFromEnd n = (\(xs,_,_) -> xs) . F.foldr f v+ where v = (mempty,0,n)+       f x (zs,k,n)+        | k < n = (zs `mappend` (x %@ mempty),k + 1,n)+        | otherwise = (zs,k,n)++-- | Inspired by: Graham Hutton. A tutorial on the universality and expressiveness of fold. /J. Functional Programming/ 9 (4): 355–372, July 1999.+-- that is available at the URL: https://www.cs.nott.ac.uk/~pszgmh/fold.pdf.+-- Is analogous to the taking the specified quantity from the structure and then reversing the result. Uses strict variant of the foldl, so is+-- not suitable for large amounts of data.+reverseTake :: (Integral b, InsertLeft t a, Monoid (t a)) => b -> t a -> t a+reverseTake n = (\(xs,_,_) -> xs) . F.foldl' f v+ where v = (mempty,0,n)+       f (zs,k,n) x+        | k < n = (x %@ zs,k + 1,n)+        | otherwise = (zs,k,n)++-- | Inspired by: Graham Hutton. A tutorial on the universality and expressiveness of fold. /J. Functional Programming/ 9 (4): 355–372, July 1999.+-- that is available at the URL: https://www.cs.nott.ac.uk/~pszgmh/fold.pdf. Uses strict variant of the foldl, so is+-- strict and the data must be finite.+take :: (Integral b, InsertLeft t a, Monoid (t a)) => b -> t a -> t a+take n = (\(xs,_,_) -> xs) . F.foldl' f v+ where v = (mempty,0,n)+       f (zs,k,n) x+        | k < n = (zs `mappend` (x %@ mempty),k + 1,n)+        | otherwise = (zs,k,n)++-- | Inspired by: Graham Hutton. A tutorial on the universality and expressiveness of fold. /J. Functional Programming/ 9 (4): 355–372, July 1999.+-- that is available at the URL: https://www.cs.nott.ac.uk/~pszgmh/fold.pdf.+-- Is analogous to the dropping the specified quantity from the structure and then reversing the result. Uses strict variant of the foldl, so is+-- strict and the data must be finite.+reverseDrop :: (Integral b, InsertLeft t a, Monoid (t a)) => b -> t a -> t a+reverseDrop n = (\(xs,_,_) -> xs) . F.foldl' f v+ where v = (mempty,0,n)+       f (zs,k,n) x+        | k < n = (mempty,k + 1,n)+        | otherwise = (x %@ zs,k,n)++-- | Inspired by: Graham Hutton. A tutorial on the universality and expressiveness of fold. /J. Functional Programming/ 9 (4): 355–372, July 1999.+-- that is available at the URL: https://www.cs.nott.ac.uk/~pszgmh/fold.pdf.+-- Drops the first argument quantity from the right end of the structure and returns the result preserving the order.+dropFromEnd :: (Integral b, InsertLeft t a, Monoid (t a)) => b -> t a -> t a+dropFromEnd n = (\(xs,_,_) -> xs) . F.foldr f v+ where v = (mempty,0,n)+       f x (zs,k,n)+        | k < n = (mempty,k + 1,n)+        | otherwise = (x %@ zs,k,n)++-- | Inspired by: Graham Hutton. A tutorial on the universality and expressiveness of fold. /J. Functional Programming/ 9 (4): 355–372, July 1999.+-- that is available at the URL: https://www.cs.nott.ac.uk/~pszgmh/fold.pdf.+-- Drops the specified quantity from the right end of the structure and then reverses the result.+reverseDropFromEnd :: (Integral b, InsertLeft t a, Monoid (t a)) => b -> t a -> t a+reverseDropFromEnd n = (\(xs,_,_) -> xs) . F.foldr f v+ where v = (mempty,0,n)+       f x (zs,k,n)+        | k < n = (mempty,k + 1,n)+        | otherwise = (zs `mappend` (x %@ mempty),k,n)++-- | Inspired by: Graham Hutton. A tutorial on the universality and expressiveness of fold. /J. Functional Programming/ 9 (4): 355–372, July 1999.+-- that is available at the URL: https://www.cs.nott.ac.uk/~pszgmh/fold.pdf. Uses strict variant of the foldl, so is+-- strict and the data must be finite.+drop :: (Integral b, InsertLeft t a, Monoid (t a)) => b -> t a -> t a+drop n = (\(xs,_,_) -> xs) . F.foldl' f v+ where v = (mempty,0,n)+       f (zs,k,n) x+        | k < n = (mempty,k + 1,n)+        | otherwise = (zs `mappend` (x %@ mempty),k,n)++-- | Inspired by: Graham Hutton. A tutorial on the universality and expressiveness of fold. /J. Functional Programming/ 9 (4): 355–372, July 1999.+-- that is available at the URL: https://www.cs.nott.ac.uk/~pszgmh/fold.pdf. Uses strict variant of the foldl, so is+-- strict and the data must be finite.+splitAt :: (Integral b, InsertLeft t a, Monoid (t a)) => b -> t a -> (t a, t a)+splitAt n = (\(x,y,_,_) -> (x,y)) . F.foldl' f v+ where v = (mempty,mempty,0,n)+       f (zs,ts,k,n) x+        | k < n = (zs `mappend` (x %@ mempty),mempty,k + 1,n)+        | otherwise = (zs,ts `mappend` (x %@ mempty),k + 1,n)++-- | If a structure is empty, just returns 'Nothing'.+safeHead :: (Foldable t) => t a -> Maybe a+safeHead = F.find (const True)++-- | If the structure is empty, just returns itself. Uses strict variant of the foldl, so is+-- strict and the data must be finite.+safeTail :: (InsertLeft t a, Monoid (t a)) => t a -> t a+safeTail = drop 1++-- | If the structure is empty, just returns itself.+safeInit :: (InsertLeft t a, Monoid (t a)) => t a -> t a+safeInit = dropFromEnd 1++-- | If the structure is empty, just returns 'Nothing'.+safeLast :: (InsertLeft t a, Monoid (t a)) => t a -> Maybe a+safeLast = F.find (const True) . takeFromEnd 1

@@ -2,9 +2,9 @@ -- see http://haskell.org/cabal/users-guide/  name:                subG-version:             0.1.1.1+version:             0.2.0.0 synopsis:            Some extension to the Foldable and Monoid classes.-description:         Introduces a new class InsertLeft -- the class of types of values that can be inserted from the left to the Foldable structure that is a data that is also the Monoid instance.+description:         Introduces a new class InsertLeft -- the class of types of values that can be inserted from the left to the Foldable structure that is a data that is also the Monoid instance. Also contains some functions to find out both minimum and maximum elements of the finite Foldable structures. homepage:            https://hackage.haskell.org/package/subG license:             MIT license-file:        LICENSE@@ -17,7 +17,7 @@ cabal-version:       >=1.10  library-  exposed-modules:     Data.SubG+  exposed-modules:     Data.SubG, Data.MinMax   -- other-modules:   other-extensions:    MultiParamTypeClasses, FlexibleInstances   build-depends:       base >=4.8 && <4.15