list-extras 0.1.1 → 0.2.0
raw patch · 5 files changed
+202/−179 lines, 5 files
Files
- Data/List/Extras.hs +3/−3
- Data/List/Extras/ArgMax.hs +0/−159
- Data/List/Extras/Argmax.hs +191/−0
- Data/List/Extras/LazyLength.hs +5/−14
- list-extras.cabal +3/−3
Data/List/Extras.hs view
@@ -2,7 +2,7 @@ {-# OPTIONS_GHC -Wall -Werror #-} ------------------------------------------------------------------- ~ 2008.07.20+-- ~ 2008.07.25 -- | -- Module : Data.List.Extras -- Copyright : Copyright (c) 2007--2008 wren ng thornton@@ -17,11 +17,11 @@ module Data.List.Extras ( module Data.List.Extras.LazyLength , module Data.List.Extras.Pair- , module Data.List.Extras.ArgMax+ , module Data.List.Extras.Argmax ) where import Data.List.Extras.LazyLength import Data.List.Extras.Pair-import Data.List.Extras.ArgMax+import Data.List.Extras.Argmax ---------------------------------------------------------------- ----------------------------------------------------------- fin.
− Data/List/Extras/ArgMax.hs
@@ -1,159 +0,0 @@--{-# OPTIONS_GHC -Wall -Werror -fno-warn-unused-binds #-}--------------------------------------------------------------------- ~ 2008.07.20--- |--- Module : Data.List.Extras.ArgMax--- Copyright : Copyright (c) 2007--2008 wren ng thornton--- License : BSD3--- Maintainer : wren@community.haskell.org--- Stability : experimental--- Portability : portable------ This module provides variants of the 'maximum' and 'minimum'--- functions which return the element for which some function is--- maximized or minimized.-------------------------------------------------------------------module Data.List.Extras.ArgMax- (- -- * Maximum variations- argmax, argmax'- - -- * Minimum variations- , argmin, argmin'- - -- * Generic versions- , argmaxBy, argmaxBy'- - {- TODO: CPS and monadic variants; argmax2, argmax3,... -}- {- TODO: make argmax et al "good consumers" for fusion -}- ) where--- argmaxM :: (Monad m, Ord b) => (a -> m b) -> [a] -> m (Maybe a)---------------------------------------------------------------------------------------------------------------------------------------- CPS version... why bother making the list first?-type CPSList a b = ((a -> b -> b) -> b -> b)---- BUG: This doesn't tail recurse and so it will stack overflow!!!-argmaxCPS :: (Ord b) => (a -> b) -> CPSList a (Maybe (a,b)) -> Maybe a-argmaxCPS f list = list k Nothing >>= Just . fst- where- k x Nothing = Just (x, f x)- k x (Just yfy) = Just (mx x yfy)- - mx a (b,fb) = let fa = f a in- if fa > fb- then (a,fa)- else (b,fb)--------------------------------------------------------------------------------------------------------------------------------------- Compared against a generic decorate-fold-undecorate implementation:--- fst . foldr1 (\a b -> if snd a > snd b then a else b)--- . map (\x -> (x, f x))--- that seems to take 50% to 100% more space vs argmax'. Using--- pattern matching instead of snd seems to improve it, but my tests--- are a bit unclear.--emptyListError :: String -> a-emptyListError fun = error $ "Data.List.Extras.ArgMax."++fun++": empty list"----- | Tail-recursive driver-_argmaxBy :: (b -> b -> Bool) -> (a -> b) -> [a] -> (a,b) -> a-_argmaxBy isBetterThan f = go- where- go [] (b,_) = b- go (x:xs) (b,fb) = go xs $! cmp x (b,fb)- - cmp a (b,fb) = let fa = f a in- if fa `isBetterThan` fb- then (a,fa)- else (b,fb)----- | Direct version of 'argmaxBy' which doesn't catch the empty--- list error.-argmaxBy' :: (b -> b -> Ordering) -> (a -> b) -> [a] -> a-argmaxBy' _ _ [] = emptyListError "argmaxBy'"-argmaxBy' ord f (x:xs) = _argmaxBy boolOrd f xs (x, f x)- where- boolOrd a b = GT == ord a b----- | Returns the element of the list which maximizes a function--- according to a user-defined ordering, or @Nothing@ if the list--- was empty.-argmaxBy :: (b -> b -> Ordering) -> (a -> b) -> [a] -> Maybe a-argmaxBy _ _ [] = Nothing-argmaxBy ord f xs@(_:_) = Just (argmaxBy' ord f xs)---------------------------------------------------------------------- The specialization pragma add about 21kB to the library size--- (compared to 29kB base for list-extras). For a basic utility--- library that's a bit excessive, though if we break the argmax--- stuff out from list-extras then we might go through with it for--- performance sake.---- | Direct version of 'argmax' which doesn't catch the empty list--- error.-{--{-# SPECIALIZE argmax' :: (a -> Int) -> [a] -> a #-}-{-# SPECIALIZE argmax' :: (a -> Integer) -> [a] -> a #-}-{-# SPECIALIZE argmax' :: (a -> Float) -> [a] -> a #-}-{-# SPECIALIZE argmax' :: (a -> Double) -> [a] -> a #-}--}-argmax' :: (Ord b) => (a -> b) -> [a] -> a-argmax' _ [] = emptyListError "argmax'"-argmax' f (x:xs) = _argmaxBy (>) f xs (x, f x)----- | Returns the element of the list which maximizes the function,--- or @Nothing@ if the list was empty.-{--{-# SPECIALIZE argmax :: (a -> Int) -> [a] -> Maybe a #-}-{-# SPECIALIZE argmax :: (a -> Integer) -> [a] -> Maybe a #-}-{-# SPECIALIZE argmax :: (a -> Float) -> [a] -> Maybe a #-}-{-# SPECIALIZE argmax :: (a -> Double) -> [a] -> Maybe a #-}--}-argmax :: (Ord b) => (a -> b) -> [a] -> Maybe a-argmax _ [] = Nothing-argmax f xs@(_:_) = Just (argmax' f xs)----------------------------------------------------------------------- | Direct version of 'argmin' which doesn't catch the empty list--- error.-{--{-# SPECIALIZE argmin' :: (a -> Int) -> [a] -> a #-}-{-# SPECIALIZE argmin' :: (a -> Integer) -> [a] -> a #-}-{-# SPECIALIZE argmin' :: (a -> Float) -> [a] -> a #-}-{-# SPECIALIZE argmin' :: (a -> Double) -> [a] -> a #-}--}-argmin' :: (Ord b) => (a -> b) -> [a] -> a-argmin' _ [] = emptyListError "argmin'"-argmin' f (x:xs) = _argmaxBy (<) f xs (x, f x)----- | Returns the element of the list which minimizes the function,--- or @Nothing@ if the list was empty.-{--{-# SPECIALIZE argmin :: (a -> Int) -> [a] -> Maybe a #-}-{-# SPECIALIZE argmin :: (a -> Integer) -> [a] -> Maybe a #-}-{-# SPECIALIZE argmin :: (a -> Float) -> [a] -> Maybe a #-}-{-# SPECIALIZE argmin :: (a -> Double) -> [a] -> Maybe a #-}--}-argmin :: (Ord b) => (a -> b) -> [a] -> Maybe a-argmin _ [] = Nothing-argmin f xs@(_:_) = Just (argmin' f xs)------------------------------------------------------------------------------------------------------------------------------ fin.
+ Data/List/Extras/Argmax.hs view
@@ -0,0 +1,191 @@++{-# OPTIONS_GHC -Wall -Werror #-}++----------------------------------------------------------------+-- ~ 2008.07.25+-- |+-- Module : Data.List.Extras.ArgMax+-- Copyright : Copyright (c) 2007--2008 wren ng thornton+-- License : BSD3+-- Maintainer : wren@community.haskell.org+-- Stability : experimental+-- Portability : portable+--+-- This module provides variants of the 'maximum' and 'minimum'+-- functions which return the elements for which some function is+-- maximized or minimized.+----------------------------------------------------------------++module Data.List.Extras.Argmax+ (+ -- * Utility functions+ catchNull+ + -- * Generic versions+ , argmaxBy, argmaxesBy, argmaxWithMaxBy, argmaxesWithMaxBy+ + -- * Maximum variations+ , argmax, argmaxes, argmaxWithMax, argmaxesWithMax+ + -- * Minimum variations+ , argmin, argmins, argminWithMin, argminsWithMin+ + {- TODO: CPS and monadic variants; argmax2, argmax3,... -}+ {- TODO: make sure argmax et al are "good consumers" for fusion -}+ ) where+-- argmaxM :: (Monad m, Ord b) => (a -> m b) -> [a] -> m (Maybe a)++import Data.List (foldl')++----------------------------------------------------------------+----------------------------------------------------------------++-- | Apply a list function safely, i.e. when the list is non-empty.+-- All other functions will throw errors on empty lists, so use+-- this to make your own safe variations.+catchNull :: ([a] -> b) -> ([a] -> Maybe b)+catchNull _ [] = Nothing+catchNull f xs@(_:_) = Just (f xs)+++-- | Minimize the number of string literals+{-# NOINLINE emptyListError #-}+emptyListError :: String -> a+emptyListError fun = error $ "Data.List.Extras.ArgMax."++fun++": empty list"+++-- | Apply a list function unsafely. For internal use.+{-# INLINE throwNull #-}+throwNull :: String -> (a -> [a] -> b) -> ([a] -> b)+throwNull fun _ [] = emptyListError fun+throwNull _ f (x:xs) = f x xs++----------------------------------------------------------------+----------------------------------------------------------------+-- | Tail-recursive driver+_argmaxWithMaxBy :: (b -> b -> Bool) -> (a -> b)+ -> a -> [a] -> (a,b)+_argmaxWithMaxBy isBetterThan f x xs = foldl' cmp (x, f x) xs+ where+ cmp bfb@(_,fb) a =+ let fa = f a in+ if fa `isBetterThan` fb+ then (a,fa)+ else bfb+++-- | Tail-recursive driver for all-variants+_argmaxesWithMaxBy :: (b -> b -> Ordering) -> (a -> b)+ -> a -> [a] -> ([a],b)+_argmaxesWithMaxBy isBetterEqualThan f x xs = foldl' cmp ([x], f x) xs+ where+ cmp bsfb@(bs,fb) a =+ let fa = f a in+ case isBetterEqualThan fa fb of+ GT -> ([a], fa)+ EQ -> (a:bs, fb)+ _ -> bsfb++_argmaxBy :: (b -> b -> Bool) -> (a -> b)+ -> a -> [a] -> a+_argmaxBy k f x xs = fst (_argmaxWithMaxBy k f x xs)+++_argmaxesBy :: (b -> b -> Ordering) -> (a -> b)+ -> a -> [a] -> [a]+_argmaxesBy k f x xs = fst (_argmaxesWithMaxBy k f x xs)++----------------------------------------------------------------+----------------------------------------------------------------++bool :: (a -> a -> Ordering) -> (a -> a -> Bool)+bool ord = \a b -> ord a b == GT+++-- | Return an element of the list which maximizes the function+-- according to a user-defined ordering.+argmaxBy :: (b -> b -> Ordering) -> (a -> b) -> [a] -> a+argmaxBy ord f = throwNull "argmaxBy"+ $ _argmaxBy (bool ord) f+++-- | Return all elements of the list which maximize the function+-- according to a user-defined ordering.+argmaxesBy :: (b -> b -> Ordering) -> (a -> b) -> [a] -> [a]+argmaxesBy ord f = throwNull "argmaxesBy"+ $ _argmaxesBy ord f+++-- | Return an element of the list which maximizes the function+-- according to a user-defined ordering, and return the value of+-- the function at that element as well.+argmaxWithMaxBy :: (b -> b -> Ordering) -> (a -> b) -> [a] -> (a, b)+argmaxWithMaxBy ord f = throwNull "argmaxWithMaxBy" + $ _argmaxWithMaxBy (bool ord) f+++-- | Return all elements of the list which maximize the function+-- according to a user-defined ordering, and return the value of+-- the function at those elements as well.+argmaxesWithMaxBy :: (b -> b -> Ordering) -> (a -> b) -> [a] -> ([a], b)+argmaxesWithMaxBy ord f = throwNull "argmaxesWithMaxBy"+ $ _argmaxesWithMaxBy ord f++----------------------------------------------------------------+-- SPECIALIZE on b \in {Int,Integer,Float,Double} for the four+-- functions below nearly doubles the library size (about +21kB).+-- For a basic utility library that's a bit excessive, though if+-- we break the argmax stuff out from list-extras then we might go+-- through with it for performance sake.++-- | Return an element of the list which maximizes the function.+argmax :: (Ord b) => (a -> b) -> [a] -> a+argmax f = throwNull "argmax"+ $ _argmaxBy (>) f++-- | Return all elements of the list which maximize the function.+argmaxes :: (Ord b) => (a -> b) -> [a] -> [a]+argmaxes f = throwNull "argmaxes"+ $ _argmaxesBy compare f+++-- | Return an element of the list which maximizes the function,+-- and return the value of the function at that element as well.+argmaxWithMax :: (Ord b) => (a -> b) -> [a] -> (a, b)+argmaxWithMax f = throwNull "argmaxWithMax" + $ _argmaxWithMaxBy (>) f+++-- | Return all elements of the list which maximize the function,+-- and return the value of the function at those elements as well.+argmaxesWithMax :: (Ord b) => (a -> b) -> [a] -> ([a], b)+argmaxesWithMax f = throwNull "argmaxesWithMax"+ $ _argmaxesWithMaxBy compare f++----------------------------------------------------------------++-- | Return an element of the list which minimizes the function.+argmin :: (Ord b) => (a -> b) -> [a] -> a+argmin f = throwNull "argmax"+ $ _argmaxBy (<) f++-- | Return all elements of the list which minimize the function.+argmins :: (Ord b) => (a -> b) -> [a] -> [a]+argmins f = throwNull "argmins"+ $ _argmaxesBy (flip compare) f+++-- | Return an element of the list which minimizes the function,+-- and return the value of the function at that element as well.+argminWithMin :: (Ord b) => (a -> b) -> [a] -> (a, b)+argminWithMin f = throwNull "argminWithMin"+ $ _argmaxWithMaxBy (<) f++-- | Return all elements of the list which minimize the function,+-- and return the value of the function at those elements as well.+argminsWithMin :: (Ord b) => (a -> b) -> [a] -> ([a], b)+argminsWithMin f = throwNull "argminsWithMin"+ $ _argmaxesWithMaxBy (flip compare) f++----------------------------------------------------------------+----------------------------------------------------------- fin.
Data/List/Extras/LazyLength.hs view
@@ -2,7 +2,7 @@ {-# OPTIONS_GHC -Wall -Werror #-} ------------------------------------------------------------------- ~ 2008.07.20+-- ~ 2008.07.25 -- | -- Module : Data.List.Extras.LazyLength -- Copyright : Copyright (c) 2007--2008 wren ng thornton@@ -33,13 +33,12 @@ -- functions with the same lazy effect as if we used Peano integers, -- but does so efficiently instead. ----- (For Peano integers see {numbers}"Data.Number.Natural" or--- {non-negative}"Numeric.NonNegative.Class".)+-- (For Peano integers see numbers:"Data.Number.Natural" or+-- non-negative:"Numeric.NonNegative.Class".) ---------------------------------------------------------------- module Data.List.Extras.LazyLength- ( lengthBound, negateOrdering- , lengthCompare+ ( lengthBound, lengthCompare ) where @@ -68,14 +67,6 @@ go 0 (_:_) = cmp 0 1 go n' (_:xs') = (go $! n'-1) xs' ---- | Flips 'LT' and 'GT'. Used by 'lengthBound' in rewrite rules.-negateOrdering :: Ordering -> Ordering-negateOrdering LT = GT-negateOrdering EQ = EQ-negateOrdering GT = LT-- {-# RULES "lengthBound/(>)" forall n xs. n > length xs = lengthBound n (>) xs@@ -94,7 +85,7 @@ "lengthBound\\(<=)" forall n xs. length xs <= n = lengthBound n (>=) xs "lengthBound\\(<)" forall n xs. length xs < n = lengthBound n (>) xs "lengthBound\\compare" forall n xs.- compare (length xs) n = negateOrdering (lengthBound n compare xs)+ compare (length xs) n = lengthBound n (flip compare) xs #-}
list-extras.cabal view
@@ -1,9 +1,9 @@ ------------------------------------------------------------------- wren ng thornton <wren@cpan.org> ~ 2008.07.23+-- wren ng thornton <wren@cpan.org> ~ 2008.07.25 ---------------------------------------------------------------- Name: list-extras-Version: 0.1.1+Version: 0.2.0 Cabal-Version: >= 1.2 Build-Type: Simple Stability: stable@@ -29,7 +29,7 @@ Library Exposed-Modules: Prelude.Listless , Data.List.Extras- , Data.List.Extras.ArgMax+ , Data.List.Extras.Argmax , Data.List.Extras.LazyLength , Data.List.Extras.Pair Build-Depends: base