nptools 0.4.0 → 0.4.1

raw patch · 2 files changed

+46/−1 lines, 2 files

Files

• Data/List/NP.hs +44/−0
• nptools.cabal +2/−1

@@ -0,0 +1,44 @@+module Data.List.NP where++import Data.Array+import Data.List (tails)++interleave :: [a] -> [a] -> [a]+interleave []      ys = ys+interleave (x:xs)  ys = x : interleave ys xs++-- | Given a `choose' function and bound indices, it returns the list of indices+-- following a dichotomic search.+-- The `choose' function, picks an index between to other indices or return+-- Nothing if this is not possible, like when indices are too close each other.+dichoIndices :: (ix -> ix -> Maybe ix) -> (ix, ix) -> [ix]+dichoIndices choose (begin, end) = begin : end : go begin end where+  go b e = case choose b e of+             Nothing  -> []+             Just m   -> m : interleave (go b m) (go m e)++-- | Order the given list by distance with previous elements, starting+-- from the higher distance.+-- It starts with the first element, then the last one, then the middle+-- one...+orderByDensity :: [a] -> [a]+orderByDensity xs = map (arr!) (dichoIndices choose bnds) where+  arr   = listArray bnds xs+  bnds  = (0, length xs - 1)+  choose x y | y - x <= 1  = Nothing+             | otherwise   = Just (x + (y - x) `div` 2)++zipTailWith :: (a -> a -> b) -> [a] -> [b]+zipTailWith _ [] = []+zipTailWith f (x0 : xs0) = go x0 xs0 where+  go _ []     = []+  go x (y:ys) = f x y : go y ys++orderByDensity_spec :: Int -> Bool+orderByDensity_spec n =+  go (orderByDensity input)+  where input          = [0..n] :: [Int] -- thanks to parametricity+        dist x y       = abs (y - x)+        distL []       = error "orderByDensity_spec: impossible"+        distL (x:xs)   = minimum (map (dist x) xs)+        go = and . zipTailWith (<=) . map distL . init . init . tails . reverse

@@ -1,6 +1,6 @@ Name:           nptools Cabal-Version:  >=1.4-Version:        0.4.0+Version:        0.4.1 License:        BSD3 License-File:   LICENSE Copyright:      (c) Nicolas Pouillard@@ -126,4 +126,5 @@ executable color-list     main-is: color-list.hs     Build-depends: base>=3&&<5, colour, array+    Other-Modules: Data.List.NP     ghc-options: -Wall -Odph