Haskell에있는 2 개 목록의 데카르트 곱

Haskell에있는 2 개 목록의 데카르트 곱

---

Haskell에서 2 개 목록의 Cartesian 곱을 만들고 싶지만 어떻게하는지 알 수 없습니다. 데카르트 곱은 목록 요소의 모든 조합을 제공합니다.

xs = [1,2,3]
ys = [4,5,6]

cartProd :: [a] -> [b] -> [(a,b)]
cartProd xs ys ==> [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]

이것은 실제 숙제 질문이 아니며 그러한 질문과 관련이 없지만이 문제를 해결하는 방법은 내가 붙어있는 문제에 도움이 될 수 있습니다.

---

이것은 목록 이해력으로 매우 쉽습니다. 목록의 직교 제품을 얻으려면 xs그리고 ys, 우리는 단지 튜플를 취할 필요가 (x,y)각 요소 x의 xs각 요소 y에 ys.

이것은 우리에게 다음 목록 이해력을 제공합니다.

cartProd xs ys = [(x,y) | x <- xs, y <- ys]

---

다른 답변에서 언급했듯이 목록 이해를 사용하는 것이 Haskell에서이를 수행하는 가장 자연스러운 방법입니다.

Haskell을 배우고 있고 Monad, 같은 타입 클래스에 대한 직관을 개발하고 싶다면 이 약간 더 짧은 정의가 왜 동등한 지 알아내는 것은 재미있는 연습입니다.

import Control.Monad (liftM2)

cartProd :: [a] -> [b] -> [(a, b)]
cartProd = liftM2 (,)

여러분은 아마 이것을 실제 코드로 작성하고 싶지 않을 것입니다. 그러나 기본적인 아이디어는 Haskell에서 항상 볼 수있는 것입니다. 우리는 liftM2non-monadic 함수 (,)를 모나드로 들어 올리기 위해 사용 하고 있습니다. 목록 모나드.

이것이 의미가 없거나 유용하지 않다면 잊어 버리십시오. 문제를 보는 또 다른 방법 일뿐입니다.

---

입력 목록이 동일한 유형 인 sequence경우 ( List모나드 사용)를 사용 하여 임의 개수의 목록에 대한 데카르트 곱을 얻을 수 있습니다 . 그러면 튜플 목록 대신 목록 목록이 표시됩니다.

> sequence [[1,2,3],[4,5,6]]
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]

---

Applicative Functor로이를 수행하는 매우 우아한 방법이 있습니다.

import Control.Applicative

(,) <$> [1,2,3] <*> [4,5,6]
-- [(1,4),(1,5),(1,6),(2,4),(2,5),(2,6),(3,4),(3,5),(3,6)]

기본 아이디어는 "래핑 된"인수에 함수를 적용하는 것입니다.

(+) <$> (Just 4) <*> (Just 10)
-- Just 14

목록의 경우 함수가 모든 조합에 적용되므로으로 "튜플 링"하기 만하면됩니다 (,).

참조 http://learnyouahaskell.com/functors-applicative-functors-and-monoids#applicative-functors 또는 (자세한 이론) http://www.soi.city.ac.uk/~ross/papers/Applicative.pdf 에 대한 세부.

---

다른 답변은 두 입력 목록이 유한하다고 가정합니다. 흔히 관용적 Haskell 코드에는 무한 목록이 포함되어 있으므로 필요한 경우 무한 데카르트 곱을 생성하는 방법에 대해 간략하게 설명하는 것이 좋습니다.

표준 접근 방식은 대각선 화를 사용하는 것입니다. 상단에 하나의 입력을 쓰고 왼쪽에 다른 입력을 쓰면 다음과 같이 전체 데카르트 곱을 포함하는 2 차원 테이블을 작성할 수 있습니다.

   1  2  3  4 ...
a a1 a2 a3 a4 ...
b b1 b2 b3 b4 ...
c c1 c2 c3 c4 ...
d d1 d2 d3 d4 ...

.  .  .  .  . .
.  .  .  .  .  .
.  .  .  .  .   .

물론 단일 행에서 작업하면 다음 행에 도달하기 전에 무한한 요소가 제공됩니다. 마찬가지로 칼럼 방식으로 진행하면 재앙이 될 것입니다. 그러나 우리는 그리드의 가장자리에 도달 할 때마다 조금 더 오른쪽으로 다시 시작하여 아래쪽과 왼쪽으로가는 대각선을 따라 갈 수 있습니다.

a1

   a2
b1

      a3
   b2
c1

         a4
      b3
   c2
d1

...등등. 순서대로 이것은 우리에게 다음을 제공합니다.

a1 a2 b1 a3 b2 c1 a4 b3 c2 d1 ...

이것을 Haskell에서 코딩하려면 먼저 2 차원 테이블을 생성하는 버전을 작성할 수 있습니다.

cartesian2d :: [a] -> [b] -> [[(a, b)]]
cartesian2d as bs = [[(a, b) | a <- as] | b <- bs]

비효율적 인 대각 화 방법은 먼저 대각선을 따라 반복 한 다음 각 대각선의 깊이를 따라 반복하여 매번 적절한 요소를 꺼내는 것입니다. 설명을 간단하게하기 위해 두 입력 목록이 모두 무한하다고 가정하므로 경계 검사를 엉망으로 만들 필요가 없습니다.

diagonalBad :: [[a]] -> [a]
diagonalBad xs =
    [ xs !! row !! col
    | diagonal <- [0..]
    , depth <- [0..diagonal]
    , let row = depth
          col = diagonal - depth
    ]

이 구현은 약간 안타깝습니다. 반복되는 목록 인덱싱 작업 !!은 갈수록 점점 더 비싸 져서 상당히 나쁜 점근 적 성능을 제공합니다. 보다 효율적인 구현은 위의 아이디어를 취하지 만 지퍼를 사용하여 구현합니다. 따라서 무한 그리드를 다음과 같이 세 가지 모양으로 나눌 것입니다.

a1 a2 / a3 a4 ...
     /
    /
b1 / b2 b3 b4 ...
  /
 /
/
c1 c2 c3 c4 ...
---------------------------------
d1 d2 d3 d4 ...

 .  .  .  . .
 .  .  .  .  .
 .  .  .  .   .

The top left triangle will be the bits we've already emitted; the top right quadrilateral will be rows that have been partially emitted but will still contribute to the result; and the bottom rectangle will be rows that we have not yet started emitting. To begin with, the upper triangle and upper quadrilateral will be empty, and the bottom rectangle will be the entire grid. On each step, we can emit the first element of each row in the upper quadrilateral (essentially moving the slanted line over by one), then add one new row from the bottom rectangle to the upper quadrilateral (essentially moving the horizontal line down by one).

diagonal :: [[a]] -> [a]
diagonal = go [] where
    go upper lower = [h | h:_ <- upper] ++ case lower of
        []         -> concat (transpose upper')
        row:lower' -> go (row:upper') lower'
        where upper' = [t | _:t <- upper]

Although this looks a bit more complicated, it is significantly more efficient. It also handles the bounds checking that we punted on in the simpler version.

But you shouldn't write all this code yourself, of course! Instead, you should use the universe package. In Data.Universe.Helpers, there is (+*+), which packages together the above cartesian2d and diagonal functions to give just the Cartesian product operation:

Data.Universe.Helpers> "abcd" +*+ [1..4]
[('a',1),('a',2),('b',1),('a',3),('b',2),('c',1),('a',4),('b',3),('c',2),('d',1),('b',4),('c',3),('d',2),('c',4),('d',3),('d',4)]

You can also see the diagonals themselves if that structure becomes useful:

Data.Universe.Helpers> mapM_ print . diagonals $ cartesian2d "abcd" [1..4]
[('a',1)]
[('a',2),('b',1)]
[('a',3),('b',2),('c',1)]
[('a',4),('b',3),('c',2),('d',1)]
[('b',4),('c',3),('d',2)]
[('c',4),('d',3)]
[('d',4)]

If you have many lists to product together, iterating (+*+) can unfairly bias certain lists; you can use choices :: [[a]] -> [[a]] for your n-dimensional Cartesian product needs.

---

The right way is using list comprehensions, as other people have already pointed out, but if you wanted to do it without using list comprehensions for any reason, then you could do this:

cartProd :: [a] -> [b] -> [(a,b)]
cartProd xs [] = []
cartProd [] ys = []
cartProd (x:xs) ys = map (\y -> (x,y)) ys ++ cartProd xs ys

---

Yet another way, using the do notation:

cartProd :: [a] -> [b] -> [(a,b)]
cartProd xs ys = do x <- xs
                    y <- ys
                    return (x,y)

---

Yet another way to accomplish this is using applicatives:

import Control.Applicative

cartProd :: [a] -> [b] -> [(a,b)]
cartProd xs ys = (,) <$> xs <*> ys

---

Well, one very easy way to do this would be with list comprehensions:

cartProd :: [a] -> [b] -> [(a, b)]
cartProd xs ys = [(x, y) | x <- xs, y <- ys]

Which I suppose is how I would do this, although I'm not a Haskell expert (by any means).

---

something like:

cartProd x y = [(a,b) | a <- x, b <- y]

---

It's a job for sequenceing. A monadic implementation of it could be:

cartesian :: [[a]] -> [[a]]
cartesian [] = return []
cartesian (x:xs) = x >>= \x' -> cartesian xs >>= \xs' -> return (x':xs')

*Main> cartesian [[1,2,3],[4,5,6]]
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]

As you may notice, the above resembles the implementation of map by pure functions but in monadic type. Accordingly you can simplify it down to

cartesian :: [[a]] -> [[a]]
cartesian = mapM id

*Main> cartesian [[1,2,3],[4,5,6]]
[[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]

---

Here is my implementation of n-ary cartesian product:

crossProduct :: [[a]] -> [[a]]
crossProduct (axis:[]) = [ [v] | v <- axis ]
crossProduct (axis:rest) = [ v:r | v <- axis, r <- crossProduct rest ]

---

Just adding one more way for the enthusiast, using only recursive pattern matching.

cartProd :: [a]->[b]->[(a,b)]
cartProd _ []=[]
cartProd [] _ = []
cartProd (x:xs) (y:ys) = [(x,y)] ++ cartProd [x] ys  ++ cartProd xs ys ++  cartProd xs [y] 

참고URL : https://stackoverflow.com/questions/4119730/cartesian-product-of-2-lists-in-haskell