Foldable.dcl 6.74 KB
Newer Older
1 2
definition module Data.Foldable

Camil Staps's avatar
Camil Staps committed
3 4
from Control.Applicative import class pure(pure), class <*>, class Applicative,
	class *>, class <*, :: Const, class Alternative(empty,<|>)
5 6 7
from Control.Monad import class Monad(bind), >>=, class MonadPlus(mzero,mplus)
from Data.Functor import class Functor
from Data.Monoid import class Monoid, class Semigroup
8
from Data.Maybe import :: Maybe
9
from StdOverloaded import class +, class one, class *, class zero, class <, class ==
10 11
from StdClass import class Ord
from StdFunc import flip
12 13 14 15 16

/**
 * Ported from Haskell's Data.Foldable by Jurriën Stutterheim 15-08-2014
 */

Camil Staps's avatar
Camil Staps committed
17 18 19 20 21 22 23 24 25 26
/**
 * Data structures that can be folded.
 *
 * For example, given a data type
 *
 * > :: Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
 *
 * a suitable instance would be
 *
 * > instance Foldable Tree where
27 28 29
 * >     foldMap f Empty = mempty
 * >     foldMap f (Leaf x) = f x
 * >     foldMap f (Node l k r) = foldMap f l <++> f k <++> foldMap f r
Camil Staps's avatar
Camil Staps committed
30 31 32 33 34
 *
 * This is suitable even for abstract types, as the monoid is assumed
 * to satisfy the monoid laws.  Alternatively, one could define foldr:
 *
 * > instance Foldable Tree where
35 36 37
 * >     foldr f z Empty = z
 * >     foldr f z (Leaf x) = f x z
 * >     foldr f z (Node l k r) = foldr f (f k (foldr f z r)) l
Camil Staps's avatar
Camil Staps committed
38
 */
39
class Foldable t where
40 41 42
	/**
	 * Combine the elements of a structure using a monoid.
	 */
43
    fold :: !(t m) -> m | Monoid m
44

45 46 47
	/**
	 * Map each element of the structure to a monoid, and combine the results.
	 */
48
    foldMap :: (a -> m) !(t a) -> m | Monoid m
49

50 51 52 53
	/**
	 * Right-associative fold of a structure.
	 * `foldr f z = 'StdList'.{{foldr}} f z {{o}} {{toList}}`
	 */
54
    foldr :: (a .b -> .b) .b !(t a) -> .b
55

56 57 58 59
	/**
	 * Right-associative fold of a structure, but with strict application of
	 * the operator.
	 */
60
    foldr` :: (a .b -> .b) !.b !(t a) -> .b
61

62 63 64 65
	/**
	 * Left-associative fold of a structure.
	 * `foldl f z = 'StdList'.{{foldl}} f z o {{toList}}`
	 */
66
    foldl :: (.b -> .(a -> .b)) .b !(t a) -> .b
67

68 69 70 71
	/**
	 * Left-associative fold of a structure, but with strict application of the
	 * operator.
	 */
72
    foldl` :: (.b -> .(a -> .b)) !.b !(t a) -> .b
73

74 75 76 77 78
	/**
	 * A variant of {{foldr}} that has no base case, and thus may only be
	 * applied to non-empty structures.
	 * `foldr1 f = 'Data.List'.{{foldr1}} f o {{toList}}`
	 */
79
    foldr1 :: (a a -> a) !(t a) -> a
80

81 82 83 84 85
	/**
	 * A variant of {{foldl}} that has no base case, and thus may only be
	 * applied to non-empty structures.
	 * `foldl1 f = 'Data.List'.{{foldl1}} f o {{toList}}`
	 */
86
    foldl1 :: (a a -> a) !(t a) -> a
87 88 89 90 91

// TODO Cleanify
//instance Ix i => Foldable (Array i)

instance Foldable (Const m)
92

93 94 95 96
/**
 * Monadic fold over the elements of a structure, associating to the right,
 * i.e. from right to left.
 */
97
foldrM :: (a b -> m b) b !(t a) -> m b | Foldable t & Monad m
98

99 100 101 102
/**
 * Monadic fold over the elements of a structure, associating to the left, i.e.
 * from left to right.
 */
103
foldlM :: (b a -> m b) b !(t a) -> m b | Foldable t & Monad m
104

105 106 107 108
/**
 * Map each element of a structure to an action, evaluate these actions from
 * left to right, and ignore the results.
 */
109
traverse_ :: (a -> f b) !(t a) -> f () | Foldable t & *> f
110

111 112
/**
 * `for_` is {{`traverse_`}} with its arguments flipped.
113
 * @type (t a) (a -> f b) -> f () | Foldable, Applicative f
114 115
 */
for_ :== flip traverse_
116

117 118 119 120
/**
 * Map each element of a structure to a monadic action, evaluate these actions
 * from left to right, and ignore the results.
 */
121
mapM_ :: (a -> m b) !(t a) -> m () | Foldable t & Monad m
122

123 124 125 126 127
/**
 * `forM_` is {{`mapM_`}} with its arguments flipped.
 * @type (t a) (a -> m b) -> m () | Foldable t & Monad m
 */
forM_ :== flip mapM_
128

129 130 131 132
/**
 * Evaluate each action in the structure from left to right, and ignore the
 * results.
 */
133
sequenceA_ :: !(t (f a)) -> f () | Foldable t & *> f
134

135 136 137 138 139 140
/**
 * Evaluate each monadic action in the structure from left to right, and ignore
 * the results.
 * @type (t (m a)) -> m () | Foldable t & Monad m
 */
sequence_ :== foldr (\ma mb -> ma >>= \_ -> mb) (pure ())
141

142 143 144 145 146
/**
 * The sum of a collection of actions, generalizing {{`concat`}}.
 * @type (t (f a)) -> f a | Foldable t & Alternative f
 */
asum :== foldr (<|>) empty
147

148 149 150 151 152
/**
 * The sum of a collection of actions, generalizing {{`concat`}}.
 * @type (t (m a)) -> m a | Foldable t & MonadPlus m
 */
msum :== foldr mplus mzero
153 154 155

// These use foldr rather than foldMap to avoid repeated concatenation.

156 157 158 159 160
/**
 * List of elements of a structure.
 * @type (t a) -> [a] | Foldable t
 */
toList t :== build (\c n -> foldr c n t)
161

162
//* @type ((a b -> b) b -> b) -> [a]
163 164 165
build g :== g (\x xs -> [x:xs]) []


166 167 168
/**
 * The concatenation of all the elements of a container of lists.
 */
169
concat :: !(t [a]) -> [a] | Foldable t
170

171 172 173 174
/**
 * Map a function over all the elements of a container and concatenate the
 * resulting lists.
 */
175
concatMap :: (a -> [b]) !(t a) -> [b] | Foldable t
176

177 178 179 180 181
/**
 * `and` returns the conjunction of a container of {{`Bool`}}s. For the result
 * to be {{`True`}}, the container must be finite; {{`False`}}, however,
 * results from a {{`False`}} value finitely far from the left end.
 */
182
and :: !(t Bool) -> Bool | Foldable t
183

184 185 186 187 188
/**
 * `or` returns the disjunction of a container of {{`Bool`}}s. For the result
 * to be {{`False`}}, the container must be finite; {{`True`}}, however,
 * results from a {{`True`}} value finitely far from the left end.
 */
189
or :: !(t Bool) -> Bool | Foldable t
190

191 192 193
/**
 * Determines whether any element of the structure satisfies the predicate.
 */
194
any :: (a -> Bool) !(t a) -> Bool | Foldable t
195

196 197 198
/**
 * Determines whether all elements of the structure satisfy the predicate.
 */
199
all :: (a -> Bool) !(t a) -> Bool | Foldable t
200

201 202 203
/**
 * The `sum` function computes the sum of the numbers of a structure.
 */
204
sum :: !(t a) -> a | Foldable t & + a & zero a
205

206 207 208
/**
 * The `product` function computes the product of the numbers of a structure.
 */
209
product :: !(t a) -> a | Foldable t & * a & one a
210

211 212 213
/**
 * The largest element of a non-empty structure.
 */
214
maximum :: !(t a) -> a | Foldable t & Ord a
215

216 217
/**
 * The largest element of a non-empty structure with respect to the given
218
 * lesser-than function.
219
 */
220
maximumBy :: (a a -> Bool) !(t a) -> a | Foldable t
221

222 223 224
/**
 * The least element of a non-empty structure.
 */
225
minimum :: !(t a) -> a | Foldable t & Ord a
226

227 228 229 230
/**
 * The least element of a non-empty structure with respect to the given
 * lesser-than function.
 */
231
minimumBy :: (a a -> Bool) !(t a) -> a | Foldable t
232

233 234 235
/**
 * Does the element occur in the structure?
 */
236
elem :: a !(t a) -> Bool | Foldable t & == a
237

238 239 240
/**
 * `notElem` is the negation of {{`elem`}}.
 */
241
notElem ::  a !(t a) -> Bool | Foldable t & == a
242

243 244 245 246 247
/**
 * The `find` function takes a predicate and a structure and returns the
 * leftmost element of the structure matching the predicate, or {{`Nothing`}}
 * if there is no such element.
 */
248
find :: (a -> Bool) !(t a) -> Maybe a | Foldable t