--------------------------------------------------------------------------------
-- |
-- Module      : Control.Comonad.Heap
-- Copyright   : (c) Donnacha Oisín Kidney 2021
-- Maintainer  : mail@doisinkidney.com
-- Stability   : experimental
-- Portability : non-portable
--
-- The Heap comonad: a comonad for efficient weighted search.
--
-- This module provides the 'Heap' *comonad*.
--------------------------------------------------------------------------------

module Control.Comonad.Heap
  (Heap(..)
  ,popMin
  ,(<+>)
  ,(<><)
  ,mergeHeaps
  ,singleton)
  where

import Data.Bifunctor ( Bifunctor(bimap) )
import Data.Bifoldable ( Bifoldable(..) )
import Data.Bitraversable ( Bitraversable(..) )
import Control.Comonad.Cofree.Class ( ComonadCofree(..) )
import Control.Comonad ( Comonad(..) )
import Data.Monus ( Monus(..) )
import MonusWeightedSearch.Internal.TestHelpers ( sumsTo )
import Test.QuickCheck
    ( shrink2,
      arbitrary2,
      sized,
      Arbitrary(..),
      Arbitrary1(..),
      Arbitrary2(..) )
import Control.Applicative ( liftA3 )
import Data.Typeable (Typeable)
import Data.Data (Data)
import GHC.Generics (Generic, Generic1)
import Control.DeepSeq (NFData(..), NFData1(..), NFData2(..))
import Control.Monad (ap)
import Data.List.NonEmpty (NonEmpty(..), nonEmpty)
import Data.Functor.Classes
    ( Eq1(..),
      Ord1(..),
      Read1(liftReadPrec),
      Show1(liftShowsPrec),
      Eq2(..),
      Ord2(..),
      Read2(liftReadListPrec2, liftReadPrec2),
      Show2(..) )
import Text.Read
    ( Read(readListPrec, readPrec),
      Lexeme(Ident),
      lexP,
      parens,
      prec,
      step )

data Heap w a
  = Root !w a [Heap w a]
  deriving (Int -> Heap w a -> ShowS
[Heap w a] -> ShowS
Heap w a -> String
(Int -> Heap w a -> ShowS)
-> (Heap w a -> String) -> ([Heap w a] -> ShowS) -> Show (Heap w a)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall w a. (Show w, Show a) => Int -> Heap w a -> ShowS
forall w a. (Show w, Show a) => [Heap w a] -> ShowS
forall w a. (Show w, Show a) => Heap w a -> String
showList :: [Heap w a] -> ShowS
$cshowList :: forall w a. (Show w, Show a) => [Heap w a] -> ShowS
show :: Heap w a -> String
$cshow :: forall w a. (Show w, Show a) => Heap w a -> String
showsPrec :: Int -> Heap w a -> ShowS
$cshowsPrec :: forall w a. (Show w, Show a) => Int -> Heap w a -> ShowS
Show, ReadPrec [Heap w a]
ReadPrec (Heap w a)
Int -> ReadS (Heap w a)
ReadS [Heap w a]
(Int -> ReadS (Heap w a))
-> ReadS [Heap w a]
-> ReadPrec (Heap w a)
-> ReadPrec [Heap w a]
-> Read (Heap w a)
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
forall w a. (Read w, Read a) => ReadPrec [Heap w a]
forall w a. (Read w, Read a) => ReadPrec (Heap w a)
forall w a. (Read w, Read a) => Int -> ReadS (Heap w a)
forall w a. (Read w, Read a) => ReadS [Heap w a]
readListPrec :: ReadPrec [Heap w a]
$creadListPrec :: forall w a. (Read w, Read a) => ReadPrec [Heap w a]
readPrec :: ReadPrec (Heap w a)
$creadPrec :: forall w a. (Read w, Read a) => ReadPrec (Heap w a)
readList :: ReadS [Heap w a]
$creadList :: forall w a. (Read w, Read a) => ReadS [Heap w a]
readsPrec :: Int -> ReadS (Heap w a)
$creadsPrec :: forall w a. (Read w, Read a) => Int -> ReadS (Heap w a)
Read, Heap w a -> Heap w a -> Bool
(Heap w a -> Heap w a -> Bool)
-> (Heap w a -> Heap w a -> Bool) -> Eq (Heap w a)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall w a. (Eq w, Eq a) => Heap w a -> Heap w a -> Bool
/= :: Heap w a -> Heap w a -> Bool
$c/= :: forall w a. (Eq w, Eq a) => Heap w a -> Heap w a -> Bool
== :: Heap w a -> Heap w a -> Bool
$c== :: forall w a. (Eq w, Eq a) => Heap w a -> Heap w a -> Bool
Eq, Eq (Heap w a)
Eq (Heap w a)
-> (Heap w a -> Heap w a -> Ordering)
-> (Heap w a -> Heap w a -> Bool)
-> (Heap w a -> Heap w a -> Bool)
-> (Heap w a -> Heap w a -> Bool)
-> (Heap w a -> Heap w a -> Bool)
-> (Heap w a -> Heap w a -> Heap w a)
-> (Heap w a -> Heap w a -> Heap w a)
-> Ord (Heap w a)
Heap w a -> Heap w a -> Bool
Heap w a -> Heap w a -> Ordering
Heap w a -> Heap w a -> Heap w a
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
forall {w} {a}. (Ord w, Ord a) => Eq (Heap w a)
forall w a. (Ord w, Ord a) => Heap w a -> Heap w a -> Bool
forall w a. (Ord w, Ord a) => Heap w a -> Heap w a -> Ordering
forall w a. (Ord w, Ord a) => Heap w a -> Heap w a -> Heap w a
min :: Heap w a -> Heap w a -> Heap w a
$cmin :: forall w a. (Ord w, Ord a) => Heap w a -> Heap w a -> Heap w a
max :: Heap w a -> Heap w a -> Heap w a
$cmax :: forall w a. (Ord w, Ord a) => Heap w a -> Heap w a -> Heap w a
>= :: Heap w a -> Heap w a -> Bool
$c>= :: forall w a. (Ord w, Ord a) => Heap w a -> Heap w a -> Bool
> :: Heap w a -> Heap w a -> Bool
$c> :: forall w a. (Ord w, Ord a) => Heap w a -> Heap w a -> Bool
<= :: Heap w a -> Heap w a -> Bool
$c<= :: forall w a. (Ord w, Ord a) => Heap w a -> Heap w a -> Bool
< :: Heap w a -> Heap w a -> Bool
$c< :: forall w a. (Ord w, Ord a) => Heap w a -> Heap w a -> Bool
compare :: Heap w a -> Heap w a -> Ordering
$ccompare :: forall w a. (Ord w, Ord a) => Heap w a -> Heap w a -> Ordering
Ord, (forall a b. (a -> b) -> Heap w a -> Heap w b)
-> (forall a b. a -> Heap w b -> Heap w a) -> Functor (Heap w)
forall a b. a -> Heap w b -> Heap w a
forall a b. (a -> b) -> Heap w a -> Heap w b
forall w a b. a -> Heap w b -> Heap w a
forall w a b. (a -> b) -> Heap w a -> Heap w b
forall (f :: Type -> Type).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
<$ :: forall a b. a -> Heap w b -> Heap w a
$c<$ :: forall w a b. a -> Heap w b -> Heap w a
fmap :: forall a b. (a -> b) -> Heap w a -> Heap w b
$cfmap :: forall w a b. (a -> b) -> Heap w a -> Heap w b
Functor, (forall m. Monoid m => Heap w m -> m)
-> (forall m a. Monoid m => (a -> m) -> Heap w a -> m)
-> (forall m a. Monoid m => (a -> m) -> Heap w a -> m)
-> (forall a b. (a -> b -> b) -> b -> Heap w a -> b)
-> (forall a b. (a -> b -> b) -> b -> Heap w a -> b)
-> (forall b a. (b -> a -> b) -> b -> Heap w a -> b)
-> (forall b a. (b -> a -> b) -> b -> Heap w a -> b)
-> (forall a. (a -> a -> a) -> Heap w a -> a)
-> (forall a. (a -> a -> a) -> Heap w a -> a)
-> (forall a. Heap w a -> [a])
-> (forall a. Heap w a -> Bool)
-> (forall a. Heap w a -> Int)
-> (forall a. Eq a => a -> Heap w a -> Bool)
-> (forall a. Ord a => Heap w a -> a)
-> (forall a. Ord a => Heap w a -> a)
-> (forall a. Num a => Heap w a -> a)
-> (forall a. Num a => Heap w a -> a)
-> Foldable (Heap w)
forall a. Eq a => a -> Heap w a -> Bool
forall a. Num a => Heap w a -> a
forall a. Ord a => Heap w a -> a
forall m. Monoid m => Heap w m -> m
forall a. Heap w a -> Bool
forall a. Heap w a -> Int
forall a. Heap w a -> [a]
forall a. (a -> a -> a) -> Heap w a -> a
forall w a. Eq a => a -> Heap w a -> Bool
forall w a. Num a => Heap w a -> a
forall w a. Ord a => Heap w a -> a
forall m a. Monoid m => (a -> m) -> Heap w a -> m
forall w m. Monoid m => Heap w m -> m
forall w a. Heap w a -> Bool
forall w a. Heap w a -> Int
forall w a. Heap w a -> [a]
forall b a. (b -> a -> b) -> b -> Heap w a -> b
forall a b. (a -> b -> b) -> b -> Heap w a -> b
forall w a. (a -> a -> a) -> Heap w a -> a
forall w m a. Monoid m => (a -> m) -> Heap w a -> m
forall w b a. (b -> a -> b) -> b -> Heap w a -> b
forall w a b. (a -> b -> b) -> b -> Heap w a -> b
forall (t :: Type -> Type).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Int)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
product :: forall a. Num a => Heap w a -> a
$cproduct :: forall w a. Num a => Heap w a -> a
sum :: forall a. Num a => Heap w a -> a
$csum :: forall w a. Num a => Heap w a -> a
minimum :: forall a. Ord a => Heap w a -> a
$cminimum :: forall w a. Ord a => Heap w a -> a
maximum :: forall a. Ord a => Heap w a -> a
$cmaximum :: forall w a. Ord a => Heap w a -> a
elem :: forall a. Eq a => a -> Heap w a -> Bool
$celem :: forall w a. Eq a => a -> Heap w a -> Bool
length :: forall a. Heap w a -> Int
$clength :: forall w a. Heap w a -> Int
null :: forall a. Heap w a -> Bool
$cnull :: forall w a. Heap w a -> Bool
toList :: forall a. Heap w a -> [a]
$ctoList :: forall w a. Heap w a -> [a]
foldl1 :: forall a. (a -> a -> a) -> Heap w a -> a
$cfoldl1 :: forall w a. (a -> a -> a) -> Heap w a -> a
foldr1 :: forall a. (a -> a -> a) -> Heap w a -> a
$cfoldr1 :: forall w a. (a -> a -> a) -> Heap w a -> a
foldl' :: forall b a. (b -> a -> b) -> b -> Heap w a -> b
$cfoldl' :: forall w b a. (b -> a -> b) -> b -> Heap w a -> b
foldl :: forall b a. (b -> a -> b) -> b -> Heap w a -> b
$cfoldl :: forall w b a. (b -> a -> b) -> b -> Heap w a -> b
foldr' :: forall a b. (a -> b -> b) -> b -> Heap w a -> b
$cfoldr' :: forall w a b. (a -> b -> b) -> b -> Heap w a -> b
foldr :: forall a b. (a -> b -> b) -> b -> Heap w a -> b
$cfoldr :: forall w a b. (a -> b -> b) -> b -> Heap w a -> b
foldMap' :: forall m a. Monoid m => (a -> m) -> Heap w a -> m
$cfoldMap' :: forall w m a. Monoid m => (a -> m) -> Heap w a -> m
foldMap :: forall m a. Monoid m => (a -> m) -> Heap w a -> m
$cfoldMap :: forall w m a. Monoid m => (a -> m) -> Heap w a -> m
fold :: forall m. Monoid m => Heap w m -> m
$cfold :: forall w m. Monoid m => Heap w m -> m
Foldable, Functor (Heap w)
Foldable (Heap w)
Functor (Heap w)
-> Foldable (Heap w)
-> (forall (f :: Type -> Type) a b.
    Applicative f =>
    (a -> f b) -> Heap w a -> f (Heap w b))
-> (forall (f :: Type -> Type) a.
    Applicative f =>
    Heap w (f a) -> f (Heap w a))
-> (forall (m :: Type -> Type) a b.
    Monad m =>
    (a -> m b) -> Heap w a -> m (Heap w b))
-> (forall (m :: Type -> Type) a.
    Monad m =>
    Heap w (m a) -> m (Heap w a))
-> Traversable (Heap w)
forall w. Functor (Heap w)
forall w. Foldable (Heap w)
forall w (m :: Type -> Type) a.
Monad m =>
Heap w (m a) -> m (Heap w a)
forall w (f :: Type -> Type) a.
Applicative f =>
Heap w (f a) -> f (Heap w a)
forall w (m :: Type -> Type) a b.
Monad m =>
(a -> m b) -> Heap w a -> m (Heap w b)
forall w (f :: Type -> Type) a b.
Applicative f =>
(a -> f b) -> Heap w a -> f (Heap w b)
forall (t :: Type -> Type).
Functor t
-> Foldable t
-> (forall (f :: Type -> Type) a b.
    Applicative f =>
    (a -> f b) -> t a -> f (t b))
-> (forall (f :: Type -> Type) a.
    Applicative f =>
    t (f a) -> f (t a))
-> (forall (m :: Type -> Type) a b.
    Monad m =>
    (a -> m b) -> t a -> m (t b))
-> (forall (m :: Type -> Type) a. Monad m => t (m a) -> m (t a))
-> Traversable t
forall (m :: Type -> Type) a.
Monad m =>
Heap w (m a) -> m (Heap w a)
forall (f :: Type -> Type) a.
Applicative f =>
Heap w (f a) -> f (Heap w a)
forall (m :: Type -> Type) a b.
Monad m =>
(a -> m b) -> Heap w a -> m (Heap w b)
forall (f :: Type -> Type) a b.
Applicative f =>
(a -> f b) -> Heap w a -> f (Heap w b)
sequence :: forall (m :: Type -> Type) a.
Monad m =>
Heap w (m a) -> m (Heap w a)
$csequence :: forall w (m :: Type -> Type) a.
Monad m =>
Heap w (m a) -> m (Heap w a)
mapM :: forall (m :: Type -> Type) a b.
Monad m =>
(a -> m b) -> Heap w a -> m (Heap w b)
$cmapM :: forall w (m :: Type -> Type) a b.
Monad m =>
(a -> m b) -> Heap w a -> m (Heap w b)
sequenceA :: forall (f :: Type -> Type) a.
Applicative f =>
Heap w (f a) -> f (Heap w a)
$csequenceA :: forall w (f :: Type -> Type) a.
Applicative f =>
Heap w (f a) -> f (Heap w a)
traverse :: forall (f :: Type -> Type) a b.
Applicative f =>
(a -> f b) -> Heap w a -> f (Heap w b)
$ctraverse :: forall w (f :: Type -> Type) a b.
Applicative f =>
(a -> f b) -> Heap w a -> f (Heap w b)
Traversable, Typeable (Heap w a)
Typeable (Heap w a)
-> (forall (c :: Type -> Type).
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> Heap w a -> c (Heap w a))
-> (forall (c :: Type -> Type).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c (Heap w a))
-> (Heap w a -> Constr)
-> (Heap w a -> DataType)
-> (forall (t :: Type -> Type) (c :: Type -> Type).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c (Heap w a)))
-> (forall (t :: Type -> Type -> Type) (c :: Type -> Type).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e))
    -> Maybe (c (Heap w a)))
-> ((forall b. Data b => b -> b) -> Heap w a -> Heap w a)
-> (forall r r'.
    (r -> r' -> r)
    -> r -> (forall d. Data d => d -> r') -> Heap w a -> r)
-> (forall r r'.
    (r' -> r -> r)
    -> r -> (forall d. Data d => d -> r') -> Heap w a -> r)
-> (forall u. (forall d. Data d => d -> u) -> Heap w a -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> Heap w a -> u)
-> (forall (m :: Type -> Type).
    Monad m =>
    (forall d. Data d => d -> m d) -> Heap w a -> m (Heap w a))
-> (forall (m :: Type -> Type).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> Heap w a -> m (Heap w a))
-> (forall (m :: Type -> Type).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> Heap w a -> m (Heap w a))
-> Data (Heap w a)
Heap w a -> DataType
Heap w a -> Constr
(forall b. Data b => b -> b) -> Heap w a -> Heap w a
forall a.
Typeable a
-> (forall (c :: Type -> Type).
    (forall d b. Data d => c (d -> b) -> d -> c b)
    -> (forall g. g -> c g) -> a -> c a)
-> (forall (c :: Type -> Type).
    (forall b r. Data b => c (b -> r) -> c r)
    -> (forall r. r -> c r) -> Constr -> c a)
-> (a -> Constr)
-> (a -> DataType)
-> (forall (t :: Type -> Type) (c :: Type -> Type).
    Typeable t =>
    (forall d. Data d => c (t d)) -> Maybe (c a))
-> (forall (t :: Type -> Type -> Type) (c :: Type -> Type).
    Typeable t =>
    (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c a))
-> ((forall b. Data b => b -> b) -> a -> a)
-> (forall r r'.
    (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall r r'.
    (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> a -> r)
-> (forall u. (forall d. Data d => d -> u) -> a -> [u])
-> (forall u. Int -> (forall d. Data d => d -> u) -> a -> u)
-> (forall (m :: Type -> Type).
    Monad m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: Type -> Type).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> (forall (m :: Type -> Type).
    MonadPlus m =>
    (forall d. Data d => d -> m d) -> a -> m a)
-> Data a
forall u. Int -> (forall d. Data d => d -> u) -> Heap w a -> u
forall u. (forall d. Data d => d -> u) -> Heap w a -> [u]
forall {w} {a}. (Data w, Data a) => Typeable (Heap w a)
forall w a. (Data w, Data a) => Heap w a -> DataType
forall w a. (Data w, Data a) => Heap w a -> Constr
forall w a.
(Data w, Data a) =>
(forall b. Data b => b -> b) -> Heap w a -> Heap w a
forall w a u.
(Data w, Data a) =>
Int -> (forall d. Data d => d -> u) -> Heap w a -> u
forall w a u.
(Data w, Data a) =>
(forall d. Data d => d -> u) -> Heap w a -> [u]
forall w a r r'.
(Data w, Data a) =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Heap w a -> r
forall w a r r'.
(Data w, Data a) =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> Heap w a -> r
forall w a (m :: Type -> Type).
(Data w, Data a, Monad m) =>
(forall d. Data d => d -> m d) -> Heap w a -> m (Heap w a)
forall w a (m :: Type -> Type).
(Data w, Data a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> Heap w a -> m (Heap w a)
forall w a (c :: Type -> Type).
(Data w, Data a) =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Heap w a)
forall w a (c :: Type -> Type).
(Data w, Data a) =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Heap w a -> c (Heap w a)
forall w a (t :: Type -> Type) (c :: Type -> Type).
(Data w, Data a, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (Heap w a))
forall w a (t :: Type -> Type -> Type) (c :: Type -> Type).
(Data w, Data a, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Heap w a))
forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Heap w a -> r
forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> Heap w a -> r
forall (m :: Type -> Type).
Monad m =>
(forall d. Data d => d -> m d) -> Heap w a -> m (Heap w a)
forall (m :: Type -> Type).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Heap w a -> m (Heap w a)
forall (c :: Type -> Type).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Heap w a)
forall (c :: Type -> Type).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Heap w a -> c (Heap w a)
forall (t :: Type -> Type) (c :: Type -> Type).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (Heap w a))
forall (t :: Type -> Type -> Type) (c :: Type -> Type).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Heap w a))
gmapMo :: forall (m :: Type -> Type).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Heap w a -> m (Heap w a)
$cgmapMo :: forall w a (m :: Type -> Type).
(Data w, Data a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> Heap w a -> m (Heap w a)
gmapMp :: forall (m :: Type -> Type).
MonadPlus m =>
(forall d. Data d => d -> m d) -> Heap w a -> m (Heap w a)
$cgmapMp :: forall w a (m :: Type -> Type).
(Data w, Data a, MonadPlus m) =>
(forall d. Data d => d -> m d) -> Heap w a -> m (Heap w a)
gmapM :: forall (m :: Type -> Type).
Monad m =>
(forall d. Data d => d -> m d) -> Heap w a -> m (Heap w a)
$cgmapM :: forall w a (m :: Type -> Type).
(Data w, Data a, Monad m) =>
(forall d. Data d => d -> m d) -> Heap w a -> m (Heap w a)
gmapQi :: forall u. Int -> (forall d. Data d => d -> u) -> Heap w a -> u
$cgmapQi :: forall w a u.
(Data w, Data a) =>
Int -> (forall d. Data d => d -> u) -> Heap w a -> u
gmapQ :: forall u. (forall d. Data d => d -> u) -> Heap w a -> [u]
$cgmapQ :: forall w a u.
(Data w, Data a) =>
(forall d. Data d => d -> u) -> Heap w a -> [u]
gmapQr :: forall r r'.
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> Heap w a -> r
$cgmapQr :: forall w a r r'.
(Data w, Data a) =>
(r' -> r -> r)
-> r -> (forall d. Data d => d -> r') -> Heap w a -> r
gmapQl :: forall r r'.
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Heap w a -> r
$cgmapQl :: forall w a r r'.
(Data w, Data a) =>
(r -> r' -> r)
-> r -> (forall d. Data d => d -> r') -> Heap w a -> r
gmapT :: (forall b. Data b => b -> b) -> Heap w a -> Heap w a
$cgmapT :: forall w a.
(Data w, Data a) =>
(forall b. Data b => b -> b) -> Heap w a -> Heap w a
dataCast2 :: forall (t :: Type -> Type -> Type) (c :: Type -> Type).
Typeable t =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Heap w a))
$cdataCast2 :: forall w a (t :: Type -> Type -> Type) (c :: Type -> Type).
(Data w, Data a, Typeable t) =>
(forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Heap w a))
dataCast1 :: forall (t :: Type -> Type) (c :: Type -> Type).
Typeable t =>
(forall d. Data d => c (t d)) -> Maybe (c (Heap w a))
$cdataCast1 :: forall w a (t :: Type -> Type) (c :: Type -> Type).
(Data w, Data a, Typeable t) =>
(forall d. Data d => c (t d)) -> Maybe (c (Heap w a))
dataTypeOf :: Heap w a -> DataType
$cdataTypeOf :: forall w a. (Data w, Data a) => Heap w a -> DataType
toConstr :: Heap w a -> Constr
$ctoConstr :: forall w a. (Data w, Data a) => Heap w a -> Constr
gunfold :: forall (c :: Type -> Type).
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Heap w a)
$cgunfold :: forall w a (c :: Type -> Type).
(Data w, Data a) =>
(forall b r. Data b => c (b -> r) -> c r)
-> (forall r. r -> c r) -> Constr -> c (Heap w a)
gfoldl :: forall (c :: Type -> Type).
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Heap w a -> c (Heap w a)
$cgfoldl :: forall w a (c :: Type -> Type).
(Data w, Data a) =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> Heap w a -> c (Heap w a)
Data, Typeable, (forall x. Heap w a -> Rep (Heap w a) x)
-> (forall x. Rep (Heap w a) x -> Heap w a) -> Generic (Heap w a)
forall x. Rep (Heap w a) x -> Heap w a
forall x. Heap w a -> Rep (Heap w a) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall w a x. Rep (Heap w a) x -> Heap w a
forall w a x. Heap w a -> Rep (Heap w a) x
$cto :: forall w a x. Rep (Heap w a) x -> Heap w a
$cfrom :: forall w a x. Heap w a -> Rep (Heap w a) x
Generic, (forall a. Heap w a -> Rep1 (Heap w) a)
-> (forall a. Rep1 (Heap w) a -> Heap w a) -> Generic1 (Heap w)
forall a. Rep1 (Heap w) a -> Heap w a
forall a. Heap w a -> Rep1 (Heap w) a
forall w a. Rep1 (Heap w) a -> Heap w a
forall w a. Heap w a -> Rep1 (Heap w) a
forall k (f :: k -> Type).
(forall (a :: k). f a -> Rep1 f a)
-> (forall (a :: k). Rep1 f a -> f a) -> Generic1 f
$cto1 :: forall w a. Rep1 (Heap w) a -> Heap w a
$cfrom1 :: forall w a. Heap w a -> Rep1 (Heap w) a
Generic1)

instance Eq2 Heap where
  liftEq2 :: forall a b c d.
(a -> b -> Bool)
-> (c -> d -> Bool) -> Heap a c -> Heap b d -> Bool
liftEq2 a -> b -> Bool
e1 c -> d -> Bool
e2 (Root a
wx c
x [Heap a c]
xs) (Root b
wy d
y [Heap b d]
ys) = a -> b -> Bool
e1 a
wx b
wy Bool -> Bool -> Bool
&& c -> d -> Bool
e2 c
x d
y Bool -> Bool -> Bool
&& (Heap a c -> Heap b d -> Bool) -> [Heap a c] -> [Heap b d] -> Bool
forall (f :: Type -> Type) a b.
Eq1 f =>
(a -> b -> Bool) -> f a -> f b -> Bool
liftEq ((a -> b -> Bool)
-> (c -> d -> Bool) -> Heap a c -> Heap b d -> Bool
forall (f :: Type -> Type -> Type) a b c d.
Eq2 f =>
(a -> b -> Bool) -> (c -> d -> Bool) -> f a c -> f b d -> Bool
liftEq2 a -> b -> Bool
e1 c -> d -> Bool
e2) [Heap a c]
xs [Heap b d]
ys
  
instance Ord2 Heap where
  liftCompare2 :: forall a b c d.
(a -> b -> Ordering)
-> (c -> d -> Ordering) -> Heap a c -> Heap b d -> Ordering
liftCompare2 a -> b -> Ordering
c1 c -> d -> Ordering
c2 (Root a
wx c
x [Heap a c]
xs) (Root b
wy d
y [Heap b d]
ys) =
    a -> b -> Ordering
c1 a
wx b
wy Ordering -> Ordering -> Ordering
forall a. Semigroup a => a -> a -> a
<> c -> d -> Ordering
c2 c
x d
y Ordering -> Ordering -> Ordering
forall a. Semigroup a => a -> a -> a
<> (Heap a c -> Heap b d -> Ordering)
-> [Heap a c] -> [Heap b d] -> Ordering
forall (f :: Type -> Type) a b.
Ord1 f =>
(a -> b -> Ordering) -> f a -> f b -> Ordering
liftCompare ((a -> b -> Ordering)
-> (c -> d -> Ordering) -> Heap a c -> Heap b d -> Ordering
forall (f :: Type -> Type -> Type) a b c d.
Ord2 f =>
(a -> b -> Ordering)
-> (c -> d -> Ordering) -> f a c -> f b d -> Ordering
liftCompare2 a -> b -> Ordering
c1 c -> d -> Ordering
c2) [Heap a c]
xs [Heap b d]
ys

instance Show2 Heap where
  liftShowsPrec2 :: forall a b.
(Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> b -> ShowS)
-> ([b] -> ShowS)
-> Int
-> Heap a b
-> ShowS
liftShowsPrec2 Int -> a -> ShowS
s1 [a] -> ShowS
sl1 Int -> b -> ShowS
s2 [b] -> ShowS
sl2 = Int -> Heap a b -> ShowS
go where
    go :: Int -> Heap a b -> ShowS
go Int
d (Root a
w b
x [Heap a b]
xs) =
      Bool -> ShowS -> ShowS
showParen (Int
d Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
> Int
10) (ShowS -> ShowS) -> ShowS -> ShowS
forall a b. (a -> b) -> a -> b
$ String -> ShowS
showString String
"Root " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> a -> ShowS
s1 Int
11 a
w ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> ShowS
showString String
" " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> b -> ShowS
s2 Int
11 b
x ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. String -> ShowS
showString String
" " ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int -> Heap a b -> ShowS)
-> ([Heap a b] -> ShowS) -> Int -> [Heap a b] -> ShowS
forall (f :: Type -> Type) a.
Show1 f =>
(Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> f a -> ShowS
liftShowsPrec Int -> Heap a b -> ShowS
go ((Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> b -> ShowS)
-> ([b] -> ShowS)
-> [Heap a b]
-> ShowS
forall (f :: Type -> Type -> Type) a b.
Show2 f =>
(Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> b -> ShowS)
-> ([b] -> ShowS)
-> [f a b]
-> ShowS
liftShowList2 Int -> a -> ShowS
s1 [a] -> ShowS
sl1 Int -> b -> ShowS
s2 [b] -> ShowS
sl2) Int
11 [Heap a b]
xs

instance Read2 Heap where
  liftReadPrec2 :: forall a b.
ReadPrec a
-> ReadPrec [a]
-> ReadPrec b
-> ReadPrec [b]
-> ReadPrec (Heap a b)
liftReadPrec2 ReadPrec a
r1 ReadPrec [a]
rl1 ReadPrec b
r2 ReadPrec [b]
rl2 = ReadPrec (Heap a b) -> ReadPrec (Heap a b)
forall a. ReadPrec a -> ReadPrec a
parens (ReadPrec (Heap a b) -> ReadPrec (Heap a b))
-> ReadPrec (Heap a b) -> ReadPrec (Heap a b)
forall a b. (a -> b) -> a -> b
$ Int -> ReadPrec (Heap a b) -> ReadPrec (Heap a b)
forall a. Int -> ReadPrec a -> ReadPrec a
prec Int
10 (ReadPrec (Heap a b) -> ReadPrec (Heap a b))
-> ReadPrec (Heap a b) -> ReadPrec (Heap a b)
forall a b. (a -> b) -> a -> b
$ do
    Ident String
"Root" <- ReadPrec Lexeme
lexP
    a
w <- ReadPrec a -> ReadPrec a
forall a. ReadPrec a -> ReadPrec a
step ReadPrec a
r1
    b
x <- ReadPrec b -> ReadPrec b
forall a. ReadPrec a -> ReadPrec a
step ReadPrec b
r2
    [Heap a b]
xs <- ReadPrec [Heap a b] -> ReadPrec [Heap a b]
forall a. ReadPrec a -> ReadPrec a
step (ReadPrec a
-> ReadPrec [a]
-> ReadPrec b
-> ReadPrec [b]
-> ReadPrec [Heap a b]
forall (f :: Type -> Type -> Type) a b.
Read2 f =>
ReadPrec a
-> ReadPrec [a] -> ReadPrec b -> ReadPrec [b] -> ReadPrec [f a b]
liftReadListPrec2 ReadPrec a
r1 ReadPrec [a]
rl1 ReadPrec b
r2 ReadPrec [b]
rl2)
    return (a -> b -> [Heap a b] -> Heap a b
forall w a. w -> a -> [Heap w a] -> Heap w a
Root a
w b
x [Heap a b]
xs)

instance Eq w => Eq1 (Heap w) where liftEq :: forall a b. (a -> b -> Bool) -> Heap w a -> Heap w b -> Bool
liftEq = (w -> w -> Bool)
-> (a -> b -> Bool) -> Heap w a -> Heap w b -> Bool
forall (f :: Type -> Type -> Type) a b c d.
Eq2 f =>
(a -> b -> Bool) -> (c -> d -> Bool) -> f a c -> f b d -> Bool
liftEq2 w -> w -> Bool
forall a. Eq a => a -> a -> Bool
(==)
instance Ord w => Ord1 (Heap w) where liftCompare :: forall a b.
(a -> b -> Ordering) -> Heap w a -> Heap w b -> Ordering
liftCompare = (w -> w -> Ordering)
-> (a -> b -> Ordering) -> Heap w a -> Heap w b -> Ordering
forall (f :: Type -> Type -> Type) a b c d.
Ord2 f =>
(a -> b -> Ordering)
-> (c -> d -> Ordering) -> f a c -> f b d -> Ordering
liftCompare2 w -> w -> Ordering
forall a. Ord a => a -> a -> Ordering
compare
instance Show w => Show1 (Heap w) where liftShowsPrec :: forall a.
(Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> Heap w a -> ShowS
liftShowsPrec = (Int -> w -> ShowS)
-> ([w] -> ShowS)
-> (Int -> a -> ShowS)
-> ([a] -> ShowS)
-> Int
-> Heap w a
-> ShowS
forall (f :: Type -> Type -> Type) a b.
Show2 f =>
(Int -> a -> ShowS)
-> ([a] -> ShowS)
-> (Int -> b -> ShowS)
-> ([b] -> ShowS)
-> Int
-> f a b
-> ShowS
liftShowsPrec2 Int -> w -> ShowS
forall a. Show a => Int -> a -> ShowS
showsPrec [w] -> ShowS
forall a. Show a => [a] -> ShowS
showList
instance Read w => Read1 (Heap w) where liftReadPrec :: forall a. ReadPrec a -> ReadPrec [a] -> ReadPrec (Heap w a)
liftReadPrec = ReadPrec w
-> ReadPrec [w]
-> ReadPrec a
-> ReadPrec [a]
-> ReadPrec (Heap w a)
forall (f :: Type -> Type -> Type) a b.
Read2 f =>
ReadPrec a
-> ReadPrec [a] -> ReadPrec b -> ReadPrec [b] -> ReadPrec (f a b)
liftReadPrec2 ReadPrec w
forall a. Read a => ReadPrec a
readPrec ReadPrec [w]
forall a. Read a => ReadPrec [a]
readListPrec

instance (NFData w, NFData a) => NFData (Heap w a) where
  rnf :: Heap w a -> ()
rnf (Root w
w a
x [Heap w a]
xs) = w -> ()
forall a. NFData a => a -> ()
rnf w
w () -> () -> ()
`seq` a -> ()
forall a. NFData a => a -> ()
rnf a
x () -> () -> ()
`seq` [Heap w a] -> ()
forall a. NFData a => a -> ()
rnf [Heap w a]
xs
  {-# INLINE rnf #-}

instance NFData2 Heap where
  liftRnf2 :: forall a b. (a -> ()) -> (b -> ()) -> Heap a b -> ()
liftRnf2 a -> ()
r1 b -> ()
r2 (Root a
w b
x [Heap a b]
xs) = a -> ()
r1 a
w () -> () -> ()
`seq` b -> ()
r2 b
x () -> () -> ()
`seq` (Heap a b -> ()) -> [Heap a b] -> ()
forall (f :: Type -> Type) a. NFData1 f => (a -> ()) -> f a -> ()
liftRnf ((a -> ()) -> (b -> ()) -> Heap a b -> ()
forall (p :: Type -> Type -> Type) a b.
NFData2 p =>
(a -> ()) -> (b -> ()) -> p a b -> ()
liftRnf2 a -> ()
r1 b -> ()
r2) [Heap a b]
xs
  {-# INLINE liftRnf2 #-}
  
instance NFData w => NFData1 (Heap w) where
  liftRnf :: forall a. (a -> ()) -> Heap w a -> ()
liftRnf = (w -> ()) -> (a -> ()) -> Heap w a -> ()
forall (p :: Type -> Type -> Type) a b.
NFData2 p =>
(a -> ()) -> (b -> ()) -> p a b -> ()
liftRnf2 w -> ()
forall a. NFData a => a -> ()
rnf
  {-# INLINE liftRnf #-}

instance Bifunctor Heap where
  bimap :: forall a b c d. (a -> b) -> (c -> d) -> Heap a c -> Heap b d
bimap a -> b
f c -> d
g (Root a
w c
x [Heap a c]
xs) = b -> d -> [Heap b d] -> Heap b d
forall w a. w -> a -> [Heap w a] -> Heap w a
Root (a -> b
f a
w) (c -> d
g c
x) ((Heap a c -> Heap b d) -> [Heap a c] -> [Heap b d]
forall a b. (a -> b) -> [a] -> [b]
map ((a -> b) -> (c -> d) -> Heap a c -> Heap b d
forall (p :: Type -> Type -> Type) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap a -> b
f c -> d
g) [Heap a c]
xs)
  {-# INLINE bimap #-}

instance Bifoldable Heap where
  bifold :: forall m. Monoid m => Heap m m -> m
bifold (Root m
w m
x [Heap m m]
xs) = m
w m -> m -> m
forall a. Semigroup a => a -> a -> a
<> m
x m -> m -> m
forall a. Semigroup a => a -> a -> a
<> (Heap m m -> m) -> [Heap m m] -> m
forall (t :: Type -> Type) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap Heap m m -> m
forall (p :: Type -> Type -> Type) m.
(Bifoldable p, Monoid m) =>
p m m -> m
bifold [Heap m m]
xs
  bifoldMap :: forall m a b. Monoid m => (a -> m) -> (b -> m) -> Heap a b -> m
bifoldMap a -> m
f b -> m
g (Root a
w b
x [Heap a b]
xs) = a -> m
f a
w m -> m -> m
forall a. Semigroup a => a -> a -> a
<> b -> m
g b
x m -> m -> m
forall a. Semigroup a => a -> a -> a
<> (Heap a b -> m) -> [Heap a b] -> m
forall (t :: Type -> Type) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap ((a -> m) -> (b -> m) -> Heap a b -> m
forall (p :: Type -> Type -> Type) m a b.
(Bifoldable p, Monoid m) =>
(a -> m) -> (b -> m) -> p a b -> m
bifoldMap a -> m
f b -> m
g) [Heap a b]
xs
  bifoldr :: forall a c b. (a -> c -> c) -> (b -> c -> c) -> c -> Heap a b -> c
bifoldr a -> c -> c
f b -> c -> c
g c
b (Root a
w b
x [Heap a b]
xs) = a -> c -> c
f a
w (b -> c -> c
g b
x ((Heap a b -> c -> c) -> c -> [Heap a b] -> c
forall (t :: Type -> Type) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr ((c -> Heap a b -> c) -> Heap a b -> c -> c
forall a b c. (a -> b -> c) -> b -> a -> c
flip ((a -> c -> c) -> (b -> c -> c) -> c -> Heap a b -> c
forall (p :: Type -> Type -> Type) a c b.
Bifoldable p =>
(a -> c -> c) -> (b -> c -> c) -> c -> p a b -> c
bifoldr a -> c -> c
f b -> c -> c
g)) c
b [Heap a b]
xs))
  bifoldl :: forall c a b. (c -> a -> c) -> (c -> b -> c) -> c -> Heap a b -> c
bifoldl c -> a -> c
f c -> b -> c
g c
b (Root a
w b
x [Heap a b]
xs) = (c -> Heap a b -> c) -> c -> [Heap a b] -> c
forall (t :: Type -> Type) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl ((c -> a -> c) -> (c -> b -> c) -> c -> Heap a b -> c
forall (p :: Type -> Type -> Type) c a b.
Bifoldable p =>
(c -> a -> c) -> (c -> b -> c) -> c -> p a b -> c
bifoldl c -> a -> c
f c -> b -> c
g) (c -> b -> c
g (c -> a -> c
f c
b a
w) b
x) [Heap a b]
xs
  
instance Bitraversable Heap where
  bitraverse :: forall (f :: Type -> Type) a c b d.
Applicative f =>
(a -> f c) -> (b -> f d) -> Heap a b -> f (Heap c d)
bitraverse a -> f c
f b -> f d
g (Root a
w b
x [Heap a b]
xs) = (c -> d -> [Heap c d] -> Heap c d)
-> f c -> f d -> f [Heap c d] -> f (Heap c d)
forall (f :: Type -> Type) a b c d.
Applicative f =>
(a -> b -> c -> d) -> f a -> f b -> f c -> f d
liftA3 c -> d -> [Heap c d] -> Heap c d
forall w a. w -> a -> [Heap w a] -> Heap w a
Root (a -> f c
f a
w) (b -> f d
g b
x) ((Heap a b -> f (Heap c d)) -> [Heap a b] -> f [Heap c d]
forall (t :: Type -> Type) (f :: Type -> Type) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse ((a -> f c) -> (b -> f d) -> Heap a b -> f (Heap c d)
forall (t :: Type -> Type -> Type) (f :: Type -> Type) a c b d.
(Bitraversable t, Applicative f) =>
(a -> f c) -> (b -> f d) -> t a b -> f (t c d)
bitraverse a -> f c
f b -> f d
g) [Heap a b]
xs)

instance Arbitrary2 Heap where
  liftArbitrary2 :: forall a b. Gen a -> Gen b -> Gen (Heap a b)
liftArbitrary2 Gen a
la Gen b
ra = (Int -> Gen (Heap a b)) -> Gen (Heap a b)
forall a. (Int -> Gen a) -> Gen a
sized Int -> Gen (Heap a b)
go
    where
      go :: Int -> Gen (Heap a b)
go Int
n = (a -> b -> [Heap a b] -> Heap a b)
-> Gen a -> Gen b -> Gen [Heap a b] -> Gen (Heap a b)
forall (f :: Type -> Type) a b c d.
Applicative f =>
(a -> b -> c -> d) -> f a -> f b -> f c -> f d
liftA3 a -> b -> [Heap a b] -> Heap a b
forall w a. w -> a -> [Heap w a] -> Heap w a
Root Gen a
la Gen b
ra (Int -> Gen [Int]
sumsTo (Int
nInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
1) Gen [Int] -> ([Int] -> Gen [Heap a b]) -> Gen [Heap a b]
forall (m :: Type -> Type) a b. Monad m => m a -> (a -> m b) -> m b
>>= (Int -> Gen (Heap a b)) -> [Int] -> Gen [Heap a b]
forall (t :: Type -> Type) (f :: Type -> Type) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse Int -> Gen (Heap a b)
go)

  liftShrink2 :: forall a b. (a -> [a]) -> (b -> [b]) -> Heap a b -> [Heap a b]
liftShrink2 a -> [a]
ls b -> [b]
rs (Root a
w b
x [Heap a b]
xs) =
    [Heap a b]
xs [Heap a b] -> [Heap a b] -> [Heap a b]
forall a. [a] -> [a] -> [a]
++ [a -> b -> [Heap a b] -> Heap a b
forall w a. w -> a -> [Heap w a] -> Heap w a
Root a
w' b
x' [Heap a b]
xs' | ((a
w', b
x'), [Heap a b]
xs') <- ((a, b) -> [(a, b)])
-> ([Heap a b] -> [[Heap a b]])
-> ((a, b), [Heap a b])
-> [((a, b), [Heap a b])]
forall (f :: Type -> Type -> Type) a b.
Arbitrary2 f =>
(a -> [a]) -> (b -> [b]) -> f a b -> [f a b]
liftShrink2 ((a -> [a]) -> (b -> [b]) -> (a, b) -> [(a, b)]
forall (f :: Type -> Type -> Type) a b.
Arbitrary2 f =>
(a -> [a]) -> (b -> [b]) -> f a b -> [f a b]
liftShrink2 a -> [a]
ls b -> [b]
rs) ((Heap a b -> [Heap a b]) -> [Heap a b] -> [[Heap a b]]
forall (f :: Type -> Type) a.
Arbitrary1 f =>
(a -> [a]) -> f a -> [f a]
liftShrink ((a -> [a]) -> (b -> [b]) -> Heap a b -> [Heap a b]
forall (f :: Type -> Type -> Type) a b.
Arbitrary2 f =>
(a -> [a]) -> (b -> [b]) -> f a b -> [f a b]
liftShrink2 a -> [a]
ls b -> [b]
rs)) ((a
w, b
x), [Heap a b]
xs) ]

instance Arbitrary w => Arbitrary1 (Heap w) where
  liftArbitrary :: forall a. Gen a -> Gen (Heap w a)
liftArbitrary = Gen w -> Gen a -> Gen (Heap w a)
forall (f :: Type -> Type -> Type) a b.
Arbitrary2 f =>
Gen a -> Gen b -> Gen (f a b)
liftArbitrary2 Gen w
forall a. Arbitrary a => Gen a
arbitrary
  liftShrink :: forall a. (a -> [a]) -> Heap w a -> [Heap w a]
liftShrink = (w -> [w]) -> (a -> [a]) -> Heap w a -> [Heap w a]
forall (f :: Type -> Type -> Type) a b.
Arbitrary2 f =>
(a -> [a]) -> (b -> [b]) -> f a b -> [f a b]
liftShrink2 w -> [w]
forall a. Arbitrary a => a -> [a]
shrink
  
instance (Arbitrary w, Arbitrary a) => Arbitrary (Heap w a) where
  arbitrary :: Gen (Heap w a)
arbitrary = Gen (Heap w a)
forall (f :: Type -> Type -> Type) a b.
(Arbitrary2 f, Arbitrary a, Arbitrary b) =>
Gen (f a b)
arbitrary2
  shrink :: Heap w a -> [Heap w a]
shrink = Heap w a -> [Heap w a]
forall (f :: Type -> Type -> Type) a b.
(Arbitrary2 f, Arbitrary a, Arbitrary b) =>
f a b -> [f a b]
shrink2

(<+>) :: Monus w => Heap w a -> Heap w a -> Heap w a
Root w
xw a
x [Heap w a]
xs <+> :: forall w a. Monus w => Heap w a -> Heap w a -> Heap w a
<+> Root w
yw a
y [Heap w a]
ys
  | w
xw w -> w -> Bool
forall a. Ord a => a -> a -> Bool
<= w
yw  = w -> a -> [Heap w a] -> Heap w a
forall w a. w -> a -> [Heap w a] -> Heap w a
Root w
xw a
x (w -> a -> [Heap w a] -> Heap w a
forall w a. w -> a -> [Heap w a] -> Heap w a
Root (w
yw w -> w -> w
forall a. Monus a => a -> a -> a
|-| w
xw) a
y [Heap w a]
ys Heap w a -> [Heap w a] -> [Heap w a]
forall a. a -> [a] -> [a]
: [Heap w a]
xs)
  | Bool
otherwise = w -> a -> [Heap w a] -> Heap w a
forall w a. w -> a -> [Heap w a] -> Heap w a
Root w
yw a
y (w -> a -> [Heap w a] -> Heap w a
forall w a. w -> a -> [Heap w a] -> Heap w a
Root (w
xw w -> w -> w
forall a. Monus a => a -> a -> a
|-| w
yw) a
x [Heap w a]
xs Heap w a -> [Heap w a] -> [Heap w a]
forall a. a -> [a] -> [a]
: [Heap w a]
ys)
{-# INLINE (<+>) #-}

mergeHeaps :: Monus w => NonEmpty (Heap w a) -> Heap w a
mergeHeaps :: forall w a. Monus w => NonEmpty (Heap w a) -> Heap w a
mergeHeaps (Heap w a
x  :| [])           = Heap w a
x
mergeHeaps (Heap w a
x1 :| Heap w a
x2 : [])      = Heap w a
x1 Heap w a -> Heap w a -> Heap w a
forall w a. Monus w => Heap w a -> Heap w a -> Heap w a
<+> Heap w a
x2
mergeHeaps (Heap w a
x1 :| Heap w a
x2 : Heap w a
x3 : [Heap w a]
xs) = (Heap w a
x1 Heap w a -> Heap w a -> Heap w a
forall w a. Monus w => Heap w a -> Heap w a -> Heap w a
<+> Heap w a
x2) Heap w a -> Heap w a -> Heap w a
forall w a. Monus w => Heap w a -> Heap w a -> Heap w a
<+> NonEmpty (Heap w a) -> Heap w a
forall w a. Monus w => NonEmpty (Heap w a) -> Heap w a
mergeHeaps (Heap w a
x3 Heap w a -> [Heap w a] -> NonEmpty (Heap w a)
forall a. a -> [a] -> NonEmpty a
:| [Heap w a]
xs)
{-# INLINE mergeHeaps #-}

(<><) :: Semigroup w => w -> Heap w a -> Heap w a
<>< :: forall w a. Semigroup w => w -> Heap w a -> Heap w a
(<><) w
w (Root w
ws a
x [Heap w a]
xs) = w -> a -> [Heap w a] -> Heap w a
forall w a. w -> a -> [Heap w a] -> Heap w a
Root (w
w w -> w -> w
forall a. Semigroup a => a -> a -> a
<> w
ws) a
x [Heap w a]
xs
{-# INLINE (<><) #-}

popMin :: Monus w => Heap w a -> ((w, a), Maybe (Heap w a))
popMin :: forall w a. Monus w => Heap w a -> ((w, a), Maybe (Heap w a))
popMin (Root w
w a
x [Heap w a]
xs) = ((w
w, a
x), (NonEmpty (Heap w a) -> Heap w a)
-> Maybe (NonEmpty (Heap w a)) -> Maybe (Heap w a)
forall (f :: Type -> Type) a b. Functor f => (a -> b) -> f a -> f b
fmap ((w
w w -> Heap w a -> Heap w a
forall w a. Semigroup w => w -> Heap w a -> Heap w a
<><) (Heap w a -> Heap w a)
-> (NonEmpty (Heap w a) -> Heap w a)
-> NonEmpty (Heap w a)
-> Heap w a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. NonEmpty (Heap w a) -> Heap w a
forall w a. Monus w => NonEmpty (Heap w a) -> Heap w a
mergeHeaps) ([Heap w a] -> Maybe (NonEmpty (Heap w a))
forall a. [a] -> Maybe (NonEmpty a)
nonEmpty [Heap w a]
xs))
{-# INLINE popMin #-}

singleton :: w -> a -> Heap w a
singleton :: forall w a. w -> a -> Heap w a
singleton w
w a
x = w -> a -> [Heap w a] -> Heap w a
forall w a. w -> a -> [Heap w a] -> Heap w a
Root w
w a
x []
{-# INLINE singleton #-}

instance Monoid w => Applicative (Heap w) where
  pure :: forall a. a -> Heap w a
pure a
x = w -> a -> [Heap w a] -> Heap w a
forall w a. w -> a -> [Heap w a] -> Heap w a
Root w
forall a. Monoid a => a
mempty a
x []
  {-# INLINE pure #-}
  <*> :: forall a b. Heap w (a -> b) -> Heap w a -> Heap w b
(<*>) = Heap w (a -> b) -> Heap w a -> Heap w b
forall (m :: Type -> Type) a b. Monad m => m (a -> b) -> m a -> m b
ap

instance Monoid w => Monad (Heap w) where
  Root w
w1 a
x [Heap w a]
xs >>= :: forall a b. Heap w a -> (a -> Heap w b) -> Heap w b
>>= a -> Heap w b
k = case a -> Heap w b
k a
x of
    Root w
w2 b
y [Heap w b]
ys -> w -> b -> [Heap w b] -> Heap w b
forall w a. w -> a -> [Heap w a] -> Heap w a
Root (w
w1 w -> w -> w
forall a. Semigroup a => a -> a -> a
<> w
w2) b
y ([Heap w b]
ys [Heap w b] -> [Heap w b] -> [Heap w b]
forall a. [a] -> [a] -> [a]
++ (Heap w a -> Heap w b) -> [Heap w a] -> [Heap w b]
forall a b. (a -> b) -> [a] -> [b]
map (Heap w a -> (a -> Heap w b) -> Heap w b
forall (m :: Type -> Type) a b. Monad m => m a -> (a -> m b) -> m b
>>= a -> Heap w b
k) [Heap w a]
xs)
  {-# INLINE (>>=) #-}

instance Comonad (Heap w) where
  extract :: forall a. Heap w a -> a
extract (Root w
_ a
x [Heap w a]
_) = a
x
  {-# INLINE extract #-}
  duplicate :: forall a. Heap w a -> Heap w (Heap w a)
duplicate xh :: Heap w a
xh@(Root w
w a
x [Heap w a]
xs) = w -> Heap w a -> [Heap w (Heap w a)] -> Heap w (Heap w a)
forall w a. w -> a -> [Heap w a] -> Heap w a
Root w
w Heap w a
xh ((Heap w a -> Heap w (Heap w a))
-> [Heap w a] -> [Heap w (Heap w a)]
forall a b. (a -> b) -> [a] -> [b]
map Heap w a -> Heap w (Heap w a)
forall (w :: Type -> Type) a. Comonad w => w a -> w (w a)
duplicate [Heap w a]
xs)
  {-# INLINE duplicate #-}
  extend :: forall a b. (Heap w a -> b) -> Heap w a -> Heap w b
extend Heap w a -> b
f xh :: Heap w a
xh@(Root w
w a
_ [Heap w a]
xs) = w -> b -> [Heap w b] -> Heap w b
forall w a. w -> a -> [Heap w a] -> Heap w a
Root w
w (Heap w a -> b
f Heap w a
xh) ((Heap w a -> Heap w b) -> [Heap w a] -> [Heap w b]
forall a b. (a -> b) -> [a] -> [b]
map ((Heap w a -> b) -> Heap w a -> Heap w b
forall (w :: Type -> Type) a b.
Comonad w =>
(w a -> b) -> w a -> w b
extend Heap w a -> b
f) [Heap w a]
xs)
  {-# INLINE extend #-}

instance ComonadCofree [] (Heap w) where
  unwrap :: forall a. Heap w a -> [Heap w a]
unwrap (Root w
w a
x [Heap w a]
xs) = [Heap w a]
xs
  {-# INLINE unwrap #-}