Указание сигнатуры типа функции в предложении where

Question

Следующая функция реализует старую старую функцию фильтрации из списков с помощью библиотеки рекурсивных схем.

import Data.Functor.Foldable 

catafilter :: (a -> Bool) -> [a] -> [a] 
catafilter p = cata alg 
  where
    -- alg :: ListF a [a] -> [a]
    alg  Nil  =  []
    alg  (Cons x xs) = if (p x) then x : xs else xs

Компилируется и короткий тест как catafilter odd [1,2,3,4] успешно. Однако, если я раскомментирую подпись типа для alg Я получаю следующую ошибку:

src/cata.hs:8:30: error:
    • Couldn't match expected type ‘a’ with actual type ‘a1’
      ‘a1’ is a rigid type variable bound by
        the type signature for:
          alg :: forall a1. ListF a1 [a1] -> [a1]
        at src/cata.hs:6:5-29
      ‘a’ is a rigid type variable bound by
        the type signature for:
          catafilter :: forall a. (a -> Bool) -> [a] -> [a]
        at src/cata.hs:3:1-39
    • In the first argument of ‘p’, namely ‘x’
      In the expression: (p x)
      In the expression: if (p x) then x : xs else xs
    • Relevant bindings include
        xs :: [a1] (bound at src/cata.hs:8:18)
        x :: a1 (bound at src/cata.hs:8:16)
        alg :: ListF a1 [a1] -> [a1] (bound at src/cata.hs:7:5)
        p :: a -> Bool (bound at src/cata.hs:4:12)
        catafilter :: (a -> Bool) -> [a] -> [a] (bound at src/cata.hs:4:1)
  |
8 |     alg  (Cons x xs) = if (p x) then x : xs else xs
  |                              ^

В ответе на вопрос SO- type-signature-in-a-where- as предлагается использовать расширение ScopedTypeVariables. Комментарий в последнем ответе на вопрос " почему это так необычно для использования типа подписи типа в где" предлагает использовать полное количественное определение.

И я добавил:

{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE RankNTypes #-}

в верхней части моего модуля и пробовал разные типы подписей для ALG, как: alg :: forall a. ListF a [a] -> [a] или же alg :: forall b. ListF b [b] -> [b] или добавление поля для подписи типа катализатора. Ничего не скомпилировано!

Вопрос: Почему я не могу указать сигнатуру типа для alg?

Answer 1

Без расширений оригинальный некомментированный код

catafilter :: (a -> Bool) -> [a] -> [a] 
catafilter p = cata alg 
  where
    alg :: ListF a [a] -> [a]
    alg  Nil  =  []
    alg  (Cons x xs) = if (p x) then x : xs else xs

эквивалентно, после включения ScopedTypeVariablesдля явного количественного определения всех переменных типа следующим образом:

catafilter :: forall a. (a -> Bool) -> [a] -> [a] 
catafilter p = cata alg 
  where
    alg :: forall a. ListF a [a] -> [a]
    alg  Nil  =  []
    alg  (Cons x xs) = if (p x) then x : xs else xs

Это в свою очередь эквивалентно (путем альфа-преобразования количественных переменных)

catafilter :: forall a. (a -> Bool) -> [a] -> [a] 
catafilter p = cata alg 
  where
    alg :: forall b. ListF b [b] -> [b]
    alg  Nil  =  []
    alg  (Cons x xs) = if (p x) then x : xs else xs

и это вызывает ошибку типа, так как p хочет a аргумент, но p x проходит b аргумент.

Дело в том, что с включенным расширением функция начинается с forall b. ... обещает, что может работать с любым выбором b, Это обещание слишком сильно для alg, который работает только на том же a из catafilter,

Итак, решение заключается в следующем. Тип catafilter могу пообещать работать с любым a вызывающий абонент может выбрать: мы можем добавить forall a. там. Вместо, alg должен обещать только работать с тем же a из catafilter, поэтому мы повторно используем переменную типа a без добавления другого forall,

catafilter :: forall a. (a -> Bool) -> [a] -> [a] 
catafilter p = cata alg 
  where
    alg :: ListF a [a] -> [a]
    alg  Nil  =  []
    alg  (Cons x xs) = if (p x) then x : xs else xs

это компилируется с ScopedTypeVariables видит это a находится в области видимости и не добавляет неявный forall в alg (как это было бы без расширения).

Резюме:

• Без ScopedTypeVariablesкаждая аннотация типа имеет свою собственную неявную forall ... сверху, количественная оценка всех переменных. Никакая аннотация не может ссылаться на переменные других аннотаций (вы можете использовать одно и то же имя, но это не считается той же самой переменной).
• С ScopedTypeVariables, Определение foo :: forall t. T t u ; foo = def обрабатывается следующим образом:
  • переменная типа t повсеместно определяется количественно и вводится в объем при проверке типа def: введите аннотации в def может относиться к t
  • переменная типа uесли в настоящее время в области, относится к внешне определенным u
  • переменная типа u, если не в области видимости, универсально определяется количественно, но не вводится в область при проверке типа def (для совместимости здесь мы следуем тому же поведению без расширения)

Answer 2

Это работает

{-# Language ScopedTypeVariables #-}

import Data.Functor.Foldable 

catafilter :: forall a. (a -> Bool) -> [a] -> [a] 
catafilter p = cata alg
  where
    alg :: ListF a [a] -> [a]
    alg  Nil  =  []
    alg  (Cons x xs) = if (p x) then x : xs else xs

---

Если вы опустите forallэто совершенно разные aс (хотя синтаксически они одинаковы).

Из-за неявного количественного определения, ваша некомментированная версия считается

catafilter :: forall a. (a -> Bool) -> [a] -> [a] 
catafilter p = cata alg
  where
    alg :: forall a1. ListF a1 [a1] -> [a1]
    alg  Nil  =  []
    alg  (Cons x xs) = if (p x) then x : xs else xs

Это объясняет ваше сообщение об ошибке:

Couldn't match expected type ‘a’ with actual type ‘a1’

Предикат (p :: a -> Bool) ожидает аргумент типа a но это было дано x :: a1 от Cons x xs :: ListF a1 [a1]!

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

xs         :: [a1] 
x          :: a1
alg        :: ListF a1 [a1] -> [a1] 
p          :: a -> Bool 
catafilter :: (a -> Bool) -> [a] -> [a]

Answer 3

Это работает, и позволяет избежать всего этого нелогичного мошенничества с foralls

{-# LANGUAGE ScopedTypeVariables #-}

import Data.Functor.Foldable 

catafilter :: (a -> Bool) -> [a] -> [a] 
catafilter p = cata alg 
  where
    -- alg :: ListF a [a] -> [a]
    alg  (Nil :: ListF aa [aa])  =  [] :: [aa]
    alg  (Cons x xs) = if (p x) then x : xs else xs

На alg Nil Уравнение я мог бы на самом деле использовать Tyvar a: Я использовал aa просто чтобы показать, что они отличные привязки. Так как aa появляется на шаблоне, компилятор объединяет его с a от подписи за catafilter,

Вы также можете / вместо этого поместить аннотации типа на alg Cons уравнение.

Я понимаю путаницу @Jogger, почему GHC так суетливы относительно позиции forall; и нервозность, что forall возможно указывает RankNTypes,

Answer 4

Проблема в том, что alg зависит от внешнего p, так algТип не может быть просто полиморфным.

Один простой способ обойти это - сделать его независимым от каких-либо внешних сущностей, передав их в качестве аргументов функции, чтобы функция могла иметь свой просто полиморфный тип, как и ожидалось:

catafilter :: (a -> Bool) -> [a] -> [a]
catafilter = cata . alg
  where
    alg :: (b -> Bool) -> ListF b [b] -> [b]
    alg p Nil  =  []
    alg p (Cons x xs)  =  if (p x) then x : xs else xs

Для этого не нужны языковые расширения.