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 []  = [[]]