Heap.dcl 2.46 KB
Newer Older
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
1 2 3 4 5 6
definition module Data.Heap

from StdOverloaded import class < (..)
import StdClass
from Data.Maybe import :: Maybe
from StdFunc import o
Mart Lubbers's avatar
Mart Lubbers committed
7
import qualified Data.List
8
from Data.Monoid import class Monoid, class Semigroup
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

/**
 * Ported from Edward Kmett's Data.Heap by Jurriën Stutterheim 15-08-2014
 */

:: Heap a
  = Empty
  | Heap !Int (a -> a -> Bool) !(Tree a)

:: Tree a = Node Int a !(Forest a)

:: Forest a
  = Cons !(Tree a) !(Forest a)
  | Nil

instance == (Heap a)

instance < (Heap a)

28
instance Semigroup (Heap a) where mappend :: !(Heap a) !(Heap a) -> Heap a
29 30 31

instance Monoid (Heap a)

Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
32 33
:: Entry p a = Entry p a

34
null :: !(Heap a) -> Bool
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
35

36
size :: !(Heap a) -> Int
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
37

38
//* @type Heap a
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
39 40
empty :== Empty

41
//* @type a -> Heap a | Ord a
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
42 43
singleton x :== singletonWith (<=) x

44
//* @type (a a -> Bool) a -> Heap a
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
45 46
singletonWith f a :== Heap 1 f (Node 0 a Nil)

47
//* @type a (Heap a) -> (Heap a) | Ord a
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
48 49
insert :== insertWith (<=)

50
insertWith :: (a a -> Bool) a !(Heap a) -> Heap a
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
51

52
union :: !(Heap a) !(Heap a) -> Heap a
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
53

54
replicate :: a !Int -> Heap a | Ord a
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
55

56
uncons :: !(Heap a) -> Maybe (a, Heap a) | Ord a
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
57

58
//* @type (Heap a) -> Maybe (a, Heap a) | Ord a
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
59 60
viewMin :== uncons

61
minimum :: !(Heap a) -> a
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
62

63
trees :: !(Forest a) -> [Tree a]
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
64

65
deleteMin :: !(Heap a) -> Heap a
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
66

67
map :: (a -> b) !(Heap a) -> Heap b | Ord b
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
68

69
mapMonotonic :: (a -> b) !(Heap a) -> Heap b | Ord b
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
70

71
filter :: (a -> Bool) !(Heap a) -> Heap a
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
72

73
partition :: (a -> Bool) !(Heap a) -> (Heap a, Heap a)
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
74

75
split :: a !(Heap a) -> (Heap a, Heap a, Heap a)
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
76

77
//* @type Int (Heap a) -> Heap a
Mart Lubbers's avatar
Mart Lubbers committed
78
take :== withList o 'Data.List'.take
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
79

80
//* @type Int (Heap a) -> Heap a
Mart Lubbers's avatar
Mart Lubbers committed
81
drop :== withList o 'Data.List'.drop
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
82

83
//* @type Int (Heap a) -> (Heap a, Heap a)
Mart Lubbers's avatar
Mart Lubbers committed
84
splitAt :== splitWithList o 'Data.List'.splitAt
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
85

86
//* @type (a -> Bool) (Heap a) -> (Heap a, Heap a)
Mart Lubbers's avatar
Mart Lubbers committed
87
break :== splitWithList o 'Data.List'.break
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
88

89
//* @type (a -> Bool) (Heap a) -> (Heap a, Heap a)
Mart Lubbers's avatar
Mart Lubbers committed
90
span :== splitWithList o 'Data.List'.span
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
91

92
//* @type (a -> Bool) (Heap a) -> Heap a
Mart Lubbers's avatar
Mart Lubbers committed
93
takeWhile :== withList o 'Data.List'.takeWhile
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
94

95
//* @type (a -> Bool) (Heap a) -> Heap a
Mart Lubbers's avatar
Mart Lubbers committed
96
dropWhile :== withList o 'Data.List'.dropWhile
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
97

98
nub :: !(Heap a) -> Heap a
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
99

100
concatMap :: (a -> Heap b) !(Heap a) -> Heap b | Ord b
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
101

102
group :: !(Heap a) -> Heap (Heap a)
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
103

104
groupBy :: (a a -> Bool) !(Heap a) -> Heap (Heap a)
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
105

106
intersect :: !(Heap a) (Heap a) -> Heap a
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
107

108
intersectWith :: (a a -> b) !(Heap a) (Heap a) -> Heap b | Ord b
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
109

110
withList :: ([a] -> [a]) !(Heap a) -> Heap a
Jurriën Stutterheim's avatar
Jurriën Stutterheim committed
111

112
splitWithList :: ([a] -> ([a], [a])) !(Heap a) -> (Heap a, Heap a)