Chức năng đa biến trong Haskell

Question

Sau khi đọc this article on writing polyvariadic functions in Haskell, tôi đã cố gắng viết một số của riêng mình.

Lúc đầu, tôi nghĩ tôi sẽ cố gắng khái quát hóa nó - vì vậy tôi có thể có một hàm trả về các hàm variadic bằng cách thu gọn các đối số như đã cho.

{-# OPTIONS -fglasgow-exts #-} 
module Collapse where 
class Collapse a r | r -> a where 
    collapse :: (a -> a -> a) -> a -> r 
instance Collapse a a where 
    collapse _ = id 
instance (Collapse a r) => Collapse a (a -> r) where 
    collapse f a a' = collapse f (f a a') 

Tuy nhiên, trình biên dịch không thích rằng:

Collapse.hs:5:9: 
    Functional dependencies conflict between instance declarations: 
     instance Collapse a a -- Defined at Collapse.hs:5:9-20 
     instance (Collapse a r) => Collapse a (a -> r) 
     -- Defined at Collapse.hs:7:9-43 

Nếu tôi quay trở lại và thêm một loại wrapper cho kết quả cuối cùng, tuy nhiên, nó làm việc:

module Collapse where 
class Collapse a r | r -> a where 
    collapse :: (a -> a -> a) -> a -> r 
data C a = C a 
instance Collapse a (C a) where 
    collapse _ = C . id 
instance (Collapse a r) => Collapse a (a -> r) where 
    collapse f a a' = collapse f (f a a') 
sum :: (Num a, Collapse a r) => a -> r 
sum = collapse (+) 

Một khi tôi đã thực hiện thay đổi này, nó biên soạn tốt, và tôi có thể sử dụng chức năng collapse trong ghci.

ghci> let C s = Collapse.sum 1 2 3 in s 
6 

Tôi không chắc chắn tại sao loại trình bao bọc được yêu cầu cho kết quả cuối cùng. Nếu ai đó có thể giải thích điều đó, tôi sẽ đánh giá cao điều đó. Tôi có thể thấy rằng trình biên dịch nói với tôi rằng đó là một số vấn đề với các phụ thuộc chức năng, nhưng tôi không thực sự grok việc sử dụng thích hợp của fundeps được nêu ra.

Sau đó, tôi đã cố gắng thực hiện một cách khác, và thử xác định bộ tạo hàm variadic cho các hàm lấy danh sách và trả về một giá trị. Tôi đã phải làm cùng một mẹo chứa và cũng cho phép UndecidableInstances.

{-# OPTIONS -fglasgow-exts #-} 
{-# LANGUAGE UndecidableInstances #-} 
module Variadic where 
class Variadic a b r | r -> a, r -> b where 
    variadic :: ([a] -> b) -> r 
data V a = V a 
instance Variadic a b (V b) where 
    variadic f = V $ f [] 
instance (Variadic a b r) => Variadic a b (a -> r) where 
    variadic f a = variadic (f . (a:)) 
list :: Variadic a [a] r => r 
list = variadic . id 
foldl :: (Variadic b a r) => (a -> b -> a) -> a -> r 
foldl f a = variadic (Prelude.foldl f a) 

Không cho phép UndecidableInstances trình biên dịch phàn nàn rằng tuyên bố dụ tôi là bất hợp pháp:

Variadic.hs:7:0: 
    Illegal instance declaration for `Variadic a b (V b)' 
     (the Coverage Condition fails for one of the functional dependencies; 
     Use -XUndecidableInstances to permit this) 
    In the instance declaration for `Variadic a b (V b)' 

Variadic.hs:9:0: 
    Illegal instance declaration for `Variadic a b (a -> r)' 
     (the Coverage Condition fails for one of the functional dependencies; 
     Use -XUndecidableInstances to permit this) 
    In the instance declaration for `Variadic a b (a -> r)' 

Tuy nhiên, một khi nó được biên dịch, tôi có thể thành công sử dụng nó trong ghci:

ghci> let V l = Variadic.list 1 2 3 in l 
[1,2,3] 
ghci> let vall p = Variadic.foldl (\b a -> b && (p a)) True 
ghci> :t vall 
vall :: (Variadic b Bool r) => (b -> Bool) -> r 
ghci> let V b = vall (>0) 1 2 3 in b 
True 

Tôi đoán những gì tôi đang tìm kiếm là giải thích lý do tại sao loại vùng chứa cho giá trị cuối cùng là cần thiết, cũng như tại sao tất cả các dấu câu khác nhau phụ thuộc nal là cần thiết.

Ngoài ra, đây có vẻ kỳ lạ:

ghci> let vsum = Variadic.foldl (+) 0 

<interactive>:1:10: 
    Ambiguous type variables `a', `r' in the constraint: 
     `Variadic a a r' 
     arising from a use of `Variadic.foldl' at <interactive>:1:10-29 
    Probable fix: add a type signature that fixes these type variable(s) 

<interactive>:1:10: 
    Ambiguous type variable `a'in the constraint: 
     `Num a' arising from the literal `0' at <interactive>:1:29 
    Probable fix: add a type signature that fixes these type variable(s) 
ghci> let vsum' = Variadic.foldl (+) 
ghci> :t vsum' 
(Num a, Variadic a a r) => t -> a -> r 
ghci> :t vsum' 0 
(Num a, Variadic a a r) => a -> r 
ghci> let V s = vsum' 0 1 2 3 in s 
6 

Tôi đoán đó là hậu quả của phép UndecidableInstances, nhưng tôi không biết, và tôi muốn hiểu rõ hơn về những gì đang xảy ra.

Answer 1

Ý tưởng đằng sau phụ thuộc hàm là trong một bản tuyên bố như

class Collapse a r | r -> a where 
    ... 

bit r -> a nói rằng a được xác định duy nhất bởi r. Vì vậy, bạn không thể có instance Collapse (a -> r) (a -> r) và instance Collapse a (a -> r). Lưu ý rằng instance Collapse (a -> r) (a -> r) theo sau từ instance Collapse a a để có hình ảnh hoàn chỉnh.

Nói cách khác, mã của bạn đang cố gắng thiết lập instance Collapse t t (tên của biến loại dĩ nhiên không quan trọng) và instance Collapse a (a -> r). Nếu bạn thay thế (a -> r) cho t trong khai báo sơ thẩm, bạn sẽ nhận được instance Collapse (a -> r) (a -> r).Bây giờ đây là trường hợp duy nhất của Collapse với thông số loại thứ hai bằng (a -> r) mà bạn có thể có, bởi vì khai báo lớp cho biết tham số loại đầu tiên sẽ được khấu trừ từ thứ hai. Tuy nhiên, tiếp theo bạn cố gắng thiết lập instance a (a -> r), sẽ thêm một phiên bản khác của Collapse với thông số loại thứ hai là (a -> r). Vì vậy, GHC than phiền.

Answer 2

Michał Marczyk là hoàn toàn chính xác về các vấn đề liên quan đến vấn đề, và loại trình bao bọc có vẻ như là một sửa chữa dễ dàng. Mặt khác, nếu bạn đã đọc trang web của Oleg, bạn có thể muốn truy cập deeper down the rabbit hole và thử viết một cá thể cho "bất kỳ loại nào mà không phải là một hàm".

Theo như UndecidableInstances, điều kiện bảo hiểm được mô tả here; nó sẽ được rõ ràng lý do tại sao trường hợp của bạn thất bại nó. Lưu ý rằng từ "undecidable" ở đây có nghĩa là không thể xác định theo nghĩa tương tự như trong "Sự cố dừng lại là không thể giải quyết" - nghĩa là bạn đang yêu cầu GHC cố gắng giải quyết mã có thể gửi mã vào vòng lặp vô hạn chỉ dựa trên khẳng định của bạn là không sao. Thật thú vị khi hack các ý tưởng gọn gàng, nhưng đồng ý trở thành người kiểm tra kiểu pass-pass đầu tiên của con người đối với GHC là một gánh nặng mà cá nhân tôi cảm thấy mệt mỏi.

Answer 3

Nếu bạn vẫn đang thử nghiệm với điều này, sau đây là một ví dụ về xây dựng một hàm polyvariadic từ một chức năng tham gia một danh sách, mà không đòi hỏi hoặc là một loại wrapper hoặc trường hợp undecidable:

{-# LANGUAGE FlexibleContexts #-} 
{-# LANGUAGE FlexibleInstances #-} 
{-# LANGUAGE MultiParamTypeClasses #-} 
{-# LANGUAGE FunctionalDependencies #-} 

class Variadic a b r | r -> a where 
    variadic :: ([a] -> b) -> r 

instance Variadic a b (a -> b) where 
    variadic f x = f [x] 

instance (Variadic a b (a -> r)) => Variadic a b (a -> a -> r) where 
    variadic f x y = variadic (f . (x:)) y 

vList :: (Variadic a [a] r) => r 
vList = variadic id 

vFoldl :: (Variadic b a r) => (a -> b -> a) -> a -> r 
vFoldl f z = variadic (foldl f z) 

vConcat :: (Variadic [a] [a] r) => r 
vConcat = vFoldl (++) [] 

main = do 
    putStrLn $ vConcat "abc" "def" "ghi" "jkl" 
    putStrLn $ vList 'x' 'y' 'z' 
    if vFoldl (&&) True True True True then putStrLn "Yes" else putStrLn "No" 
    if vFoldl (&&) True True False True then putStrLn "Yes" else putStrLn "No" 

Những nhược điểm để phương pháp này là trình kiểm tra kiểu phải có khả năng suy ra loại kết quả (hoặc bạn phải chú thích nó) và rằng nó không thành công trên các hằng số số đa hình; lý do cho cả hai vấn đề được thảo luận trong bài viết bạn đã đề cập. Không biết nếu bạn sẽ thấy rằng hữu ích, nhưng tôi đã tinkering với chức năng polyvariadic trước đó và nhớ câu hỏi này.