Перекрытие экземпляров для выравнивания кортежей

Question

Я пытаюсь написать код, чтобы удалить пустые кортежи из кортежей. Компилятор отвергает программу:

Код:

{-# LANGUAGE FlexibleInstances #-} 
{-# LANGUAGE FunctionalDependencies #-} 
{-# LANGUAGE MultiParamTypeClasses #-} 
{-# LANGUAGE OverlappingInstances #-} 
{-# LANGUAGE UndecidableInstances #-} 
{-# LANGUAGE TypeOperators #-} 

infixr 9 :* 
data a :* b = a :* !b 
    deriving (Show, Eq, Ord) 

class Flatten a b | a -> b where 
    flatten :: a -> b 

instance Flatten a a where 
    flatten = id 

instance Flatten a b => Flatten (() :* a) b where 
    flatten (() :* y) = flatten y 

instance Flatten b c => Flatten (a :* b) (a :* c) where 
    flatten (x :* y) = x :* flatten y 


test :: Int :*() 
test = flatten $ 0 :*() 

---

[1 of 1] Compiling Main    (Test\Test.hs, interpreted) 

Test\Test.hs:26:8: 
    Overlapping instances for Flatten (Int :*()) (Int :*()) 
     arising from a use of `flatten' 
    Matching instances: 
     instance [overlap ok] Flatten a a 
     -- Defined at Test\Test.hs:15:10-20 
     instance [overlap ok] Flatten b c => Flatten (a :* b) (a :* c) 
     -- Defined at Test\Test.hs:21:10-49 
    In the expression: flatten 
    In the expression: flatten $ 0 :*() 
    In an equation for `test': test = flatten $ 0 :*() 
Failed, modules loaded: none. 

Цель:

flatten (0:*():*1:*2:3:*():*():*4:*()) == (0:*1:*2:*3:*4:*()) 

Answer 1

Хорошо, прежде всего: Причина компилятор жалуется на fundeps конфликтующие является ... потому что они do конфликт. В этом нет никакого пути, как такового - конфликт присущ тому, что вы пытаетесь сделать. Первым параметром типа является «ввод», и вы, по сути, сопоставляете его с шаблонами для определенных типов, с перекрытием, предоставляя стандартные случаи падения. Но второй параметр типа «output» должен варьироваться в зависимости от «ввода» способами, которые различаются между конкретными и стандартными случаями, таким образом, конфликтом.

Чтобы обойти эту проблему, вам нужно использовать немного хитрости эксплуатирующей тот факт, что GHC рассматривает только головку экземпляра при выборе экземпляра, а затем проверяет контекст позже применить дополнительные ограничения. Основной трюк заключается в том, чтобы оставить «выходной» тип полностью неуказанным, так что выбор экземпляра проверяет только первый параметр и считает, что второй идентичен для всех экземпляров, а что-то вскользь в контекст, который объединяет второй параметр с нужным " вывода "после факта.

Самый простой способ использовать эту технику в текущих версиях GHC - это позволить семействам типов также получить функцию ограничения ограничений . Вот пример:

instance (() ~ r) => Flatten (() :*()) r where 
    flatten _ =() 

instance (Flatten a r) => Flatten (() :* a) r where 
    flatten (_ :* rest) = flatten rest 

instance (a ~ r) => Flatten (a :*()) r where 
    flatten (x :* _) = x 

instance ((a :* c) ~ r, Flatten b c) => Flatten (a :* b) r where 
    flatten (x :* rest) = (x :* flatten rest) 

instance (a ~ r) => Flatten a r where 
    flatten x = x 

Чтобы проиллюстрировать картину, я сделал каждый экземпляр использовать этот трюк, даже если он не является абсолютно необходимым. Мы можем определить необходимый вход:

test = (0 :*() :* 1 :* 2 :* 3 :*() :*() :*4 :*()) 

, а затем в GHCi:

∀x. x ⊢ flatten test 
0 :* (1 :* (2 :* (3 :* 4))) 

Теперь, вы можете быть удивлены, почему я определил test вне GHCi. К сожалению, приведенные выше экземпляры будут еще сбой при применении к полиморфному типу ввода и загрузка его из файла приводит к ограничению мономорфизма и типу по умолчанию, чтобы превратить все числовые литералы в Integer. Тем не менее, очень мало того, что можно сделать с такой неоднозначностью, поскольку параметр типа, который может соответствовать нескольким входам, действительно, неоднозначен.

---

В исторической справке, вы можете сделать то же трюк без ~, используя только fundeps и странные причуды GHC. Некоторая версия этого требуется для большого количества смешного типа хакерства, а оригинал был (неудивительно) изобретен Олегом, идя мимо слегка вводящего в заблуждение имени TypeCast и использовался для реализации предиката равенства TypeEq, который лежит в основе таких вещей, как HList.