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

3
from Control.Applicative import class Applicative (..), :: Const, class Alternative (..)
4
from Control.Monad import class Monad (..), >>=, class MonadPlus (..)
5
from Data.Functor import class Functor (..)
6
from Data.Monoid import class Monoid (..), class Semigroup (..)
7
from Data.Maybe import :: Maybe
8
from StdOverloaded import class +, class one, class *, class zero, class <, class ==
9 10
from StdClass import class Ord
from StdFunc import flip
11 12 13 14 15

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

Camil Staps's avatar
Camil Staps committed
16 17 18 19 20 21 22 23 24 25
/**
 * 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
26 27 28
 * >     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
29 30 31 32 33
 *
 * 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
34 35 36
 * >     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
37
 */
38
class Foldable t where
39 40 41
	/**
	 * Combine the elements of a structure using a monoid.
	 */
42
    fold :: !(t m) -> m | Monoid m
43

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

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

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

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

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

73 74 75 76 77
	/**
	 * 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}}`
	 */
78
    foldr1 :: (a a -> a) !(t a) -> a
79

80 81 82 83 84
	/**
	 * 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}}`
	 */
85
    foldl1 :: (a a -> a) !(t a) -> a
86 87 88 89 90

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

instance Foldable (Const m)
91

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

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

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

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

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

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

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

134 135 136 137 138 139
/**
 * 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 ())
140

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

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

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

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

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


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

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

176 177 178 179 180
/**
 * `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.
 */
181 182
and :: (t Bool) -> Bool | Foldable t

183 184 185 186 187
/**
 * `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.
 */
188 189
or :: (t Bool) -> Bool | Foldable t

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

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

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

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

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

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

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

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

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

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

242 243 244 245 246
/**
 * 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.
 */
247
find :: (a -> Bool) (t a) -> Maybe a | Foldable t