Thủ thuật Typeclass cho chức năng đa thông số tổng quát nâng

Question

Tôi muốn nâng một hàm Haskell vào trong mã hóa tính toán lambda bậc cao hơn. Điều này được thực hiện gần như nguyên văn từ mã hóa Taged cuối cùng của Oleg.

class Lam r where 
    emb :: a -> r a 
    (^) :: r (r a -> r a) -> (r a -> r a) 
    lam :: (r a -> r a) -> r (r a -> r a) 

instance Lam Identity where 
    emb = Identity 
    f^x = f >>= ($ x) 
    lam f = return (f . return =<<) -- call-by-value 

eval = runIdentity 

Tôi có thể nhúng các loại Haskell tùy ý vào Lam sử dụng emb, nhưng tôi không thể sử dụng (^) cho các ứng dụng sau đó. Hơn nữa, các chức năng nâng sẽ hoạt động uể oải. Thay vào đó, tôi phải nâng ứng dụng đó lên bằng ứng dụng.

emb1 :: (Applicative r, Lam r) 
    => (a -> b) -> r (r a -> r b) 
emb1 f = lam $ \ra -> f <$> ra 

emb2 :: (Applicative r, Lam r) 
    => (a -> b -> c) -> r (r a -> r (r b -> r c)) 
emb2 f = lam $ \ra -> lam $ \rb -> f <$> ra <*> rb 

emb3 :: (Applicative r, Lam r) 
    => (a -> b -> c -> d) 
    -> r (r a -> r (r b -> r (r c -> r d))) 
emb3 f = lam $ \ra -> lam $ \rb -> lam $ \rc -> f <$> ra <*> rb <*> rc 

>>> eval $ emb2 (+)^emb 1^emb 2 
3 

Đó là rất nhiều lò hơi. Tôi muốn tạo ra một chức năng nâng chung mà sẽ làm việc cho bất kỳ chức năng tinh thần. Tôi cảm thấy như nó có thể sử dụng một cái gì đó giống như của Printf 's PrintfType hoặc fixed-vector' s Cont loại. Tôi có thể chỉ định những gì tôi muốn sử dụng chức năng loại

type family Low h  o 
type instance Low ()  o = o 
type instance Low (a, h) o = a -> Low h o 

type family Lift r h  o 
type instance Lift r()  o = o 
type instance Lift r (a, h) o = r a -> r (Lift r h o) 

class Emb r h o where 
    embed :: Low h o -> r (Lift r h o) 

instance (Lam r) => Emb r() o where 
    embed = emb 

instance (Lam r, Applicative r, Emb r h o) => Emb r (a, h) o where 
    embed = ? 

Nhưng tôi rất khó khăn thông qua phương pháp này, thường do các vấn đề về tiêm. Tôi đã có thể giải quyết tiêm với một sự kết hợp thực sự ghê tởm của wrapper newtype và biến kiểu scoped, nhưng nó không bao giờ thực sự gõ kiểm tra.

Điều này có thể diễn tả trong Haskell không?

Answer 1

Bạn có thể muốn xem Ordinary and one-pass CPS transformation theo kiểu không có thẻ. Bí quyết là để khái quát hóa các loại mũi tên trong ngôn ngữ đối tượng. Thực tế là chúng ta thường sử dụng hàm dựng kiểu của Haskell -> cho các kiểu hàm trong ngôn ngữ đối tượng (được nhúng) là sự trùng hợp và thuận tiện. Nói chung, các hàm đối tượng không ánh xạ tới các hàm Haskell một cách đơn giản. Mã trong bài viết được giới thiệu chứa ESymantics

-- How to interpret arrows and other types 
type family Arr (repr :: * -> *) (a :: *) (b :: *) :: * 

class ESymantics repr where 
    int :: Int -> repr Int 
    add :: repr Int -> repr Int -> repr Int 

    lam :: (repr a -> repr b) -> repr (Arr repr a b) 
    app :: repr (Arr repr a b) -> repr a -> repr b 

Bây giờ chúng ta có đủ tự do để giải thích Arr tùy thuộc vào một đại diện cụ thể. Bài báo được giới thiệu giải thích Arr cho cá thể CPS.

Chỉnh sửa: Hóa ra chúng ta có thể đạt được hiệu quả tương tự - xác định lại ý nghĩa của mũi tên cho ngôn ngữ đối tượng - không giới thiệu loại Arr (với các vấn đề về tiêm) và không có ESemantics. Liên kết trên, với các phép biến đổi CPS thông thường và một lần, hiển thị mã mới, sử dụng Ngữ nghĩa chuẩn và diễn giải lại ý nghĩa của hàm tạo kiểu hàm. Không còn bất kỳ vấn đề tiêm nào nữa.