Haskell리스트의 중첩 된 직교 좌표계

Question

길이의 목록을 제공 할 수있는 방법을 만들고 싶습니다. 그리고 그 길이까지 직교 좌표의 모든 조합을 반환합니다. 예제로 설명하기가 더 쉽습니다.

cart [2,5] 
Prelude> [ [0,0],[0,1],[0,2],[0,3],[0,4],[1,0],[1,1],[1,2],[1,3],[1,4] ] 

cart [2,2,2] 
Prelude> [ [0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1] ] 

목록이 얼마나 오래 지속될 지 모르기 때문에 간단한 목록 이해가 작동하지 않습니다. Haskell이 많은 문제에 대해 단순함을 좋아하는 동안, 이것은 Haskell이 나에게 동맥류를 제공하는 반면 5 분 안에 절차 적으로 (C 또는 무언가로) 작성할 수있는 것입니다!

이 특정 문제에 대한 해결책은 많은 도움이 될 것입니다. 나는 또한 이와 같은 문제를 다룰 때 당신의 생각 과정에 대해 듣고 싶다.

Answer 1

이것은 재귀 적으로 해결할 수 있습니다. 첫째, Cartesian product of nothing는 {∅}입니다 :

cart [] = [[]] 

(또는 빈 제품이 유효하지 않은 경우 단지 한 요소 양식을 정의

cart [x] = [[i] | i <- [0 .. x-1]] 

)의 다음

, 데카르트의 제품 x:xs은 다음과 같이 쓸 수 있습니다.

cart (x:xs) = [i:rest | i <- [0 .. x-1], rest <- cart xs] 

---

당신이 f를 함수 무엇을 작성하는 경우 일반적으로

는 N, 작은 목록을 예에 따라 F (N)를 만들 수있는 방법을 생각하려고 목록의 길이를 요구하는 f (N - 1) 경우에만 기본 케이스 f (0) 또는 f (1) 등을 푸십시오. 그러면 문제를 쉽게 해결할 수있는 재귀로 변환 할 수 있습니다.

Answer 2

귀하의 절차 적 해결책에는 재귀가 포함됩니다. 하스켈의 솔루션에는 재귀도 포함됩니다.

그래서 재귀. 먼저 재귀 적 사례. 여기

cart (c : cs) = [i : r | i <- [0 .. c-1], r <- rcart] 
    where rcart = cart cs 

우리는 단지 각각의 가능한 초기 좌표, 나머지 길이에서 직교 좌표의 가능한 조합 각각에 대해, 우리는 남아와 합동 조합의 명백한 일을 말을하는지 좌표.

그 다음 기본 케이스.

cart [] = [[]] 

아마도 cart [] = [] 일 수 있습니다. 나는 처음에했다. 재귀 케이스가 기본 케이스에서 요구하는 것에 대해 생각해보십시오.

Answer 3

음 ..

cart = sequence . map (enumFromTo 0 . subtract 1) 

그것은 [[a]] -> [[a]] 기능은 우리가 이미 라이브러리에있는 무엇을 기대하고 기대하는 것이 합리적이다. 따라서 sequence에 익숙하지 않은 사용자는 hoogling이라는 간단한 문제입니다.newacct는 지적 :

편집은

cart = mapM (enumFromTo 0 . subtract 1) 

이것은 또한 HLint에 이전 솔루션을 공급하여 찾을 수 있습니다.