Как разыграть a -> a` вернуться к `a -> a`? - PullRequest
Новая
       66

Как разыграть a -> a` вернуться к `a -> a`?

3 голосов
/ 17 января 2020

В моей реальной задаче у меня есть функция f, переданная в качестве параметра, которая изменяет порядок в списке, но не имеет требований к типу и также не меняет тип. Я хочу применить эту функцию к [Int] и [Bool], поэтому мне нужно разрешить оба контекста, пытаясь ввести f в [Int] -> [Int] или [Bool] -> [Bool]. Я решил это с Rank2Types. Но затем я использую any в списке функций, таких как f, а any требует, чтобы функции были [a] -> [a], а не forall a. [a] -> [a].

Приведенный ниже код, в то время как бессмысленный, прекрасно воспроизводит ошибку: 

{-# LANGUAGE Rank2Types #-}

--debug :: (forall a. [a] -> [a]) -> Bool 
debug swap = any combine [swap]
  where
    combine :: (forall a. [a] -> [a]) -> Bool
    combine f =  usefonBool f && usefonInt f
    --usefonBool :: (forall a. [a] -> [a]) -> Bool
    usefonBool f = f [True,True] == [False]

    --usefonInt :: (forall a. [a] -> [a]) -> Bool
    usefonInt f = (f [1,2]) == [2,1]

Сообщение об ошибке: 

• Couldn't match type ‘a’ with ‘forall a1. [a1] -> [a1]’
  ‘a’ is a rigid type variable bound by
    the inferred type of debug :: a -> Bool
    at /path/debug.hs:(4,1)-(12,36)
  Expected type: a -> Bool
    Actual type: (forall a. [a] -> [a]) -> Bool
• In the first argument of ‘any’, namely ‘combine’
  In the expression: any combine [swap]
  In an equation for ‘debug’:
      debug swap
        = any combine [swap]
        where
            combine :: (forall a. [a] -> [a]) -> Bool
            combine f = usefonBool f && usefonInt f
            usefonBool f = f [True, ....] == [False]
            usefonInt f = (f [1, ....]) == [2, ....]
• Relevant bindings include
    swap :: a (bound at /path/debug.hs:4:7)
    debug :: a -> Bool (bound at /path/debug.hs:4:1)
|

Моя цель - найти аннотацию, позволяющую использовать f для разных типов, а затем применить любую в списке таких generi c functions.

Если я раскомментирую все свои аннотации типов (или только самые верхние), ошибка изменится на 

• Couldn't match type ‘[a0] -> [a0]’ with ‘forall a. [a] -> [a]’
  Expected type: ([a0] -> [a0]) -> Bool
    Actual type: (forall a. [a] -> [a]) -> Bool
• In the first argument of ‘any’, namely ‘combine’
  In the expression: any combine [swap]
  In an equation for ‘debug’:
      debug swap
        = any combine [swap]
        where
            combine :: (forall a. [a] -> [a]) -> Bool
            combine f = usefonBool f && usefonInt f
            usefonBool :: (forall a. [a] -> [a]) -> Bool
            usefonBool f = f [True, ....] == [False]
            ....
  |

1 Ответ

4 голосов
/ 17 января 2020

Во-первых, обратите внимание, что Rank2Types является устаревшим именем. Это эквивалентно RankNTypes в современном GH C, и это предпочтительное имя для расширения.

Вот основная проблема. «Список таких обобщенных c функций» может иметь тип: 

[forall a. [a] -> [a]]

К сожалению, это недопустимый тип Haskell, потому что Haskell не поддерживает «непредсказуемый полиморфизм». В частности, следующая программа: 

{-# LANGUAGE RankNTypes #-}
myFunctions :: [forall a. [a] -> [a]]
myFunctions = [f1, f2]
   where f1 (x:y:rest) = y:x:rest
         f2 = reverse

выдает сообщение об ошибке: 

DebugRank.hs:2:16: error:
    • Illegal polymorphic type: forall a. [a] -> [a]
      GHC doesn't yet support impredicative polymorphism
    • In the type signature: myFunctions :: [forall a. [a] -> [a]]

Существует расширение, ImpredicativeTypes. Он ненадежный и неполный, но он позволяет компилировать следующее: 

{-# LANGUAGE Rank2Types #-}
{-# LANGUAGE ImpredicativeTypes #-}

myFunctions :: [forall a. [a] -> [a]]
myFunctions = [f1, f2]
   where f1 (x:y:rest) = y:x:rest
         f2 = reverse

debug :: [forall a. [a] -> [a]] -> Bool
debug = any combine
  where
    combine :: (forall a. [a] -> [a]) -> Bool
    combine f = usefonBool f && usefonInt f
    usefonBool f = f [True,True] == [False]
    usefonInt  f = f [1,2] == [2,1]

main = print (debug myFunctions)

Я все равно рекомендую не использовать его.

Обычной альтернативой является использование оболочки newtype для функции polymorphi c: 

newtype ListFunction = ListFunction (forall a. [a] -> [a])

Для этого требуется некоторый шаблон, но без расширений, кроме RankNTypes: 

myFunctions :: [ListFunction]
myFunctions = [ListFunction f1, ListFunction f2]
   where f1 (x:y:rest) = y:x:rest
         f2 = reverse

debug :: [ListFunction] -> Bool
debug = any combine
  where
    combine :: ListFunction -> Bool
    combine (ListFunction f) = usefonBool f && usefonInt f
    usefonBool f = f [True,True] == [False]
    usefonInt  f = f [1,2] == [2,1]

Полный код: 

{-# LANGUAGE RankNTypes #-}

newtype ListFunction = ListFunction (forall a. [a] -> [a])

myFunctions :: [ListFunction]
myFunctions = [ListFunction f1, ListFunction f2]
   where f1 (x:y:rest) = y:x:rest
         f2 = reverse

debug :: [ListFunction] -> Bool
debug = any combine
  where
    combine :: ListFunction -> Bool
    combine (ListFunction f) = usefonBool f && usefonInt f
    usefonBool f = f [True,True] == [False]
    usefonInt  f = f [1,2] == [2,1]

main = print $ debug myFunctions
...