Haskell에서 행렬을 확장하는 방법

Question

주어진 행렬을 반환하고 한 행을 추가하려고 시도했습니다. & 열 옆의 행/열에있는 숫자의 합계입니다. 열의 숫자 중 ...

예 : 나는 "배열"을 사용하기 때문에

(1 2 
3 4) 

(1 2 3 
3 4 7 
4 6 10) 

내 첫번째 생각은

> extend1 :: Int -> Array (Int,Int) Int 
> extend1 ((a,b),(c,d)) = n where 
>     n = array ((a,b),(c,d),(n,n)) 

같은 것을했다. 이제는 어떻게 해야할지 모르겠습니다. 괜찮아요, 아니면 완전히 잘못 됐나요?

Answer 1

우선, 당신은 어떻게 haskell 배열과 인터페이스하는지 이해해야합니다. Array 데이터 유형은 Data.Array입니다. 자세한 내용은 해당 모듈의 문서를 참조하십시오.

이러한 모든 기능에서 찾을 수있는 Ix i 제약 조건을 생략했습니다. 이 상황에서 정말로 중요하지 않습니다.

bounds :: Array i e -> (i, i) :이 함수는 배열의 최소 및 최대 인덱스를 반환합니다. 1D 배열의 경우, 이것은 숫자 일뿐입니다. 2D 배열의 경우 왼쪽 위 및 아래 오른쪽 모서리 (행렬의 경우)입니다.

array :: (i, i) -> [(i, e)] -> Array i e :이 함수는 범위에 대한 최소/최대 쌍 및 연관 목록을 만듭니다. 즉, 인덱스에서 값까지의 맵입니다. 귀하의 초기 예제는 다음과 같이 쓸 수 있습니다 array ((0,0),(1,1)) [((0,0),1),((0,1),2),((1,0),3),((1,1),4)]

assocs :: Array i e -> [(i, e)] : 이것은 array의 '반대'입니다. 그래서 arr == array (bounds arr) (assocs arr).

이제 기능 :

extendArray :: Num e => Array (Int, Int) e -> Array (Int, Int) e 
extendArray arr = 
    let 
     arr' = assocs arr 
     ((xMin, yMin), (xMax, yMax)) = bounds arr 
     newCol = [ ((n, yMax + 1) , sum [ v | ((x,_),v) <- arr', x == n]) | n <- [xMin .. xMax]] 
     newRow = [ ((xMax + 1, n) , sum [ v | ((_,y),v) <- arr', y == n]) | n <- [yMin .. yMax]] 
     newCorner = [((xMax + 1, yMax + 1), sum $ map snd arr')] 
     newArr = array ((xMin, yMin), (xMax + 1, yMax + 1)) (arr' ++ newCol ++ newRow ++ newCorner) 

    in newArr 

여기서 무슨 일이 일어나고 있는지 파괴 할 수 있습니다. let 문장의 처음 두 줄은 지금까지는 설명이 필요 없습니다. 세 번째 줄인 newCol은 마술이 일어나는 곳입니다. 목록 작성법을 사용하므로 익숙하지 않은 경우 here을 참조하십시오.

n <- [xMin .. xMax] :이 부분은 가능한 모든 x 값을 가져옵니다.

[ v | ((x,_),v) <- arr', x == n] : 인덱스 arr'의 모든 값에 대해 색인의 x 좌표가 n과 같으므로 그 좌표에서 값을 반환합니다.

((n, yMax + 1) , sum ... 행이 n이고 이전 열 (즉, 행의 오른쪽에 1 열)이 더해진 새 색인을 만듭니다. - 행 n의 모든 값의 합계).

newRow은 같은 방식으로 작동하지만 행과 열은 반대입니다.

newCorner은 행렬의 모든 값을 가져 와서 합계를 계산하고이 값을 새 배열의 적절한 색인에 배치합니다.

newArr은 단순히 모든 단계를 새로운 배열로 결합합니다. 분명히 범위는 각 방향으로 하나씩 커질 것입니다. 새로운 배열의 연관은 우리가 계산 한 새로운 연관뿐만 아니라 모든 이전 연관을 포함하게 될 것입니다. 그래서

:이 구현은 효율적 아니라고

>let x = array ((0,0),(1,1)) [((0,0),1),((0,1),2),((1,0),3),((1,1),4)] 
>x 
array ((0,0),(1,1)) [((0,0),1),((0,1),2),((1,0),3),((1,1),4)] 
>extendArray x 
array ((0,0),(2,2)) [((0,0),1),((0,1),2),((0,2),3),((1,0),3),((1,1),4),((1,2),7),((2,0),4),((2,1),6),((2,2),10)] 

주 (그러나 그것은 간단하다). newRow에서 전체 행렬 xMax - xMin 번 (각 n 값에 대해 한 번)을 탐색합니다. assocs은 항상 같은 순서 (왼쪽에서 오른쪽, 열에서 아래로의 열)로 요소를 반환하므로 arr' 목록을 길이가 각각 yMax - yMin 인 목록으로 분할하는 것이 좋습니다. 이렇게하면 행 목록을 얻을 수 있습니다. 그러나 나는이 최적화를 당신에게 맡길 것입니다.

Answer 2

튜플의 표현을 사용하고 일반성에 대한 많은 눈이없이 다음은 문제 해결 방법입니다. 내가 입력의 패턴과 where 절에 정의에서 모두 발췌 변수 정의를 사용하는 방법

type Square2 a = ((a,a), (a,a)) 
type Square3 a = ((a,a,a), (a,a,a), (a,a,a)) 

extend1 :: Num a => Square2 a -> Square3 a 
extend1 ((a,b), (c,d)) = 
    ((a, b, ab ) 
    , (c, d, cd ) 
    , (ac, bd, abcd)) 

    where 
    ab = a + b 
    cd = c + d 
    ac = a + c 
    bd = b + d 
    abcd = ab + cd 

참고. 또한 완전히 새로운 출력을 구축하면서 입력을 파괴하고 소비하는 방법에 주목하십시오. 요소 중 일부는 재사용되지만 구조 자체는 파괴됩니다. 마지막으로 튜플의 내부에서 상수를 선택하고 Num typeclass로 제약을 받으면 추가로 (+)을 사용할 수 있습니다.

유사한 기능, 일반화 및 Array의를 사용하여 우리가 Array의의 정확한 크기를 알 수있는 능력을 잃었다

extend1A :: Num a => Array (Int,Int) a -> Array (Int, Int) a 

같은 유형이 있지만, 우리의 기능 중 하나 Array 걸리는 것으로 나타났다 것 어떤 크기로 동일한 Num -constrained 유형을 포함하는 다른 Array을 동일하게 색인화하여 반환합니다.

array 함수는 첫 번째 인수로 경계 집합을 취합니다. 우리는 그런 array가 두 번째 인수로 "assocs"의 목록을 취 입력 배열

extend1A ary0 = array bounds1 ... where 
    ((minX, minY), (maxX, maxY)) = bounds ary0 
    (maxX1, maxY1) = (succ maxX, succ maxY) 
    bounds1 = ((minX, minY, (maxX1, maxY1)) 

의 bounds에 따라 사람들을 업데이트해야합니다. 어떤 Array ix a도 "ix 인덱스에서 a"이라는 값을 나열하는 assocs [(ix, a)] 목록과 동등한 것으로 취급 할 수 있습니다 (대략). 이렇게하려면 우리가 이전에 관리 한 ix 유형의 bounds을 알아야합니다.

이전 정보의 정보를 사용하여 배열을 업데이트하려면 이전 배열의 assocs을 수정하여 새로운 정보를 포함시킵니다. 구체적으로는,이 extend1A는 extraInformation 비어 있다면

extend1A ary0 = array bounds1 (priorInformation ++ extraInformation) where 
    priorInformation = assocs ary0 
    extraInformation = ... 
    ((minX, minY), (maxX, maxY)) = bounds ary0 
    (maxX1, maxY1) = (succ maxX, succ maxY) 
    bounds1 = ((minX, minY, (maxX1, maxY1)) 

([]) 같은 비트 다음 extend1A ary 그 범위의 모든 외부 입력 ary 및 undefined의 범위에있는 모든 모든 인덱스에 ary 동일한 것이 보이는 것을 의미한다. 합계 정보를 extraInformation으로 작성해야합니다.우리는 세 가지의 배열을 연장 생각하면

extend1A ary0 = array bounds1 (priorInformation ++ extraInformation) where 
    priorInformation = assocs ary0 
    extraInformation = xExtension ++ yExtension ++ totalExtension 
    xExtension = ... 
    yExtension = ... 
    totalExtension = ... 
    ((minX, minY), (maxX, maxY)) = bounds ary0 
    (maxX1, maxY1) = (succ maxX, succ maxY) 
    bounds1 = ((minX, minY, (maxX1, maxY1)) 

, ab 및 extend1에 cd 의해 표시된 xExtension, extend1에 ac 및 bd 의해 표시된 yExtension 우리가 각을 계산할 수 extend1에 abcd 의해 표시된 totalExtension 부분적으로.

totalExtension이 가장 쉽습니다. 각 (i,a) 쌍의 "값 구성 요소"의 합계가 priorInformation입니다. xExtension 또는 yExtension의 "값 구성 요소"의 합계 일 수도 있지만 가능하면 분명히 정확하기 위해 첫 번째 선택 항목을 선택하여 오른쪽 하단 모서리에 설치합니다. 우리는 반복해서 표시됩니다 sumValues 같은 새로운 기능을 정의 할 where 절을 사용할 수 있습니다

extend1A ary0 = array bounds1 (priorInformation ++ extraInformation) where 
    priorInformation = assocs ary0 
    extraInformation = xExtension ++ yExtension ++ totalExtension 
    sumValues asscs = sum (map snd asscs) 
    xExtension = ... 
    yExtension = ... 
    totalExtension = [((maxX1, maxY1), sumValues priorInformation)] 
    ((minX, minY), (maxX, maxY)) = bounds ary0 
    (maxX1, maxY1) = (succ maxX, succ maxY) 
    bounds1 = ((minX, minY), (maxX1, maxY1)) 

참고.

그러면 우리는 priorInformation을 통해 목록 보급으로 확장을 계산할 수 있습니다. 우리는 오래된 assoc에 대해 특정 종류의 합을 수집해야합니다 --- 하나의 인덱스가 고정되어있는 모든 값을 합산합니다.

xExtension = [((maxX1, yix) 
       , sumValues (filter (\((_, j), _) -> j == yix) priorInformation) 
      ) 
      | yix <- [minY .. maxY] 
      ] 

yExtension = [((xix, maxY1) 
       , sumValues (filter (\((i, _), _) -> i == xix) priorInformation) 
      ) 
      | xix <- [minX .. maxX] 
      ] 

그리고 나서 끝났습니다. 그것은 효율적이지 않지만 모든 조각이 함께 작동합니다.

extend1A ary0 = array bounds1 (priorInformation ++ extraInformation) where 
    priorInformation = assocs ary0 
    extraInformation = xExtension ++ yExtension ++ totalExtension 
    xExtension = [((maxX1, yix) 
       , sumValues (filter (\((_, j), _) -> j == yix) priorInformation) 
       ) 
       | yix <- [minY .. maxY] 
       ] 
    yExtension = [((xix, maxY1) 
       , sumValues (filter (\((i, _), _) -> i == xix) priorInformation) 
       ) 
       | xix <- [minX .. maxX] 
       ] 
    totalExtension = [((maxX1, maxY1), sum xExtension)] 
    ((minX, minY), (maxX, maxY)) = bounds ary0 
    (maxX1, maxY1) = (succ maxX, succ maxY) 
    bounds1 = ((minX, minY), (maxX1, maxY1)) 

Answer 3

사용 hmatrix :

import Numeric.LinearAlgebra 
import Numeric.LinearAlgebra.Util(col,row) 

m = (2><2) [1 , 2 
      ,3 , 4] :: Matrix Double 


extend m = fromBlocks [[m ,sr] 
         ,[sc, s]] 
    where 
    sr = col $ map sumElements (toRows m) 
    sc = row $ map sumElements (toColumns m) 
    s = scalar (sumElements sr) 


main = do 
    print m 
    print $ extend m 


(2><2) 
[ 1.0, 2.0 
, 3.0, 4.0 ] 
(3><3) 
[ 1.0, 2.0, 3.0 
, 3.0, 4.0, 7.0 
, 4.0, 6.0, 10.0 ]