Как позволить функции [a] -> [a] работать с [(a, Int)]?

Question

Я часто пишу код по шаблону:

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

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

Теперь я хочу абстрагироваться

foo = indexesOf (filter (<10))

bar = indexesOf sort

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

Как выполнить magick?

Answer 1

Ваша подпись типа не будет работать.Вы должны иметь возможность передать переданной функции список кортежей, что означает, что вы должны либо использовать типы более высокого ранга, чтобы заставить ее быть полиморфной, либо явно упоминать кортежи в сигнатуре вашего типа.

БезТаким образом, вы не можете «заглянуть внутрь» функции, чтобы увидеть, как она переставляет элементы списка.На самом деле, учитывая вашу сигнатуру типа, переданная функция может делать с списком все, что угодно, включая вставку элементов, которых там даже не было!

Вот что я получил, работая с типами более высокого ранга:

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

Обратите внимание, что мне также пришлось добавить дополнительный аргумент в переданную функцию, чтобы сообщить ей, как извлечь часть, которую оназаботится об элементах списка, над которым он работает.Без этого вы могли бы использовать только функции, которые не проверяют элементы списка, например reverse, и это было бы не очень полезно.

Пример выполнения в 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

Отличный вопрос, но я подозреваю, что такой функции не существует.См. Теоремы бесплатно! .Как говорит молоток, вам нужно передать функции, которые явно принимают кортежи.

Вот моя немного упрощенная версия, которая не требует RankNTypes (что, по общему признанию, не очень хорошее улучшение по сравнению с оригинальным кодом):

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