Высший рейтинг и непредсказуемые типы - PullRequest
Новая
       34

Высший рейтинг и непредсказуемые типы

15 голосов
/ 05 января 2012

Я хочу реализовать следующую stripPrefixBy функцию: 

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

Я пытался использовать ImpredicativeTypes и RankNTypes, но без удачи. Как я могу реализовать stripPrefixBy с типом, который я хочу иметь?

Ответы [ 2 ]

20 голосов
/ 05 января 2012

Проблема с вашей подписью состоит в том, что список, переданный stripPrefixBy, объявляется как список функций, которые принимают в качестве аргумента определенный a , а затем выдают Maybe b для любого * 1005.* b звонящий выбирает.Единственные значения, которые могут возвращать функции в списке, это ⊥, Nothing и Just ⊥.

То есть, когда используется неумеренный полиморфизм, forall не означаетТо же самое он делает с экзистенциально квантифицированным типом: там forall применяется к типу конструктора , то есть 

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

, но здесь говорится, что функция должнав буквальном смысле слова типа forall b. a -> Maybe b.

Вот исправленный пример использования экзистенциального типа: 

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

Я считаю, что UHC поддерживает непосредственное выражение нужного типа,как 

stripPrefixBy :: [exists b. a -> Maybe b] -> [a] -> Maybe [a]
5 голосов
/ 19 января 2012

Другой ответ: «Почему вы хотите, чтобы это было такого типа?» Если вы готовы ограничить список функций (первый аргумент stripPrefixBy) всеми одинаковыми типами результатов, вы можете использовать, например, 

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

и затем передайте stripPrefix по следующему типу Haskell98: 

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

Эквивалентно, вы могли заметить, что результаты функций в первом аргументе не могут быть использованы (ничто иное не упоминает тип "b"), поэтому вы можете также иметь список предикатов: 

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

Но, может быть, этот вопрос является абстракцией более сложной проблемы, которая у вас есть, и более простой ответ не сработает? Все должно быть максимально просто, но не проще.

...