¿Cómo operar una función [a] -> [a] en [(a, Int)]?

Question

me encuentro a menudo la escritura de código siguiendo el patrón:

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

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

Ahora quiero el extracto esta distancia

foo = indexesOf (filter (<10)) 

bar = indexesOf sort 

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

cómo realizar la magick?

Answer 1

Su tipo de firma no funcionará. Debes poder darle a la función pasada una lista de tuplas, lo que significa que debes usar tipos de rango más alto para forzar que sea polimórfica o mencionar explícitamente tuplas en tu firma de tipo.

Sin esto, no puede "mirar dentro" de la función para ver cómo reorganiza los elementos de la lista. De hecho, dada su firma de tipo, la función aprobada podría hacer cualquier cosa que desee a la lista, ¡incluyendo insertar elementos que ni siquiera estaban allí para empezar!

Aquí es lo que tengo que trabajar utilizando los tipos de rango superior:

{-# 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) 

Tenga en cuenta que también he tenido que añadir un argumento adicional para la función pasada para decirle cómo extraer la parte que se preocupa de la elementos de la lista en la que está trabajando. Sin esto, solo podría usar funciones que no inspeccionan los elementos de la lista, como reverse, y eso no sería muy útil.

Ejemplo correr en 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] 

Answer 2

Muy buena pregunta, pero sospecho que no existe tal función. Ver Theorems For Free!. Como dice hammer, necesitas pasar funciones que toman tuplas explícitamente.

Aquí está mi versión ligeramente simplificada que no requiere RankNTypes (que es, sin duda, no una muy buena mejora sobre el código original):

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