튜플을 평평하게하는 중복 인스턴스

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가 충돌에 대해 컴파일러가 불평 이유는 컴파일러는 프로그램을 거부합니다 ... 왜냐하면 그들은 을 수행하기 때문에이 충돌합니다. 그와 같은 주변에는 실제로 갈 길이 없습니다 - 갈등은 당신이하려는 일에 내재되어 있습니다. 첫 번째 유형 매개 변수는 "입력"이며, 특정 유형에 대해서는 본질적으로 패턴 매칭입니다. 중복 된 기본 추락 사례가 있습니다. 그러나 두 번째 "출력"유형 매개 변수는 특정 경우와 기본 경우 사이에 다른 방식으로 "입력"에 따라 달라야하므로 충돌이 발생합니다.

당신은 인스턴스를 선택할 때 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 

내가 모든 인스턴스가이 트릭을 사용했습니다 패턴을 설명하기 위해 예를 들면 다음과 같습니다이다. GHCi에서 다음

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

그리고, : 우리는 당신이 원하는 입력을 정의 할 수 있습니다

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

을 지금, 나는이 GHCi의 test 외부에서 정의 된 이유가 궁금 할 것이다. 불행히도 다형 적 입력 유형에 적용하면 여전히이 실패하고 파일에서 해당 입력을로드하면 단조 제한이 발생하고 기본값을 입력하면 모든 숫자 상수가 Integer이됩니다. 그러나 이러한 모호성에 대해서는 할 수있는 일이별로 없습니다. 왜냐하면 여러 입력과 일치 할 수있는 유형 매개 변수가 실제로 모호하기 때문입니다.

---

는 역사적 참고로, 당신은 단지 fundeps 및 GHC의 이상한 버릇을 사용하여, ~없이 같은 트릭을 할 수 있습니다. 이것의 일부 버전은 우스꽝스러운 유형의 해커가 많이 필요한 경우에 필요하며 오리지널은 오렐 (Oleg)에 의해 다소 오도 된 이름 TypeCast으로 만들어졌으며 HList와 같은 것들의 기초가되는 동등 조건부 TypeEq을 구현하는 데 사용되었습니다.