xếp hạng cao hơn và impredicative loại

Question

Tôi muốn thực hiện các chức năng stripPrefixBy sau:

-- psuedo code signature 
stripPrefixBy :: forall a. [forall b. a -> Maybe b] -> [a] -> Maybe [a] 
stripPrefixBy [] xs = Just xs 
stripPrefixBy _ [] = Nothing 
stripPrefixBy (p:ps) (x:xs) = case p x of 
    Just _ -> stripPrefixBy ps xs 
    Nothing -> Nothing 

res :: Maybe String 
res = stripPrefixBy [const (Just 0), Just] "abc" 

wantThisToBeTrue :: Bool 
wantThisToBeTrue = case res of 
    Just "c" -> True 
    _ -> False 

Tôi đã cố gắng sử dụng ImpredicativeTypes và RankNTypes nhưng không may mắn. Làm thế nào tôi có thể thực hiện stripPrefixBy với loại tôi muốn nó có?

Answer 1

Vấn đề với chữ ký của bạn là danh sách truyền cho stripPrefixBy được khai báo là một danh sách các chức năng mà phải mất một số một như một cuộc tranh cãi, và sau đó tạo ra một Maybe b cho bất kỳ b pick gọi. Các giá trị duy nhất mà các hàm trong danh sách được phép trả lại là ⊥, Nothing và Just ⊥.

Đó là để nói, khi sử dụng đa hình impredicative, các forall không có nghĩa là điều tương tự nó với một loại existentially định lượng: đó, forall được áp dụng cho các loại hình constructor, tức là

data MyType = forall a. Foo a 
Foo :: forall a. a -> MyType 

nhưng ở đây, có nghĩa là hàm phải theo kiểu forall b. a -> Maybe b.

Dưới đây là một ví dụ sửa lại sử dụng một loại hiện sinh:

{-# LANGUAGE ExistentialQuantification #-} 

data Pred a = forall b. Pred (a -> Maybe b) 

stripPrefixBy :: [Pred a] -> [a] -> Maybe [a] 
stripPrefixBy [] xs = Just xs 
stripPrefixBy _ [] = Nothing 
stripPrefixBy (Pred p:ps) (x:xs) = case p x of 
    Just _ -> stripPrefixBy ps xs 
    Nothing -> Nothing 

res :: Maybe String 
res = stripPrefixBy [Pred $ const (Just 0), Pred Just] "abc" 

wantThisToBeTrue :: Bool 
wantThisToBeTrue = case res of 
    Just "c" -> True 
    _ -> False 

Tôi tin rằng UHC hỗ trợ thể hiện kiểu bạn muốn trực tiếp, như

stripPrefixBy :: [exists b. a -> Maybe b] -> [a] -> Maybe [a] 

Answer 2

phản ứng khác là, "tại sao bạn muốn nó để có loại đó? " Nếu bạn hài lòng để hạn chế danh sách các hàm (đối số đầu tiên của stripPrefixBy) tất cả để có các loại kết quả tương tự, bạn có thể sử dụng ví dụ

res :: Maybe String 
res = stripPrefixBy [const (Just undefined), Just] "abc" 

và sau đó cung cấp cho stripPrefixBy loại Haskell98 sau:

stripPrefixBy :: [a -> Maybe b] -> [a] -> Maybe [a] 

Tương tự, bạn có thể nhận thấy rằng các kết quả của các chức năng trong đối số đầu tiên không thể được sử dụng (không có gì khác đề cập đến loại "b"), vì vậy bạn cũng có thể có một danh sách các vị từ:

stripPrefixBy :: [a -> Bool] -> [a] -> Maybe [a] 
stripPrefixBy [] xs = Just xs 
stripPrefixBy _ [] = Nothing 
stripPrefixBy (p:ps) (x:xs) = case p x of 
    True -> stripPrefixBy ps xs 
    False -> Nothing 

res :: Maybe String 
res = stripPrefixBy (map (isJust.) [const (Just undefined), Just]) "abc" 

isJust :: Maybe a -> Bool 
isJust (Just _) = True 
isJust Nothing = False 

Nhưng có lẽ câu hỏi này là trừu tượng của một vấn đề phức tạp hơn bạn có, và phản ứng đơn giản hơn sẽ không hoạt động? Mọi thứ nên đơn giản nhất có thể, nhưng không đơn giản hơn.