이 멱집합 생성 함수는 어떻게 동작하는거죠?

Haskell 멱집합 생성 함수 설명, SO 번역

2015년 8월 24일

Elm 강의를 보고 있는데 멱집합을 생성하는 함수가 과제로 나왔다. 한참을 고민하다가 결국 검색을 해보게 되었다. 반성하는 차원에서 How is this powerset generating function working?를 짧게 번역했다. 수학공부 부지런히 해야겠다.


이 멱집합 생성 함수는 어떻게 동작하는거죠?

리스트를 넣어 멱집합을 생성하는 함수를 만들려고 하는데 다음과 같은 코드를 인터넷에서 찾게 되었다. 설명은 없었지만 테스트 해보니 정상적으로 동작했다. 이 함수가 어떻게 동작하는지 이해할 수가 없었다. 설명을 해주면 감사하겠다.

generateSubset [] = [[]]
generateSubset (x:xs) = let p = generateSubset xs in p ++ map (x:) p

Daniel Wagner의 답변

멱집합의 특성으로 쉽게 증명할 수 있다. P(A ∪ B) = {a ∪ b | a ∈ P(A) 또는 b ∈ P(B)}. 특히 집합 S와 그 집합에 포함된 원소인 s로 분해하고 S’의 모든 원소는 s가 아닐 때,

P(S) = P({s} ∪ S')
     = {a ∪ b | a ∈ P({s}), b ∈ P(S')}

여기서 P({s})는 직접 계산하기 좋을 정도로 충분히 작다. P({s}) = {{}, {s}}. 이 사실로 다음과 같이 유도한다.

P(S) = {a ∪ b | a ∈ {{}, {s}}, b ∈ P(S')}
     = {b | b ∈ P(S')} ∪ {{s} ∪ b | b ∈ P(S')}
     = P(S') ∪ {{s} ∪ b | b ∈ P(S')}
     = let p = P(S') in p ∪ {{s} ∪ b | b ∈ p}

이 방법은 멱집합이 빈 원소를 갖는 집합이기 때문에 사용 가능한 계산 방법이다. 먼저 원소를 고른 후, 나머지로 멱집합을 연산한다. 그 후 각각의 부분집합에 추가하거나 더하지 않는다. 질문한 함수는 이 부분을 코드로 전환한 것으로 리스트를 집합으로 사용했다.

-- P         ({s} ∪ S') = let p = P(S')             in p  ∪ {{s} ∪ b | b ∈ p}
generateSubset (x:xs)   = let p = generateSubset xs in p ++     map (x:) p

재귀를 위해 기본값을 넣어주는 일만 남았다. 멱집합의 정의에 따라 다음과 같이 추가한다.

-- P          ({}) = {{}}
generateSubset []  = [[]]