Jak pozwolić funkcji [a] -> [a] działać na [(a, Int)]?

Question

łapię się często pisania kodu następującego wzoru:

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

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

Teraz chcę streszczenie tego z dala

foo = indexesOf (filter (<10)) 

bar = indexesOf sort 

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

Jak wykonać magick?

Answer 1

Podpis typu nie działa. Musisz dać przekazanej funkcji listę krotek, co oznacza, że ​​musisz albo użyć typów wyższego rzędu, aby wymusić to polimorficzne, albo wyraźnie wspomnieć krotki w swoim sygnaturze typu.

Bez tego nie można "zajrzeć do środka" funkcji, aby zobaczyć, jak zmienia ona układ elementów listy. W rzeczywistości, biorąc pod uwagę twój typ podpisu przekazana funkcja mogłaby zrobić wszystko, co chciała na liście, włączając wstawianie elementów, których nawet tam nie było!

Oto co mam do pracy przy użyciu typów wyższej rank:

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

Zauważ, że miałem też dodać dodatkowy argument do funkcji przekazywane, aby poinformować go, jak wyodrębnić część Dba o od elementy listy, nad którą pracuje. Bez tego można by używać tylko funkcji, które nie sprawdzają elementów listy, takich jak reverse, a to nie byłoby zbyt użyteczne.

Przykład uruchomić w 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

Dobre pytanie, ale podejrzewam, że nie istnieje taka funkcja. Zobacz Theorems For Free!. Jak mówi młotek, musisz przekazać funkcje, które jawnie przyjmują krotki.

Oto mój nieco uproszczona wersja, która nie wymaga RankNTypes (co jest, co prawda, nie jest to bardzo dobry postęp w stosunku do oryginalnego kodu):

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