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

11
votes

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?

2
haskellabstraction
...I'm really not clear what you're trying to do. – Louis Wasserman
I have a function working on a list, say sort. Now instead of the sorted list I want to get back the indexes of the elements. E.g. for [5.0, 8.0, 7.0] I don't want [5.0. 7.0, 8.0] but [0,2,1]. – Landei

2 Answers

11
votes

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]
4
votes

Great question, but I suspect there exists no such function. See Theorems For Free!. Like hammer says, you need to pass functions that take tuples explicitly.

Here is my slightly simplified version that doesn't require RankNTypes (which is, admittedly, not a very good improvement over the original code):

import Data.List
import Data.Ord

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

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

bar :: Ord a => [a] -> [Int]
bar = indexesOf $ sortBy $ comparing fst