Cách để chức năng [a] -> [a] hoạt động trên [(a, Int)]?

Question

tôi thấy mình thường viết mã sau mô hình:

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

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

Bây giờ tôi muốn trừu tượng này đi

foo = indexesOf (filter (<10)) 

bar = indexesOf sort 

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

Làm thế nào để thực hiện các magick?

Answer 1

Chữ ký loại của bạn sẽ không hoạt động. Bạn cần có khả năng cung cấp cho hàm được truyền một danh sách các bộ dữ liệu, có nghĩa là bạn phải sử dụng các loại xếp hạng cao hơn để buộc nó phải được đa hình hoặc đề cập rõ ràng các bộ dữ liệu trong chữ ký loại của bạn.

Nếu không có điều này, bạn không thể "nhìn vào bên trong" hàm để xem cách sắp xếp lại các yếu tố trong danh sách. Trong thực tế, với chữ ký kiểu của bạn, hàm được truyền có thể làm bất cứ điều gì nó muốn trong danh sách, bao gồm chèn các phần tử thậm chí không có trong đó để bắt đầu!

Đây là những gì tôi đã làm việc sử dụng các loại-rank cao hơn:

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

Lưu ý rằng tôi cũng đã có thêm một đối số bổ sung cho các chức năng thông qua nói với nó như thế nào để trích xuất các phần nó quan tâm đến từ các yếu tố của danh sách mà nó đang hoạt động. Nếu không có điều này, bạn sẽ chỉ có thể sử dụng các chức năng không kiểm tra các phần tử của danh sách, chẳng hạn như reverse và điều đó sẽ không hữu ích lắm.

Ví dụ chạy trong 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

Great câu hỏi, nhưng tôi nghi ngờ có tồn tại không có chức năng như vậy. Xem Theorems For Free!. Giống như búa nói, bạn cần phải vượt qua các hàm nhận các bộ dữ liệu một cách rõ ràng.

Đây là phiên bản của tôi hơi đơn giản mà không đòi hỏi RankNTypes (đó là, phải thừa nhận, không phải là một cải tiến rất tốt trên mã cũ):

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