하스켈:"groupBy"의 놀라운 행동

StackOverflow https://stackoverflow.com/questions/1316365

  •  19-09-2019
  •  | 
  •  

문제

첫 번째 인수로 전달된 "동일성 테스트" 함수를 통해 목록의 요소를 그룹화하는 라이브러리 함수 groupBy(Data.List의)의 동작을 파악하려고 합니다.유형 서명은 동일성 테스트에 유형만 있으면 된다는 것을 나타냅니다. 

(a -> a -> Bool)

그러나 GHCi 6.6에서 "동등성 테스트"로 (<)를 사용하면 결과가 예상한 것과 다릅니다.

ghci> groupBy (<) [1, 2, 3, 2, 4, 1, 5, 9]
[[1,2,3,2,4],[1,5,9]]

대신 다음과 같이 숫자가 엄격하게 증가할 것으로 예상합니다.

[[1,2,3],[2,4],[1,5,9]]

내가 무엇을 놓치고 있나요?

도움이 되었습니까?

해결책

살펴보십시오 GHC 구현 그룹비:

groupBy                 :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy _  []           =  []
groupBy eq (x:xs)       =  (x:ys) : groupBy eq zs
                           where (ys,zs) = span (eq x) xs

이제이 두 출력을 비교하십시오.

Prelude List> groupBy (<) [1, 2, 3, 2, 4, 1, 5, 9]
[[1,2,3,2,4],[1,5,9]]
Prelude List> groupBy (<) [8, 2, 3, 2, 4, 1, 5, 9]
[[8],[2,3],[2,4],[1,5,9]]

간단히 말해서, 이것은 다음과 같습니다. groupBy 주어진 함수 (첫 번째 인수)가 평등을 테스트한다고 가정하므로 비교 함수가 반사, 전이 그리고 대칭 (보다 동등성 관계). 여기서 문제는 적은 것보다 관계는 반사적이거나 대칭이 아닙니다.

편집하다: 다음 구현은 전환 만 가정합니다.

groupBy' :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy' _   []                        = []
groupBy' _   [x]                       = [[x]]
groupBy' cmp (x:xs@(x':_)) | cmp x x'  = (x:y):ys
                           | otherwise = [x]:r
  where r@(y:ys) = groupBy' cmp xs

다른 팁

"<"는 동등성 테스트가 아니라는 사실입니다.

다르게 구현하기 때문에 일부 동작을 기대할 수도 있지만 그것이 약속하는 것은 아닙니다.

그것이 출력하는 것이 합리적인 대답인 이유에 대한 예는 그것이 그것을 훑어보는 경우입니다.

[1, 2, 3, 2, 4, 1, 5, 9] ->
[[1,2,3], [2,4], [1,5,9]]

이제 동일한 요소로 구성된 3개의 그룹이 있습니다.따라서 실제로 동일한 것이 있는지 확인합니다.

각 그룹의 모든 요소가 동일하다는 것을 알고 있으므로 각 그룹의 첫 번째 요소인 1, 2, 1만 볼 수 있습니다.

1 > 2?예!따라서 처음 두 그룹을 병합합니다.

1 > 1?아니요!따라서 마지막 그룹은 그대로 유지됩니다.

이제 모든 요소가 동일한지 비교됩니다.

...단지, 예상한 종류의 기능을 전달하지 않았습니다.

즉, 평등 테스트를 원할 때 평등 테스트를 실시하세요..

문제는 참조 구현입니다 groupBy Haskell 보고서에서는 요소를 첫 번째 요소와 비교하므로 그룹이 엄격하게 증가하지 않습니다 (첫 번째 요소보다 더 커야합니다). 당신이 원하는 것은 대신 버전입니다 groupBy 테스트합니다 인접한 구현과 같은 요소 여기.

GroupBy 기능에도 적용되기 전에 귀하의 목록을 정렬해야한다고 지적하고 싶습니다.

예를 들어:

equalityOp :: (a, b1) -> (a, b2) -> Bool
equalityOp x y = fst x == fst y

testData = [(1, 2), (1, 4), (2, 3)]

correctAnswer = groupBy equalityOp testData == [[(1, 2), (1, 4)], [(2, 3)]]

otherTestData = [(1, 2), (2, 3), (1, 4)]

incorrectAnswer = groupBy equalityOp otherTestData == [[(1, 2)], [(2, 3)], [(1, 4)]]

이 동작은 Groupby가 정의에 SPAN을 사용하고 있기 때문에 발생합니다. 특정 순서로 기본 목록을 갖는 우리에게 의존하지 않는 합리적인 행동을 얻으려면 기능을 정의 할 수 있습니다.

groupBy' :: (a -> a -> Bool) -> [a] -> [[a]]
groupBy' eq []     = []
groupBy' eq (x:xs) = (x:similarResults) : (groupBy' eq differentResults)
    where similarResults   = filter (eq x) xs
          differentResults = filter (not . eq x) xs
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top