Как использовать прокси в Haskell? (возможно, используя расширение типов более высокого ранга)

Последние несколько месяцев я прилагал серьезные усилия к изучению Haskell - раньше я был, казалось бы, вечным новичком с очень ограниченными знаниями основ. Пытался применить свои новые знания на практике в нескольких шагах от-привет-мир проектов, я все время обнаруживаю, что хочу использовать шаблоны, подобные прокси, на основе классов типов. Первые пару раз, когда я понял, почему это не работает, я отклонил это как «Хорошо - я могу не найти ни одной идиоматической замены Haskell, но, скорее всего, проблема в том, что я использую неправильный подход для язык".Но я обнаружил, что мне действительно действительно не нравится, что я не могу делать вещи, подобные прокси.

Пытаясь глубже понять, почему я не могу использовать прокси, после множества экспериментов я наконец понял, что с расширением типов более высокого ранга GHC, возможно, я смогу иметь прокси. Но я все еще не могу заставить его работать, и я не уверен, почему.

Вот код для лучшего, что мне удалось ...

{-# LANGUAGE RankNTypes #-}
module Test where

--  Simple type class based on parser combinators.
class Gen g where
  get :: g x -> [(x, g x)]

instance Gen [] where
  get [] = []
  get (x:xs) = [(x, xs)]

--  Proxy type - holds a pair containing...
--    - a value of some type that supports Gen
--    - a function to indicate when an item should be skipped
newtype PROXY nestedgen x = Proxy (nestedgen x, x -> Bool)

proxyskip :: Gen nestedgen => PROXY nestedgen r -> Bool
proxyskip (Proxy (g, predf)) = case get g of
                                 []        -> False
                                 ((r,_):_) -> predf r

proxyget :: Gen nestedgen => PROXY nestedgen r -> [(r, PROXY nestedgen r)]
proxyget pr@(Proxy (sg, predf)) = if proxyskip pr
                                    then [(r2, g2) | (_, g1) <- get sg, (r2,g2) <- proxyget (Proxy (g1, predf))]
                                    else [(r3, Proxy (g3, predf)) | (r3,g3) <- get sg]

--  Instance of Gen for PROXY - get skips items where appropriate
instance Gen nestedgen => Gen (PROXY nestedgen) where
  get = proxyget

--  Test "parser"
--  Get the specified number of items, providing them as a list (within
--  the list of nondeterministic (result, state) pairs).
getN :: Gen g => Int -> g x -> [([x], g x)]
getN n g | (n < 0)  = error "negative n"
         | (n == 0) = [([], g)]
         | True     = [(r1:r2, g2) | (r1, g1) <- get g, (r2, g2) <- getN (n-1) g1]

--  Wrap some arbitrary "parser" in a PROXY that skips over the letter 'l'
proxyNotL :: Gen gb => gb Char -> PROXY gb Char
proxyNotL gg = (Proxy (gg, \ch -> (ch /= 'l')))

call_f0 :: Gen gb => (Gen ga => ga Char -> [(r, ga Char)]) -> gb Char -> [(r, PROXY gb Char)]
call_f0 f0 g0 = f0 (proxyNotL g0)

test :: Gen gb => (Gen ga => ga Char -> [(r, ga Char)]) -> gb Char -> [(r, gb Char)]
test f0 g0 = [(r, g2) | (r, Proxy (g2, _)) <- call_f0 f0 g0]

Последняя оставшаяся ошибка возникает в строке call_f0 f0 g0 = f0 (proxyNotL g0) ...

[1 of 1] Compiling Test             ( Test.hs, Test.o )

Test.hs:44:21:
    Could not deduce (ga ~ PROXY gb)
    from the context (Gen gb)
      bound by the type signature for
                 call_f0 :: Gen gb =>
                            (Gen ga => ga Char -> [(r, ga Char)])
                            -> gb Char
                            -> [(r, PROXY gb Char)]
      at Test.hs:44:1-33
      `ga' is a rigid type variable bound by
           the type signature for
             call_f0 :: Gen gb =>
                        (Gen ga => ga Char -> [(r, ga Char)])
                        -> gb Char
                        -> [(r, PROXY gb Char)]
           at Test.hs:44:1
    Expected type: ga Char
      Actual type: PROXY gb Char
    In the return type of a call of `proxyNotL'
    In the first argument of `f0', namely `(proxyNotL g0)'
    In the expression: f0 (proxyNotL g0)

Глядя в проблемной функции ...

call_f0 :: Gen gb => (Gen ga => ga Char -> [(r, ga Char)]) -> gb Char -> [(r, PROXY gb Char)]
call_f0 f0 g0 = f0 (proxyNotL g0)

Функция f0 является (если я правильно понимаю типы более высокого ранга) полиморфной функцией, переданной в качестве параметра с типом Gen ga => ga Char -> [(r, ga Char)] . В терминах перевода на C вызывающая сторона передала указатель на функцию, но не предоставила указатель vtable.

Функция proxyNotL возвращает что-то типа PROXY gb Char , и есть объявление экземпляра instance Gen nestedgen => Gen (PROXY nestedgen), где ... , так что PROXY gb Char экземпляры Gen предоставили gb экземпляры Gen , что соответствует сигнатуре типа для call_f0 .

В основном, насколько я могу судить, GHC должен сказать: «Могу ли я предоставить vtable, которую f0 требует ... хммм ... да, поскольку экземпляры PROXY gb Gen , и я знаю о PROXY и gb , да, могу ».

Итак ...почему GHC отказывается объединить ga и Proxy gb ? Почему GHC отказывается вызывать полиморфную функцию со значением аргумента, которое должно поддерживаться полиморфным типом этой функции?

Или, альтернативно, что я здесь совершенно не понимаю?