하스켈의 다변량 함수

Question

this article on writing polyvariadic functions in Haskell을 읽은 후, 나는 내 자신의 것을 쓰려고 시도했다.

처음에는 일반화하려고 시도 했으므로 주어진 인수를 축소하여 가변 함수를 반환하는 함수를 가질 수있었습니다. 그러나

{-# OPTIONS -fglasgow-exts #-} 
module Collapse where 
class Collapse a r | r -> a where 
    collapse :: (a -> a -> a) -> a -> r 
instance Collapse a a where 
    collapse _ = id 
instance (Collapse a r) => Collapse a (a -> r) where 
    collapse f a a' = collapse f (f a a') 

, 컴파일러가 마음에 들지 않았다

Collapse.hs:5:9: 
    Functional dependencies conflict between instance declarations: 
     instance Collapse a a -- Defined at Collapse.hs:5:9-20 
     instance (Collapse a r) => Collapse a (a -> r) 
     -- Defined at Collapse.hs:7:9-43 

내가 다시 가서 최종 결과에 대한 래퍼 형식을 추가 한 경우, 그러나, 일 :

module Collapse where 
class Collapse a r | r -> a where 
    collapse :: (a -> a -> a) -> a -> r 
data C a = C a 
instance Collapse a (C a) where 
    collapse _ = C . id 
instance (Collapse a r) => Collapse a (a -> r) where 
    collapse f a a' = collapse f (f a a') 
sum :: (Num a, Collapse a r) => a -> r 
sum = collapse (+) 

이 변경 작업을 마치면 컴파일 된 것이므로 ghci에 collapse 함수를 사용할 수 있습니다.

ghci> let C s = Collapse.sum 1 2 3 in s 
6 

최종 결과에 래퍼 유형이 필요한 이유가 확실하지 않습니다. 누구든지 그것을 설명 할 수 있다면, 나는 그것을 높이 평가할 것이다. 필자는 컴파일러가 함수 종속성에 문제가 있음을 알았지 만 아직 펀드를 제대로 사용하지는 못했습니다.

나중에 다른 태도를 취하고 목록을 취하여 값을 반환하는 함수에 대해 가변 인수 생성기를 정의하려고했습니다. 나는 같은 컨테이너 속임수를 써야했고 또한 UndecidableInstances을 허용해야했다. 내 생각

ghci> let V l = Variadic.list 1 2 3 in l 
[1,2,3] 
ghci> let vall p = Variadic.foldl (\b a -> b && (p a)) True 
ghci> :t vall 
vall :: (Variadic b Bool r) => (b -> Bool) -> r 
ghci> let V b = vall (>0) 1 2 3 in b 
True 

: 그것은 컴파일하면

Variadic.hs:7:0: 
    Illegal instance declaration for `Variadic a b (V b)' 
     (the Coverage Condition fails for one of the functional dependencies; 
     Use -XUndecidableInstances to permit this) 
    In the instance declaration for `Variadic a b (V b)' 

Variadic.hs:9:0: 
    Illegal instance declaration for `Variadic a b (a -> r)' 
     (the Coverage Condition fails for one of the functional dependencies; 
     Use -XUndecidableInstances to permit this) 
    In the instance declaration for `Variadic a b (a -> r)' 

그러나, 나는 성공적으로 ghci에서 그것을 사용할 수 있습니다

{-# OPTIONS -fglasgow-exts #-} 
{-# LANGUAGE UndecidableInstances #-} 
module Variadic where 
class Variadic a b r | r -> a, r -> b where 
    variadic :: ([a] -> b) -> r 
data V a = V a 
instance Variadic a b (V b) where 
    variadic f = V $ f [] 
instance (Variadic a b r) => Variadic a b (a -> r) where 
    variadic f a = variadic (f . (a:)) 
list :: Variadic a [a] r => r 
list = variadic . id 
foldl :: (Variadic b a r) => (a -> b -> a) -> a -> r 
foldl f a = variadic (Prelude.foldl f a) 

UndecidableInstances을 허용하지 않고 컴파일러는 내 인스턴스 선언은 불법이라고 불평 내가 찾고있는 이유는 왜 최종 값을위한 컨테이너 유형이 필요한지에 대한 설명뿐 아니라 모든 다양한 functio 최종 종속성이 필요합니다..

또한,이 이상한 듯 :

ghci> let vsum = Variadic.foldl (+) 0 

<interactive>:1:10: 
    Ambiguous type variables `a', `r' in the constraint: 
     `Variadic a a r' 
     arising from a use of `Variadic.foldl' at <interactive>:1:10-29 
    Probable fix: add a type signature that fixes these type variable(s) 

<interactive>:1:10: 
    Ambiguous type variable `a'in the constraint: 
     `Num a' arising from the literal `0' at <interactive>:1:29 
    Probable fix: add a type signature that fixes these type variable(s) 
ghci> let vsum' = Variadic.foldl (+) 
ghci> :t vsum' 
(Num a, Variadic a a r) => t -> a -> r 
ghci> :t vsum' 0 
(Num a, Variadic a a r) => a -> r 
ghci> let V s = vsum' 0 1 2 3 in s 
6 

내가 UndecidableInstances을 허용에서 그 다툼 같은데요,하지만 나도 몰라, 내가 더 무슨 일이 일어나고 있는지 이해하고 싶습니다.

Answer 1

함수 종속 뒤에 아이디어는

class Collapse a r | r -> a where 
    ... 

같은 선언에 r -> a 비트 a 고유 r에 의해 결정되는 것을 말한다는 것이다. 따라서 instance Collapse (a -> r) (a -> r) 및 instance Collapse a (a -> r)을 가질 수 없습니다. 전체 그림은 에서 instance Collapse (a -> r) (a -> r)입니다.

즉, 코드는 instance Collapse t t (유형 변수의 이름은 물론 중요하지 않음) 및 instance Collapse a (a -> r)을 설정하려고합니다. 첫 번째 인스턴스 선언에서 t을 (a -> r)으로 대체하면 instance Collapse (a -> r) (a -> r)이됩니다.이제 이 Collapse의 유일한 인스턴스이며 과 같을 수있는 두 번째 유형 매개 변수는 일 수 있습니다. 클래스 선언은 첫 번째 유형 매개 변수가 두 번째 매개 변수에서 연역 될 것이라고 말하기 때문입니다. 그러나 다음에 instance a (a -> r)을 설정하려고 시도합니다. 그러면 Collapse의 또 다른 인스턴스가 추가되고 두 ​​번째 유형 매개 변수는 (a -> r)입니다. 따라서 GHC는 불평합니다.

Answer 2

Michał Marczyk은 fundeps 및 인스턴스 일치 문제에 대해 절대적으로 정확하며 래퍼 유형은 쉬운 수정처럼 보입니다. 반면에 이미 Oleg 사이트를 읽고 있다면 deeper down the rabbit hole으로 가서 "이 함수가 아닌이 아닌 모든 유형"에 대한 인스턴스를 작성하는 것이 좋습니다.

UndecidableInstances까지는 적용 조건이 here으로 설명됩니다. 귀하의 인스턴스가 왜 실패하는지 분명해야합니다. 여기서 "undecidable"이란 단어는 "Halting Problem undecidable"과 거의 동일한 의미로 결정 불가능한 것을 의미합니다. 즉, GHC가 무한 루프로 보낼 수있는 코드를 무모하게 해결하려고 시도하고 있다고 말하고있는 것입니다 괜찮다는 당신의 주장에만 근거합니다. 깔끔한 아이디어를 해킹하는 것은 재미 있지만 GHC의 첫 번째 패스 유형 검사기로 동의하는 것은 개인적으로 지친 것입니다. 이 방법에

{-# LANGUAGE FlexibleContexts #-} 
{-# LANGUAGE FlexibleInstances #-} 
{-# LANGUAGE MultiParamTypeClasses #-} 
{-# LANGUAGE FunctionalDependencies #-} 

class Variadic a b r | r -> a where 
    variadic :: ([a] -> b) -> r 

instance Variadic a b (a -> b) where 
    variadic f x = f [x] 

instance (Variadic a b (a -> r)) => Variadic a b (a -> a -> r) where 
    variadic f x y = variadic (f . (x:)) y 

vList :: (Variadic a [a] r) => r 
vList = variadic id 

vFoldl :: (Variadic b a r) => (a -> b -> a) -> a -> r 
vFoldl f z = variadic (foldl f z) 

vConcat :: (Variadic [a] [a] r) => r 
vConcat = vFoldl (++) [] 

main = do 
    putStrLn $ vConcat "abc" "def" "ghi" "jkl" 
    putStrLn $ vList 'x' 'y' 'z' 
    if vFoldl (&&) True True True True then putStrLn "Yes" else putStrLn "No" 
    if vFoldl (&&) True True False True then putStrLn "Yes" else putStrLn "No" 

단점 :

Answer 3

여전히이 실험을하는 경우, 여기에 래퍼 형 또는 결정 불가능한 경우 중 하나를 필요로하지 않고, 목록을 복용 함수에서 polyvariadic 기능을 구성의 예 형식 검사기가 결과 유형을 추론 할 수 있어야하며 (또는 주석을 달아야 함) 다형성 숫자 상수에 잘못 적용됩니다. 두 문제에 대한 이유는 언급 한 기사에서 논의됩니다. 도움이 될지 모르겠지만 이전에 다변량 함수를 수정하고이 질문을 기억했습니다.