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

3
from Control.Applicative import class Applicative (..), :: Const, class Alternative (..), class *>
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
/**
162
 * @type ((a b -> b) b -> b) -> [a]
163
 */
164 165 166
build g :== g (\x xs -> [x:xs]) []


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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