하스켈 :`지도 (a, b) c` 대`지도 a (지도 b c)`?

Question

지도를 유한 함수의 표현으로 생각하면 둘 이상의 변수의지도를 카레 또는 곱슬 곱슬 한 형식으로 지정할 수 있습니다. 즉, Map (a,b) c 및 Map a (Map b c) 유형은 동형이거나 그와 비슷한 것입니다.

효율성과 관련하여 두 가지 표현 중에서 선택하는 데있어 실제적인 고려 사항은 무엇입니까?

Answer 1

터플의 인스턴스 인 Ord은 사전 식 순서를 사용하므로 은 먼저 a으로 정렬되므로 전체 순서가 동일합니다. 실제적인 고려에 대해서 :

• Data.Map는 키에서 이진 검색 트리 분할은 그래서보다 훨씬 더 많은 비용이되지 않습니다 a를 uncurried 형태로 a 주어진에 대한 서브맵을 받고, 조회에 비교할 수 있기 때문에 카레 양식.

• 카레로이드 형식은 하나가 아닌 여러 개의 트리가있는 명백한 이유 때문에 전반적으로 덜 균형 잡힌 트리를 생성 할 수 있습니다.

• 카레 된 양식에는 중첩 된 맵을 저장하는 데 약간의 추가 오버 헤드가 있습니다.

• 일부 a 값이 동일한 결과를 생성하는 경우 "부분 응용 프로그램"을 나타내는 카레 드 양식의 중첩 된지도를 공유 할 수 있습니다.

• 마찬가지로 카레 상태의 "부분 적용"은 기존의 내부 맵을 제공하지만 uncurried 양식은 새로운 맵을 생성해야합니다.

는 그래서 uncurried 형태는 일반적으로 명확하게 더 나은,하지만 당신은 종종 "일부 응용 프로그램"을 할 것으로 기대하고 Map b c 값의 공유에서 도움이 될 경우 카레 형태는 더 좋을 수 있습니다.

실제로 잠재 고객이 이되도록주의를 기울여야합니다. 전체 내부 맵을 명시 적으로 정의하고 전체 맵을 생성 할 때 단일 값을 재사용해야합니다.

편집 : Tikhon Jelvis는 설명에서 생각하지 못했던 튜플 생성자의 메모리 오버 헤드가 거의 무시할 수 없다고 지적합니다. 카레트 폼에는 약간의 오버 헤드가 있지만 오버 헤드는 얼마나 많은 수의 고유 한 숫자가 있는지에 비례합니다. 반면, 터무니없는 형태의 튜플 생성자 오버 헤드는 총 키 수에 비례합니다.

따라서 평균 값이 a 인 경우 3 개 이상의 고유 키가있을 경우 카레 버전을 사용하여 메모리를 절약 할 수 있습니다. 불균형 한 나무에 대한 우려는 물론 적용됩니다. 더 생각하면할수록 키가 매우 드물고 불규칙적으로 분포되어있는 경우를 제외하고는 카레가 된 형태가 분명히 더 나은 것으로 의심됩니다.정의의 인수에 대응이 GHC에 문제 않기 때문에 당신이 하위 표현식 공유하고자 할 경우 함수를 정의 할 때, 같은주의가 필요하다는

는

---

참고; 이것은 당신이 때때로이 같은 스타일로 정의 함수를 볼 이유 중 하나입니다 :

foo x = go 
    where z = expensiveComputation x 
     go y = doStuff y z 

Answer 2

튜플이 두 요소에 게으른, 그래서 튜플 버전은 약간의 여분의 게으름을 소개합니다. 이것이 좋은 것인지 나쁜지는 강하게 다릅니다. (특히, 비교는 터플 요소를 강제 할 수 있지만 중복 값이 ​​많은 경우에만)

그 이상으로, 얼마나 많은 중복이 있느냐에 달려 있다고 생각합니다. b 일 때마다 a이 거의 항상 다른 경우 작은 나무가 많이 생겨 터플 버전이 더 좋을 수 있습니다. 반대의 경우, 비 튜플 버전을 사용하면 약간의 시간을 절약 할 수 있습니다 (a은 적절한 하위 트리를 찾았 으면 b을 계속 찾고 있습니다).

나는 일반적인 접두사를 한 번 저장하는 방법과 시도에 대해 상기시켜줍니다. non-tuple 버전은 그런 것처럼 보입니다. 공통 접두사가 많으면 트라이가 BST보다 더 효율적일 수 있습니다.

하지만 결론은 입니다. ;-)

Answer 3

효율성 측면 외에도이 질문에 대한 실용적인 측면도 있습니다.이 구조로 무엇을하고 싶습니까?

예를 들어 주어진 값이 a 인 빈지도를 저장하고 싶습니까? 만약 그렇다면, 그때 잔인하지 않은 버전이 더 실용적일지도 모릅니다!

다음은 간단한 예입니다. String의 평가 된 속성을 저장하려고한다고 가정 해 봅시다 - 해당 사용자의 stackoverflow 프로필 페이지의 일부 필드 값을 말합니다. 카레 버전으로

type Person = String 
type Property = String 

uncurriedMap :: Map Person (Map Property String) 
uncurriedMap = fromList [ 
        ("yatima2975", fromList [("location","Utrecht"),("age","37")]), 
        ("PLL", fromList []) ] 
curriedMap :: Map (Person,Property) String 
curriedMap = fromList [ 
       (("yatima2975","location"), "Utrecht"), 
       (("yatima2975","age"), "37") ] 

는이 사용자 "PLL"가 시스템에 알려진 사실을 기록 할 좋은 방법은 없지만, 어떤 정보를 작성하지 않았습니다. 사람/속성 쌍 ("PLL",undefined)은 Map이 키에 엄격하기 때문에 런타임 충돌을 일으킬 수 있습니다.

당신은 Map (Person,Property) (Maybe String)에 curriedMap의 유형을 변경하고 거기에 Nothing의 저장, 그것은 아주 잘 이 경우 가장 좋은 해결책이 될 수 있었다; 그러나 어려움을 겪을 수있는 알려지지 않은/다양한 수의 속성 (예 : 사람의 종류에 따라 다름)이있는 곳.

그래서, 나는 또한이 같은 쿼리 기능을 필요 여부에 따라 달라집니다 추측이 쓰기 어려운 (불가능하지는 않더라도)에 카레 버전,하지만 uncurried 버전에서 쉽게

data QueryResult = PersonUnknown | PropertyUnknownForPerson | Value String 
query :: Person -> Property -> Map (Person, Property) String -> QueryResult 

.