Mô phỏng định lượng hiện hữu trong các kiểu trả về hàm

Question

Thỉnh thoảng tôi thấy cần phải trả về các giá trị của một kiểu định lượng hiện có. Điều này xảy ra thường xuyên nhất khi tôi đang làm việc với các loại phantom (ví dụ đại diện cho độ sâu của một cây cân bằng). AFAIK GHC không có bất kỳ loại định lượng nào là exists. Nó chỉ cho phép existentially quantified data types (trực tiếp hoặc sử dụng GADT).

Để đưa ra một ví dụ, tôi muốn có chức năng như thế này:

Cho đến nay, tôi có 2 giải pháp khả thi mà tôi sẽ thêm như một câu trả lời, tôi muốn được hạnh phúc để biết nếu có ai biết điều gì đó tốt hơn hoặc khác biệt.

Answer 1

Giải pháp tiêu chuẩn là tạo một kiểu dữ liệu định lượng hiện có. Kết quả sẽ như sau:

{-# LANGUAGE ExistentialQuantification #-} 

data Exists1 = forall a . (Show a) => Exists1 a 
instance Show Exists1 where 
    showsPrec _ (Exists1 x) = shows x 

somethingPrintable1 :: Int -> Exists1 
somethingPrintable1 x = Exists1 x 

Bây giờ, bạn có thể tự do sử dụng show (somethingPrintable 42). Exists1 không thể là newtype, tôi cho rằng đó là vì nó cần thiết để vượt qua việc thực hiện cụ thể show trong từ điển ngữ cảnh ẩn.

Đối với vectơ kiểu an, người ta có thể tiến hành theo cùng một cách để tạo ra fromList1 thực hiện:

{-# LANGUAGE GADTs #-} 

data Zero 
data Succ n 

data Vec a n where 
    Nil ::     Vec a Zero 
    Cons :: a -> Vec a n -> Vec a (Succ n) 

data Exists1 f where 
    Exists1 :: f a -> Exists1 f 

fromList1 :: [a] -> Exists1 (Vec a) 
fromList1 [] = Exists1 Nil 
fromList1 (x:xs) = case fromList1 xs of 
        Exists1 r -> Exists1 $ Cons x r 

này hoạt động tốt, nhưng nhược điểm chính tôi thấy là các nhà xây dựng bổ sung. Mỗi cuộc gọi đến fromList1 kết quả trong một ứng dụng của các nhà xây dựng, đó là ngay lập tức deconstructed. Như trước đây, newtype là không thể cho Exists1, nhưng tôi đoán không có bất kỳ ràng buộc loại lớp nào mà trình biên dịch có thể cho phép.

---

Tôi đã tạo một giải pháp khác dựa trên tiếp tục xếp hạng-N. Nó không cần hàm tạo bổ sung, nhưng tôi không chắc chắn, nếu ứng dụng hàm bổ sung không thêm một chi phí tương tự. Trong trường hợp đầu tiên, giải pháp sẽ là:

{-# LANGUAGE Rank2Types #-} 

somethingPrintable2 :: Int -> ((forall a . (Show a) => a -> r) -> r) 
somethingPrintable2 x = \c -> c x 

giờ đây một người sẽ sử dụng somethingPrintable 42 show để nhận kết quả.

Và, đối với loại Vec dữ liệu:

{-# LANGUAGE RankNTypes, GADTs #-} 

fromList2 :: [a] -> ((forall n . Vec a n -> r) -> r) 
fromList2 [] c  = c Nil 
fromList2 (x:xs) c = fromList2 xs (c . Cons x) 

-- Or wrapped as a newtype 
-- (this is where we need RankN instead of just Rank2): 
newtype Exists3 f r = Exists3 { unexists3 :: ((forall a . f a -> r) -> r) } 

fromList3 :: [a] -> Exists3 (Vec a) r 
fromList3 []  = Exists3 (\c -> c Nil) 
fromList3 (x:xs) = Exists3 (\c -> unexists3 (fromList3 xs) (c . Cons x)) 

này có thể được thực hiện một chút dễ đọc hơn sử dụng một vài chức năng helper:

-- | A helper function for creating existential values. 
exists3 :: f x -> Exists3 f r 
exists3 x = Exists3 (\c -> c x) 
{-# INLINE exists3 #-} 

-- | A helper function to mimic function application. 
(?$) :: (forall a . f a -> r) -> Exists3 f r -> r 
(?$) f x = unexists3 x f 
{-# INLINE (?$) #-} 

fromList3 :: [a] -> Exists3 (Vec a) r 
fromList3 []  = exists3 Nil 
fromList3 (x:xs) = (exists3 . Cons x) ?$ fromList3 xs 

Những khó khăn chính tôi nhìn thấy ở đây là:

1. Chi phí có thể có với ứng dụng chức năng bổ sung (Tôi không biết trình biên dịch có thể chọn bao nhiêu imize này).
2. Mã ít có thể đọc được (ít nhất là đối với những người không được sử dụng để tiếp tục).