如何让函数[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

大的问题，但我怀疑存在没有这样的功能。 见Theorems For Free!。像锤子一样，你需要传递明确带有元组的元素。

这里是我的略微简化的版本，不需要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