Aelve Codesearch

grep over package repositories
Please provide a string to search for.
3+ characters are required.
Index updated 5 hours ago

total matches: 53

TreeStructures-0.0.2
3 matches
Data/Heap/Binary.hs
toList Leaf = []
toList h@(Node _ _ _ _) = head h : toList (tail h)

-- | /O(n)/. 'fromList' constructs a binary heap from an unsorted list.
fromList :: (Ord a) => [a] -> BinaryHeap a
fromList [] = Leaf
fromList l = mergeList (map singleton l)
              where mergeList [a] = a
                    mergeList x = mergeList (mergePairs x)

            
Tests.hs
import qualified Data.Tree.AVL as A
import qualified Data.Tree.Splay as P

binary_fromListToList s = (B.toList . B.fromList) s == sort s
  where _ = s :: [Int]

binomial_fromListToList s = (N.toList . N.fromList) s == sort s
  where _ = s :: [Int]

skew_fromListToList s = (S.toList . S.fromList) s == sort s
  where _ = s :: [Int]

avl_fromListToList s = (map fst . A.toList . A.fromList) s == (map fst . sort) s
  where _ = s :: [(Int,Int)]

splay_fromListToList s = (map fst . P.toList . P.fromList) s == (map fst . sort) s
  where _ = s :: [(Int,Int)]



tests = [

            
Tests.hs


tests = [
    ("Heap.Binary:   toList.fromList/sort", test binary_fromListToList),
    ("Heap.Binomial: toList.fromList/sort", test binomial_fromListToList),
    ("Heap.Skew:     toList.fromList/sort", test skew_fromListToList),
    ("Tree.AVL:      toList.fromList/sort", test avl_fromListToList),
    ("Tree.Splay:    toList.fromList/sort", test splay_fromListToList)]

main  = mapM_ (\(s,a) -> printf "%-25s: " s >> a) tests
 
instance Arbitrary Char where
    arbitrary     = choose ('\0', '\128')

            
hans-3.0.2
1 matches
src/Hans/Time.hs
module Hans.Time (
    module Hans.Time,
    H.Entry(..),
    H.toUnsortedList,
  ) where

import qualified Data.Heap as H
import           Data.Time.Clock (UTCTime,NominalDiffTime,diffUTCTime)
import           Data.Tuple (swap)

            
heap-1.0.4
7 matches
Data/Heap/Internal.hs

import Control.Exception
import Data.Foldable ( Foldable(foldl, foldr, foldMap), foldl' )
import Data.List ( groupBy, sortBy )
import Data.Semigroup
import Data.Monoid
import Data.Ord
import Data.Typeable
import Prelude hiding ( foldl, foldr, span, splitAt, foldMap )

            
Data/Heap/Internal.hs

-- | /O(n log n)/. Build a 'HeapT' from the given priority-value pairs.
fromList :: (Ord prio) => [(prio, val)] -> HeapT prio val
fromList = fromDescList . sortBy (flip (comparing fst))
{-# INLINE fromList #-}

-- | /O(n log n)/. List all priority-value pairs of the 'HeapT' in no specific
-- order.
toList :: HeapT prio val -> [(prio, val)]

            
Data/Heap/Internal.hs
{-# INLINE toAscList #-}

-- | List the priority-value pairs of the 'HeapT' just like 'toAscList' does,
-- but don't ignore the value @val@ when sorting.
toPairAscList :: (Ord prio, Ord val) => HeapT prio val -> [(prio, val)]
toPairAscList = concat
    . fmap (sortBy (comparing snd))
    . groupBy (\x y -> fst x == fst y)
    . toAscList

            
Data/Heap.hs
--    elements by implementing an instance of 'HeapItem' and let the maintainer
--    know what's missing.
--
-- All sorts of heaps mentioned above ('MinHeap', 'MaxHeap', 'MinPrioHeap' and
-- 'MaxPrioHeap') are built on the same underlying type: @'HeapT' prio val@. It is
-- a simple minimum priority heap. The trick is, that you never insert @(prio,
-- val)@ pairs directly: You only insert an \"external representation\", usually
-- called @item@, and an appropriate 'HeapItem' instance is used to 'split' the
-- @item@ to a @(prio, val)@ pair. For details refer to the documentation of

            
Data/Heap.hs
break p = span (not . p)

-- | /O(n log n)/. Build a 'Heap' from the given items. Assuming you have a
-- sorted list, you probably want to use 'fromDescList' or 'fromAscList', they
-- are faster than this function.
fromList :: (HeapItem pol item) => [item] -> Heap pol item
fromList = I.fromList . fmap split

-- | /O(n log n)/. List all items of the 'Heap' in no specific order.

            
Test/Heap/Internal.hs
    qc "splitAt" splitAtProperty
    qc "span" spanProperty
    qc "fromList/toList" (listProperty :: [Char] -> Bool)
    qc "fromDescList/toAscList" (sortedListProperty :: [Char] -> Bool)
    where
    testProp :: Char -> Int -> Bool
    testProp c i = even i && isLetter c

instance (Arbitrary prio, Arbitrary val, Ord prio) => Arbitrary (HeapT prio val) where

            
Test/Heap/Internal.hs

listProperty :: (Ord prio) => [prio] -> Bool
listProperty xs = let
    list = List.sort xs
    heap = fromList (zip xs [(1 :: Int) ..])
    in
    list == fmap fst (List.sort (toList heap))

sortedListProperty :: (Ord prio) => [prio] -> Bool
sortedListProperty xs = let
    list = List.sort xs
    heap = fromDescList (zip (reverse list) [(1 :: Int) ..])
    in
    list == fmap fst (toAscList heap)

            
heaps-0.3.6.1
7 matches
src/Data/Heap.hs
    , mapMonotonic      -- O(n) :: Ord b => (a -> b) -> Heap a -> Heap b
    , map               -- O(n) :: Ord b => (a -> b) -> Heap a -> Heap b
    -- * To/From Lists
    , toUnsortedList    -- O(n) :: Heap a -> [a]
    , fromList          -- O(n) :: Ord a => [a] -> Heap a
    , sort              -- O(n log n) :: Ord a => [a] -> [a]
    , traverse          -- O(n log n) :: (Applicative t, Ord b) => (a -> t b) -> Heap a -> t (Heap b)
    , mapM              -- O(n log n) :: (Monad m, Ord b) => (a -> m b) -> Heap a -> m (Heap b)
    , concatMap         -- O(n) :: Ord b => Heap a -> (a -> Heap b) -> Heap b
    -- * Filtering
    , filter            -- O(n) :: (a -> Bool) -> Heap a -> Heap a

            
src/Data/Heap.hs
    fromList `fmap` step readPrec

instance (Ord a, Data a) => Data (Heap a) where
  gfoldl k z h = z fromList `k` toUnsortedList h
  toConstr _ = fromListConstr
  dataTypeOf _ = heapDataType
  gunfold k z c = case constrIndex c of
    1 -> k (z fromList)
    _ -> error "gunfold"

            
src/Data/Heap.hs
--
-- @
-- 'fromList' '.' 'toList' ≡ 'id'
-- 'toList' '.' 'fromList' ≡ 'sort'
-- @

-- >>> size (fromList [1,5,3])
-- 3
fromList :: Ord a => [a] -> Heap a

            
src/Data/Heap.hs
fromListWith f = foldr (insertWith f) mempty
{-# INLINE fromListWith #-}

-- | /O(n log n)/. Perform a heap sort
sort :: Ord a => [a] -> [a]
sort = toList . fromList
{-# INLINE sort #-}

#if MIN_VERSION_base(4,9,0)
instance Semigroup (Heap a) where
  (<>) = union
  {-# INLINE (<>) #-}

            
src/Data/Heap.hs
  {-# INLINE mappend #-}
#endif

-- | /O(n)/. Returns the elements in the heap in some arbitrary, very likely unsorted, order.
--
-- >>> toUnsortedList (fromList [3,1,2])
-- [1,3,2]
--
-- @'fromList' '.' 'toUnsortedList' ≡ 'id'@
toUnsortedList :: Heap a -> [a]
toUnsortedList Empty = []
toUnsortedList (Heap _ _ t) = foldMap return t
{-# INLINE toUnsortedList #-}

instance Foldable Heap where
  foldMap _ Empty = mempty
  foldMap f l@(Heap _ _ t) = f (root t) `mappend` foldMap f (deleteMin l)
#if __GLASGOW_HASKELL__ >= 710

            
src/Data/Heap.hs
    go _ _ _ [] = empty
{-# INLINE intersectWith #-}

-- | /O(n log n)/. Traverse the elements of the heap in sorted order and produce a new heap using 'Applicative' side-effects.
traverse :: (Applicative t, Ord b) => (a -> t b) -> Heap a -> t (Heap b)
traverse f = fmap fromList . Traversable.traverse f . toList
{-# INLINE traverse #-}

-- | /O(n log n)/. Traverse the elements of the heap in sorted order and produce a new heap using 'Monad'ic side-effects.

            
src/Data/Heap.hs
traverse f = fmap fromList . Traversable.traverse f . toList
{-# INLINE traverse #-}

-- | /O(n log n)/. Traverse the elements of the heap in sorted order and produce a new heap using 'Monad'ic side-effects.
mapM :: (Monad m, Ord b) => (a -> m b) -> Heap a -> m (Heap b)
mapM f = liftM fromList . Traversable.mapM f . toList
{-# INLINE mapM #-}

both :: (a -> b) -> (a, a) -> (b, b)

            
huff-0.1.0.1
2 matches
src/Huff/FF/Planner.hs
import qualified Data.Heap as Heap
import           Data.IORef ( IORef, newIORef, readIORef, writeIORef )
import qualified Data.IntMap.Strict as IM
import           Data.List ( sortBy )
import           Data.Maybe ( isJust, fromMaybe, catMaybes )
import           Data.Ord ( comparing )
import qualified Data.Set as Set



            
src/Huff/FF/Planner.hs
           -> IO [Node a]
successors checkGD hash cg parent goal refs =
  do mbs <- mapM heuristic refs
     return $! sortBy (comparing nodeMeasure) (catMaybes mbs)

  where

  heuristic nodeOp =
    do let key = mkKey (applyEffect nodeOp (keyState (nodeState parent)))

            
impure-containers-0.5.0
1 matches
test/Spec.hs
  let sg = runST $ Graph.create $ \mg -> do
        forM_ xs (MGraph.insertVertex mg)
      ys = Graph.with sg (Graph.verticesToVector . Graph.vertices)
   in List.nub (List.sort xs) == List.sort (V.toList ys)

graphBuildingEdgesEverywhere :: TenElemsOrLessList Int -> Bool
graphBuildingEdgesEverywhere (TenElemsOrLessList xs) =
  let onlyEdge = 77 :: Int
      sg = runST $ Graph.create $ \mg -> do

            
salak-0.3.5.3
1 matches
src/Salak/Internal/Val.hs
newtype Vals = Vals { unVals :: Heap (Val Value) } deriving Eq

instance Show Vals where
  show (Vals v) = intercalate "," $ go <$> H.toUnsortedList v
    where
      go (Val i x) = '#' : show i ++ ('.' : show x)

instance Eq v => Ord (Val v) where
  compare (Val a _) (Val b _) = compare a b

            
streamly-0.6.1
1 matches
src/Streamly/SVar.hs
-- not dequeued until the already running one has finished and at that time we
-- would also know the exact sequence number of the already queued item.
--
-- we can even run the already queued items but they will have to be sorted in
-- layers in the heap. We can use a list of heaps for that.
{-# INLINE enqueueAhead #-}
enqueueAhead :: SVar t m a -> IORef ([t m a], Int) -> t m a -> IO ()
enqueueAhead sv q m = do
    atomicModifyIORefCAS_ q $ \ case

            
twee-lib-2.1.5
3 matches
Data/Heap.hs
--   case removeMin h of
--     Nothing -> discard
--     Just (_, h) -> invariant h
-- prop_4 h = withMaxSuccess 10000 $ List.sort (toList h) == toList h
-- prop_5 x h = withMaxSuccess 10000 $ toList (insert x h) == List.insert x (toList h)
-- prop_6 x h =
--   withMaxSuccess 1000 $
--   case removeMin h of
--     Nothing -> discard

            
Data/Heap.hs
-- prop_7 h1 h2 = withMaxSuccess 10000 $
--   invariant (union h1 h2)
-- prop_8 h1 h2 = withMaxSuccess 10000 $
--   toList (union h1 h2) == List.sort (toList h1 ++ toList h2)
-- prop_9 (Blind f) h = withMaxSuccess 10000 $
--   invariant (mapMaybe f h)
-- prop_10 (Blind f) h = withMaxSuccess 1000000 $
--   toList (mapMaybe f h) == List.sort (Maybe.mapMaybe f (toList h))

-- return []
-- main = $quickCheckAll

            
Twee/PassiveQueue.hs
makePassiveSet rule ps
  | and [passive_rule2 p == rule | p <- right] =
    mkPassiveSet proxy rule
      (Vector.fromList (map (pack True) (sort left)))
      (Vector.fromList (map (pack False) (sort right)))
  | otherwise = error "rule id does not occur in passive"
  where
    proxy :: Proxy params
    proxy = Proxy
    

            
twentyseven-0.0.0
2 matches
src/Rubik/Symmetry.hs

-- | Compute the table of smallest representatives for all symmetry classes.
-- The @RawCoord'@ coordinate of that representative is a @Repr@.
-- The table is sorted in increasing order.
symClasses
  :: RawEncodable a
  => Action s a    {- ^ Symmetry group, including the identity,
                    -   represented by its action on @a@ -}
  -> SymClassTable s a {- ^ Smallest representative -}

            
src/Rubik/Symmetry.hs
    heapOf :: RawCoord a -> H.MinHeap (RawCoord a)
    heapOf x
      = let dx = decode x
            nub' = map head . group . sort
        in H.fromAscList . tail . nub' $ map (\z -> (encode . z) dx) sym

symClassTable
  :: Int
  -> SymReprTable s a