CODEWITHSUNDEEP
haskell
rafalio
rafalio

Reputation: 3946

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

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.

Upvotes: 3

Views: 236

Answers (4)

Lee Duhem
Lee Duhem

Reputation: 15121

That function can be implemented like this:

  1. extract key list from that association list
  2. apply that "rearrange" function to this key list to get a new key list (maybe embedded in a container)
  3. map each key in that new key list to its corresponding pair in the original association list

The above description can be translated to Haskell code directly:

generalArrange :: (Functor f, Eq a, Show a) => [(a, b)] -> ([a] -> f a) -> f (a, b)
generalArrange al f = fmap keyToPair $ f as
    where as = map fst al
          keyToPair k = lookup k al
          lookup k [] = error $ "Invalid key: " ++ show k
          lookup k (a:as)
            | k == fst a = a
            | otherwise = lookup k as

Testing:

ghc > let al = [(2, "def"), (1, "abc"), (3, "ijk")]
ghc > generalArrange al sort
[(1,"abc"),(2,"def"),(3,"ijk")]

Upvotes: 1

Gabriel Riba
Gabriel Riba

Reputation: 6738

Let's say you have a

rearrange :: [a] -> [a]

but you want to rearrange a list like [(a,b)].

you have just to rewrite rearrange as

rearrangeBy :: (c -> a) -> [c] -> [c]

substituting occurrences of element x with (f x) on check positions

Then rewrite your target function passing the new one

targetfun :: ((c -> a) -> [c] -> [c]) -> [(a,b)] -> [(a,b)]
targetfun rearrangeBy pairList = rearrangeBy fst pairList

Upvotes: 1

danidiaz
danidiaz

Reputation: 27771

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

Upvotes: 7

Ørjan Johansen
Ørjan Johansen

Reputation: 18189

There is no way to "thread along" a value of another type in a [a] -> T a function. And once that has been applied, you're going to need some way of looking up the corresponding b for each a. I think your idea of a Map is about the best you can do without rewriting f. Dependent on a, a HashMap or IntMap might work better in your specific case.

Upvotes: 0

Related Questions