Có thể mã hóa chức năng "nâng" chung trong Haskell không?

Question

Tôi không phải là fan hâm mộ lớn nhất của varargs, nhưng tôi luôn nghĩ rằng cả hai ứng dụng (f <$> x <*> y) và thành ngữ ([i| f x y |]) phong cách có quá nhiều biểu tượng. Tôi thường thích đi theo cách liftA2 f x y, nhưng tôi cũng nghĩ rằng A2 hơi xấu xí. Từ this question, tôi đã học được rằng có thể triển khai các hàm vararg trong Haskell. Bằng cách này, là nó có thể sử dụng cùng một nguyên tắc để thực hiện một chức năng nâng, chẳng hạn rằng:

lift f a b == pure f <*> a <*> b 

Tôi đã thử thay thế + bởi <*> trên mã niêm yết:

class Lift r where 
    lift :: a -> r 

instance Lift a where 
    lift = id 

instance (Lift r) => Lift (a -> r) where 
    lift x y = lift (x <*> y) 

Nhưng Tôi không thể quản lý đúng loại ...

Answer 1

Lưu ý rằng bạn có thể chuỗi bất kỳ số nào là <*>, để có được chức năng của biểu mẫu

f (a0 -> .. -> an) -> (f a0 -> .. -> f an) 

Nếu chúng tôi có loại a0 -> .. -> an và f a0 -> .. -> f an, chúng tôi có thể tính f từ điều này. Chúng tôi có thể mã hóa mối quan hệ này, và loại chung nhất, như sau

class Lift a f b | a b -> f where 
    lift' :: f a -> b 

Như bạn có thể mong đợi, các "trường hợp đệ quy" dụ sẽ chỉ cần áp dụng <*> một lần, sau đó recurse:

instance (a ~ a', f' ~ f, Lift as f rs, Applicative f) 
     => Lift (a -> as) f (f' a' -> rs) where 
    lift' f a = lift' $ f <*> a 

Các cơ sở trường hợp là khi không có thêm chức năng. Vì bạn không thể thực sự khẳng định "a không phải là một loại chức năng", điều này phụ thuộc vào trường hợp chồng chéo:

instance (f a ~ b) => Lift a f b where 
    lift' = id 

Do GHCs quy tắc lựa chọn Ví dụ, trường hợp đệ quy sẽ luôn luôn được lựa chọn, nếu có thể.

Sau đó các chức năng bạn muốn là lift' . pure:

lift :: (Lift a f b, Applicative f) => a -> b 
lift x = lift' (pure x) 

Đây là nơi mà phụ thuộc chức năng trên Lift trở nên rất quan trọng. Vì f chỉ được đề cập trong ngữ cảnh, chức năng này sẽ bị đánh máy sai trừ khi chúng tôi có thể xác định f chỉ biết a và b (xuất hiện ở bên phải của =>).

Điều này đòi hỏi nhiều phần mở rộng:

{-# LANGUAGE 
    OverlappingInstances 
    , MultiParamTypeClasses 
    , UndecidableInstances 
    , FunctionalDependencies 
    , ScopedTypeVariables 
    , TypeFamilies 
    , FlexibleInstances 
    #-} 

và, như thường lệ với các chức năng variadic trong Haskell, thường là cách duy nhất để chọn một thể hiện là để cho một chữ ký kiểu tường minh.

lift (\x y z -> x * y + z) readLn readLn readLn :: IO Int 

Con đường tôi đã viết nó, GHC sẽ vui vẻ chấp nhận lift đó là đa hình trong lập luận để f (nhưng không f chính nó).

lift (+) [1..5] [3..5] :: (Enum a, Num a) => [a] 

Đôi khi bối cảnh đủ để suy ra loại chính xác. Lưu ý rằng loại đối số là một lần nữa đa hình.

main = lift (\x y z -> x * y + z) readLn readLn readLn >>= print 

---

Tính đến GHC> = 7.10, OverlappingInstances đã bị phản đối và trình biên dịch sẽ phát hành một cảnh báo. Nó có thể sẽ được gỡ bỏ trong một số phiên bản sau này. Điều này có thể được sửa chữa bằng cách loại bỏ OverlappingInstances từ {-# LANGUAGE .. #-} pragma và thay đổi Ví dụ 2 đến

instance {-# OVERLAPS #-} (f a ~ b) => Lift a f b where 

Answer 2

Tôi giả sử bạn muốn sử dụng lift không có loại chú thích. Trong trường hợp này về cơ bản có hai lựa chọn:

Đầu tiên, nếu chúng ta sử dụng OverlappingInstances, chức năng đa hình cần chú thích:

{-# LANGUAGE 
    OverlappingInstances, 
    MultiParamTypeClasses, 
    UndecidableInstances, 
    FunctionalDependencies, 
    FlexibleInstances, 
    TypeFamilies 
    #-} 

import Control.Applicative 

class Applicative f => ApN f a b | a b -> f where 
    apN :: f a -> b 

instance (Applicative f, b ~ f a) => ApN f a b where 
    apN = id 

instance (Applicative f, ApN f a' b', b ~ (f a -> b')) => ApN f (a -> a') b where 
    apN f fa = apN (f <*> fa) 

lift :: ApN f a b => a -> b 
lift a = apN (pure a) 

-- Now we can't write "lift (+) (Just 0) Nothing" 
-- We must annotate as follows: 
-- lift ((+) :: Int -> Int -> Int) (Just 0) Nothing 
-- Monomorphic functions work fine though: 
-- lift (||) (Just True) (Just True) --> results in "Just True" 

Second, nếu chúng ta thay vì sử dụng IncoherentInstances, lift sẽ làm việc mà không chú thích thậm chí về chức năng đa hình. Tuy nhiên, một số nội dung phức tạp vẫn không kiểm tra, ví dụ: (lift . lift) (+) (Just (Just 0)) Nothing.

{-# LANGUAGE 
    IncoherentInstances, MultiParamTypeClasses, 
    UndecidableInstances,ScopedTypeVariables, 
    AllowAmbiguousTypes, FlexibleInstances, TypeFamilies 
    #-} 

import Control.Applicative 

class Applicative f => ApN f a b where 
    apN :: f a -> b 

instance (Applicative f, b ~ f a) => ApN f a b where 
    apN = id 

instance (Applicative f, ApN f a' b', b ~ (f a -> b')) => ApN f (a -> a') b where 
    apN f fa = apN (f <*> fa) 

lift :: forall f a b. ApN f a b => a -> b 
lift a = (apN :: f a -> b) (pure a) 

-- now "lift (+) (Just 0) (Just 10)" works out of the box 

tôi đã trình bày hai giải pháp thay vì chỉ một với IncoherentInstances vì IncoherentInstances là một phần mở rộng khá thô mà nên tránh nếu có thể. Nó có thể là tốt ở đây, nhưng tôi nghĩ nó đáng giá để cung cấp một giải pháp thay thế, anyway.

---

Trong cả hai trường hợp, tôi sử dụng cùng một mẹo để trợ giúp suy luận và giảm chú thích: Tôi cố gắng di chuyển thông tin từ các cá thể dụ sang ràng buộc đối tượng. Vì vậy, thay vì

instance (Applicative f) => ApN f a (f a) where 
    apN = id 

tôi viết

instance (Applicative f, b ~ f a) => ApN f a b where 
    apN = id 

Ngoài ra, trong trường hợp khác mà tôi sử dụng một tham số đơn giản b vào đầu dụ và thêm b ~ (f a ~ b') sự ràng buộc.

Lý do để thực hiện điều này là trước tiên GHC sẽ kiểm tra xem có đầu kết hợp phù hợp không và chỉ cố gắng giải quyết các ràng buộc sau khi có kết quả khớp thành công. Chúng tôi muốn đặt ít nhất gánh nặng lên đầu thể hiện và để người giải quyết hạn chế sắp xếp mọi thứ (vì nó linh hoạt hơn, có thể trì hoãn việc đánh giá và có thể sử dụng các ràng buộc từ các phần khác của chương trình).