I’ve been working on some practical research projects lately, and so, I’ve been doing a ton of programming. In these projects I’ve been working with a lot of different data types and a particular programming pattern that I’ve been using over and over again has emerged.

The types of operations I’ve been working with have the shape `a -> D b`

which can be viewed as an indexing into the type `D b`

. Let’s consider an example, suppose we want to define generalized union over sets. That is, given a function `i : a -> Set b`

and a `s : Set a`

, then define the union \(\bigcup_{x \in s} (i\,x)\). We can define this function as follows:

```
indexedUnion :: (a -> Set b) -> Set a -> Set b
indexedUnion i = foldr (\x r -> (i x) `union` r) empty
```

We can see by this definition that we are essentially mapping the indexed operation over the set and folding, but we do this at the same time instead of going over the set twice.

Here is another example, suppose we want to take the conjunction of the application an indexed operation `i : a -> Bool`

over the set `s : Set a`

. Then we can define this function as follows:

```
indexedAnd :: (a -> Bool) -> Set a -> Bool
indexedAnd i = foldr (\x r -> (i x) && r) True
```

So at this point we can see a pattern emerging. Both of these functions can be defined by a combinator of type:

```
Foldable s => (b -> b -> b)
-> b
-> (a -> b)
-> s a
-> b
```

This is an instance of the well known `foldMap`

function on monoids:

`foldMap :: Monoid m => (a -> m) -> t a -> m`

where we get our examples above if we take the monoid on sets to be union and the empty set, and conjunction and `True`

for the monoid on booleans.

However, consider a third example where we have an operation `i : a -> b`

and a set `s : Set a`

, and we want to map over the set `s`

, but we want to do this using the accumulator pattern. Then we can define this function as follows:

```
indexedInsert :: (a -> b) -> Set a -> Set b
indexedInsert i = foldl (\a x -> (i x) `insert` a) empty
```

This uses the same programming pattern, but has a slightly more general type:

```
indexedOp :: Foldable s
=> (c -> b -> b)
-> b
-> (a -> c)
-> s a
-> b
indexedOp op start i = foldl (\a x -> (i x) `op` a) start
```

Here we can see that this combinator differs from `foldMap`

in that the binary operation we are using to fold has different types for each argument, and we index into the first. It’s easily defined using `foldr`

as well:

```
indexedOp' :: Foldable s
=> (c -> b -> b)
-> b
-> (a -> c)
-> s a
-> b
indexedOp' op start i = foldr (\x r -> (i x) `op` r) start
```

We can also define versions where we index into the second argument as well. Notice that neither of these require `op`

to be commutative, and in our third example, `insert`

is non-commutative.

Every example above can be defined using this combinator, and I’ve used this operation to define a ton of programs. It’s a very useful combinator, and I thought it would make a nice short post.