Xác định việc thực hiện phương pháp dựa trên các ràng buộc có sẵn

Question

Giả sử tôi có các chức năng ghi nhớ sau đây. (Bỏ qua sự thật là họ trong sạch.)

memoEq :: Eq a  => (a -> b) -> a -> b 
memoOrd :: Ord a  => (a -> b) -> a -> b 
memoHash :: Hashable a => (a -> b) -> a -> b 

Bây giờ tôi muốn có một cấu trúc cho phép tôi chọn 'tốt nhất' của ba chức năng ghi nhớ ở trên. Cái gì mà về cơ bản nào sau đây:

memo f = case constraint_of_typevar_a_in f of 
    Eq a  -> memoEq 
    Ord a  -> memoOrd 
    Hashable a -> memoHash 

Bạn có thể thử điều này với các lớp học kiểu nhưng bạn sẽ nhận được trường hợp chồng chéo:

class Memo a where 
    memo :: (a -> b) -> a -> b 

instance Eq a => Memo a where 
    memo = memoEq 

instance Ord a => Memo a where 
    memo = memoOrd 

Tôi cũng đã cố gắng sử dụng cast để lấy những hạn chế. Tôi nhận ra rằng điều này sẽ xảy ra vào thời gian chạy và như tôi đã nói trong #haskell đây có lẽ là một ý tưởng tồi. (Tôi đã bỏ qua các trường hợp cho memoOrd và memoHash vì lợi ích ngắn gọn.)

{-# LANGUAGE ImpredicativeTypes, ScopedTypeVariables #-} 
module Main where 

import Data.Typeable 

memo :: forall a b. (Typeable a, Typeable b) => (a -> b) -> Maybe (a -> b) 
memo f = 
    let eqf = cast f :: Eq a => Maybe (a -> b) 
    in case eqf of 
     Just eqf' -> Just $ memoEq eqf' 
     Nothing -> Nothing 

memoEq :: Eq a => (a -> b) -> a -> b 
memoEq = undefined 

memoOrd :: Ord a => (a -> b) -> a -> b 
memoOrd = undefined 

Mã này tạo ra các thông báo lỗi sau:

cast.hs:8:19: 
Could not deduce (Eq a) arising from an expression type signature 
from the context (Typeable a, Typeable b) 
    bound by the type signature for 
      memo :: (Typeable a, Typeable b) => (a -> b) -> Maybe (a -> b) 
    at cast.hs:6:9-74 
Possible fix: 
    add (Eq a) to the context of 
    the type signature for 
     memo :: (Typeable a, Typeable b) => (a -> b) -> Maybe (a -> b) 
In the expression: cast f :: Eq a => Maybe (a -> b) 
In an equation for `eqf': eqf = cast f :: Eq a => Maybe (a -> b) 
In the expression: 
    let eqf = cast f :: Eq a => Maybe (a -> b) 
    in 
    case eqf of { 
     Just eqf' -> Just $ memoEq eqf' 
     Nothing -> Nothing } 

Di chuyển Eq a hạn chế bên trong Maybe đưa ra một lỗi thêm không có ràng buộc Typeable1 trên phương trình.

Không thể suy ra (Typeable1 Eq) phát sinh từ việc sử dụng của `đúc' từ bối cảnh (Typeable một, Typeable b)

Là những gì tôi muốn đạt được có thể, có lẽ sử dụng Template Haskell ? Hoặc là nó hoàn toàn không thể và không mong muốn để có thể làm điều này?

Answer 1

Trong việc thực hiện GHC của các lớp loại (và nói chung), bạn không thể tra cứu từ điển lớp học vào thời gian chạy. Thuật toán tạo mã từ điển được tích hợp vào công cụ suy luận kiểu của trình biên dịch và không có thuật toán tương ứng trong bất kỳ mã thời gian chạy nào. Theo tôi biết, không có cơ sở dữ liệu thời gian chạy của tất cả các phiên bản lớp mà bạn cần để thực hiện thuật toán đó. Nguyên tắc thiết kế đằng sau điều này là các loại không phải là dữ liệu, vì vậy một chương trình không thể kiểm tra chúng.

Hơn nữa, không thể chọn phương pháp ghi nhớ tốt nhất tại thời gian biên dịch vì hệ thống loại lớp cho phép xác định các cá thể mới. Vì bạn không thể chứng minh rằng một loại là không phải là thành viên của Hashable —có nghĩa là định nghĩa cá thể nằm trong một tệp chưa được biên soạn — bạn không thể loại trừ khả năng bất kỳ loại nhất định nào đều phải được ghi nhớ trên lớp Hashable; điều tương tự cũng xảy ra với Eq và Ord.

Tôi nghĩ giải pháp tốt nhất là chọn thủ công từng loại được ghi nhớ bằng cách viết Memo trường hợp cho mỗi hàm tạo kiểu.