如何让函数 [a] -> [a] 对 [(a,Int)] 进行操作？

我发现自己经常按照以下模式编写代码：

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?

您的类型签名将不起作用。您需要能够为传递的函数提供一个元组列表，这意味着您要么必须使用更高级别的类型来强制它是多态的，要么在类型签名中显式提及元组。

如果没有这个，您就无法“查看”函数内部以了解它如何重新排列列表的元素。事实上，给定您的类型签名，传递的函数可以对列表执行任何它想要的操作，包括插入本来就不在其中的元素！

这是我使用更高级别的类型所做的工作：

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