How to let a function [a] -> [a] operate on [(a,Int)]?

Question

I find myself often writing code following the pattern:

foo xs = map snd $ filter ((< 10).fst) $ zip xs [0..]

bar ys = map snd $ sortBy (compare `on` fst) $ zip ys [0..]

Now I want to abstract this away

foo = indexesOf (filter (<10))

bar = indexesOf sort

indexesOf :: ([a] -> [a]) -> [a] -> [Int] 
indexesOf f xs = map snd $ magick $ zip xs [0..] where
    magick = undefined

How to perform the magick?

Answer 1

Your type signature won't work. You need to be able to give the passed function a list of tuples, which means that you either have to use higher-rank types to force it to be polymorphic, or explicitly mention tuples in your type signature.

Without this, you can't "look inside" the function to see how it rearranges the elements of the list. In fact, given your type signature the passed function could do anything it wanted to the list, including inserting elements that weren't even in there to begin with!

Here's what I got to work using higher-rank types:

{-# LANGUAGE RankNTypes #-}

import Data.List (sortBy)
import Data.Ord (comparing)

indexesOf :: (forall b. (b -> a) -> [b] -> [b]) -> [a] -> [Int]
indexesOf f xs = map snd $ f fst $ zip xs [0..]

foo :: (Ord a, Num a) => [a] -> [Int]
foo = indexesOf (filter . ((< 10) .))

bar :: Ord a => [a] -> [Int]
bar = indexesOf (sortBy . comparing)

Note that I also had to add an extra argument to the passed function to tell it how to extract the part it cares about from the elements of the list it's working on. Without this, you would only be able to use functions that don't inspect the elements of the list, such as reverse, and that wouldn't be very useful.

Example run in GHCi:

> let xs = [42, 0, 7, 3, 12, 17, 99, 36, 8]
> foo xs
[1,2,3,8]
> bar xs
[1,3,2,8,4,5,7,0,6]
> indexesOf (const reverse) xs
[8,7,6,5,4,3,2,1,0]