How to write a function of type `[(a,b)] -> ([a] -> [a]) -> [(a,b)]`

Question

I have an association list

L :: [(a,b)]

where every a is associated to a b.

The b is just extra information, and the interesting part is a.

I want to work with a, so I have a function f of type [a] -> [a]. (In my problem I actually have [a] -> [[a]], so if your answer would generalize to any container that I can traverse that would be good.

I think I need something like

[(a,b)] -> ([a] -> T a) -> T (a,b)

where T is some kind of container I can traverse). This function basically rearranges the a's around, it doesn't create new ones, or delete anything.

I seem to have gotten stuck on what's the most idiomatic way to run f on the a part of [(a,b)], and at the end attach back the b.

I thought of using Data.Map to simply do a lookup at the end, but I'm wondering if there is a better way to do what I'm after, somehow "thread along" the b along with the rest of computation.

If there isn't, could you explain why?

The obvious other way is to rewrite f but I don't want that since f doesn't care about b.

Thanks a lot for any help.

Answer 1

Your type b being "just extra information" reminds me of the Env comonad, which is one of the simplest comonads and can be used to attach useful extra information to values.

import Control.Comonad
import Control.Comonad.Env

toenv :: [(a,b)] -> [Env b a]
toenv = map (\(a,b)->env b a)

Perhaps you could rewrite your function of type [a] -> [a] to work with the more general type Comonad w => [w a] -> [w a], polymorphic in the comonad. If you had to generate new values, that would be a problem (comonads don't offer a general way of putting values inside a comonadic context) but since you only want to reorder existing values (or drop them) it would work ok.

Remember that you can always can get the a value from an w a using the extract function.

To recover the original [a] -> [a] function from the generalized one, just use the Identity comonad.

import Control.Comonad.Identity

simplify :: Functor f => (forall w. Comonad w => f (w a) -> f (w a)) -> f a -> f a
simplify f = fmap extract . f . fmap Identity