Wyższa rankingu i impredicative rodzaje

Question

Chcę realizować następujące stripPrefixBy funkcję:

-- 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 

Próbowałem za pomocą ImpredicativeTypes i RankNTypes ale bez powodzenia. Jak mogę zaimplementować stripPrefixBy z typem, który chcę mieć?

Answer 1

Problem z podpisem, że lista jest przekazywana do stripPrefixBy jest zadeklarowana jako lista funkcji, które biorą pewien jako argument, a następnie produkować Maybe b za b Picki abonentów. Jedynymi wartościami, które mogą być zwracane funkcjom na liście, są: ⊥, Nothing i Just ⊥.

To znaczy, przy użyciu polimorfizmu impredicative The forall nie znaczy to samo robi z typem egzystencjalnie mierzalnej: tam, forall ubiega się rodzaju konstruktora, tj

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

ale tutaj mówi się, że funkcja musi być dosłownie typu forall b. a -> Maybe b.

Oto poprawiony przykład przy użyciu typu egzystencjalnego:

{-# 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 

wierzę, że UHC obsługuje wyrażając typ chcesz bezpośrednio, jak

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

Answer 2

Inna odpowiedź brzmi: „dlaczego chcesz go mieć tego typu? " Jeśli jesteś szczęśliwy, aby ograniczyć listę funkcji (pierwszy argument stripPrefixBy) wszystkie mają ten sam typ wyniku, można użyć np

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

a następnie dać stripPrefixBy następujący typ Haskell98:

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

równoważnie można zaobserwować, że wyniki tych funkcji w pierwszy argument nie może być stosowany (nic innego nie wspomina typu „B”), więc równie dobrze można mieć listę predykatów:

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 

Ale może to pytanie jest abstrakcją bardziej skomplikowanego problemu, a prostsza odpowiedź nie zadziała? Wszystko powinno być tak proste, jak to tylko możliwe, ale nie prostsze.