목록의 목록으로 유형을 확인하십시오

Question

저는 하스켈 프로가 아닙니다. 오늘 저는 타입 시스템에 대해 다소 기괴한 경험을했습니다. 이 두 번째 줄은 형식 오류를 발생시킵니다.

그것은 다음과 같은 오류와 함께 실패

maxdiag ((a:as):(b:bs):(c:cs):(d:ds):xs) len = 
    maximum [a*(bs !! 0)*(cs !! 1)*(ds !! 2), maxdiag (as:bs:cs:ds) (len-1)] 

이 : 나는 maxdiag (as:bs:cs:ds:xs)에 두 번째 줄의 잘못된 부분을 변경하는 경우

Occurs check: cannot construct the infinite type: a0 = [a0] 
Expected type: [[a0]] 
    Actual type: [a0] 
In the second argument of `(:)', namely `ds' 
In the second argument of `(:)', namely `cs : ds' 

그것이

을 읽을 수 있도록 문제는 두 번째 줄의 maxdiag (as:bs:cs:ds) 비트가

maxdiag ((a:as):(b:bs):(c:cs):(d:ds):xs) len = 
    maximum [a*(bs !! 0)*(cs !! 1)*(ds !! 2), maxdiag (as:bs:cs:ds:xs) (len-1)] 

... 오류가 없습니다. 마찬가지로, maxdiag (as:bs:cs:(ds:xs))으로 바꾸면 성공합니다. 제 질문은

1. 이 오류는 무엇을 의미합니까?
2. 왜 발생 했습니까?
3. 왜이 두 가지 외형 적으로 다른 점이 수정 되었습니까?

Answer 1

기억하는 것은 첫 번째 인자는 요소가 있으므로 두 번째 인수는 그 요소 유형리스트 중에 (:)는, a -> [a] -> [a] 유형을 갖는다는 것이다. 요소 자체가 목록이면 [a] -> [[a]] -> [[a]]이됩니다. xs이 [[a]] 입력 가지고있는 동안 당신의 예에서

는 as, bs, cs 및 ds 모두 ds:xs가 잘 입력하는 동안 너무 cs:ds 오류이며, 입력 [a] 있습니다.

특정 오류 메시지에 대한 이유는 동일한 유형 b의 두 가지에 (:)를 사용하려고하면 b가 [b]와 동일한 유형이 있다면, 일하는 것이 유일한 방법이라고하지만, 그 무한한 것 허용되지 않는 유형.

다른 문의 사항은 (:) 연산자가 오른쪽 연관이므로 as:bs:cs:ds:xs은 as:(bs:(cs:(ds:xs)))과 같으며 as:bs:cs:(ds:xs)과 동일합니다.

Answer 2

오류 :

A.hs:2:63: 
    Occurs check: cannot construct the infinite type: a0 = [a0] 
    Expected type: [[a0]] 
     Actual type: [a0] 
    In the second argument of `(:)', namely `ds' 
    In the second argument of `(:)', namely `cs : ds' 

당신이 불법 유형에 재귀 적 제약을 의미합니다. 나는. 귀하의 유형 a은 a과 [a]이어야합니다.

"occurs check"은이 시점에서 실행중인 the type checking algorithm 부분의 기술 이름입니다. "발생 확인"은 무한 재귀 유형의 생성을 방지합니다.

필자의 경험에 따르면 목록 오류와 함께 발생 체크가 실패하면 (:)과 (++)이 혼합되어 있음을 의미합니다. 즉, 때때로 값을 목록 요소로 사용하고 때로는 목록 자체로 사용합니다.

이 경우 as:bs:cs:ds에 (:)을 사용합니다. 아마 당신은 같은 의미 : 당신의 코드가 꽤 복잡하다

[as,bs,cs,ds]++xs 

주 -이 항상 사실 매우 가능성이 목록에있는 요소의 수와 형태에 대한 가정을 많이합니다. 나는이 코드를 매우 두려워 할 것입니다.

• 사용 패턴은 패턴 매칭과 인덱싱 (!)를 대체 할 다른 경우 (예를 들어 빈 목록, 누락 된 요소)
• 을 배제하기 위해 일치 : 그것은 훨씬 더 안전 할 것입니다.

어떻게 알고리즘을 단순화 할 수 있는지 생각해보십시오.