Come far funzionare una funzione [a] -> [a] su [(a, Int)]?

Question

mi ritrovo spesso la scrittura di codice seguendo il modello:

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

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

Ora voglio abstract questa via

foo = indexesOf (filter (<10)) 

bar = indexesOf sort 

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

come eseguire il magick?

Answer 1

La tua firma del tipo non funzionerà. Devi essere in grado di fornire alla funzione passata un elenco di tuple, il che significa che devi utilizzare tipi di rango più elevato per forzare la polimorfizzazione, o menzionare esplicitamente le tuple nella tua firma del tipo.

Senza questo, non è possibile "guardare dentro" la funzione per vedere come riordina gli elementi della lista. Infatti, data la tua firma del tipo, la funzione passata poteva fare tutto ciò che voleva nella lista, incluso inserire elementi che non erano nemmeno lì per cominciare!

Ecco quello che ho avuto modo di lavorare con i tipi più alto rango:

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

Nota che ho dovuto anche aggiungere un argomento in più per la funzione passata per dirgli come estrarre la parte che preoccupa dal elementi della lista su cui sta lavorando. Senza questo, si sarà in grado di utilizzare solo le funzioni che non controllano gli elementi dell'elenco, come ad esempio reverse e che non sarebbe molto utile.

Esempio eseguito 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] 

Answer 2

Grande questione, ma ho il sospetto che non esiste tale funzione. Vedi Theorems For Free!. Come dice il martello, è necessario passare le funzioni che accettano le tuple in modo esplicito.

Ecco la mia versione leggermente semplificata che non richiede RankNTypes (che è, certamente, non è un buon miglioramento rispetto al codice originale):

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