Каков наилучший способ извлечь диагональ из матрицы в Haskell?

Мне было предложено написать функцию, которая будет извлекать диагональ матрицы, хранящейся в виде списка списков. Первая версия заключалась в том, чтобы извлечь число, индексируя списки, но вскоре я пришел к выводу, что это не хороший алгоритм для Haskell и написал еще одну функцию:

getDiagonal :: (Num a) => [[a]] -> [a]
getDiagonal [[]]       = []
getDiagonal (xs:[])    = [head xs]
getDiagonal (x:xs)     = head x : getDiagonal (map tail xs)

Поскольку я только начал изучать Haskell, я не уверен, написано ли это идиоматическим способом или если он будет работать хорошо.

Итак, мой вопрос заключается в том, есть ли лучший способ извлечь диагональ из матрицы, хранящейся в таком представлении, или если нет лучшего алгоритма, который можно было бы построить, если бы матрица была представлена с использованием более высоких порядков Haskell, например алгебраических типов? Также существует ли разница в производительности между деконструкцией списка в сопоставлении с образцом (так: (x: _): xs) или с функцией головы, как показано выше?

EDIT: На самом деле больше любопытных запросов, чем домашнее задание, они не учат функциональному программированию в технических университетах здесь (что я думаю, я думаю), но я оставлю тег.

Ответы

Ответ 1

Вы можете упростить свое первоначальное определение:

mainDiagonal :: [[a]] -> [a]
mainDiagonal []     = []
mainDiagonal (x:xs) = head x : getDiagonal (map tail xs)

Нет ничего плохого в использовании индексации для этого, что позволяет упростить его:

mainDiagonal xs = zipWith (!!) xs [0..]

Представление на основе массива

Вы также можете представлять матрицы, используя Data.Array, индексированные (i,j). Это позволяет использовать математическое определение основной диагонали почти дословно:

import Data.Array

mainDiagonal :: (Ix i) => Array (i, i) e -> [e]
mainDiagonal xs = [ e | ((i,j),e) <- assocs xs, i == j ]

Вы можете использовать это как:

-- n×n matrix helper
matrix n = listArray ((0,0),(n-1,n-1))

> mainDiagonal $ matrix 3 [1..]
[1,5,9]

Эффективность

Предыдущее определение mainDiagonal по-прежнему неэффективно: для этого все еще нужны тесты O (N²) i == j. Аналогично версии zipWith ее можно фиксировать и обобщать следующим образом:

mainDiagonal xs = (xs !) `map` zip [n..n'] [m..m']
                      where ((n,m),(n',m')) = bounds xs

Эта версия только индексирует массив O (N) раз. (В качестве бонуса он также работает с прямоугольными матрицами и не зависит от базы индексирования.)

Ответ 2

Я думаю, что использование индексации в порядке, если вы можете предположить, что аргумент является квадратной матрицей. В любом случае диагональ с этим представлением будет O (N ²), так как вам нужно пройти по спискам.

diag x = zipWith (!!) x [0..]

Ответ 3

sdcwc ответил на исходный вопрос. Я хотел бы отметить, что представление матрицы в виде списка списков обычно неэффективно. Списки хороши там, где длина неизвестна, матрицы обычно имеют фиксированный размер. Вы можете использовать плоский ассоциативный список или карту для построения матрицы и все, что имеет постоянное время доступа к элементу, когда вы фактически выполняете вычисления с помощью этой матрицы. Data.Array - хороший выбор (см. ответ Пита).

Если вы запускаете численные вычисления в Haskell, вы можете использовать пакет hmatrix. Он имеет собственный тип данных матрицы, Data.Packed.Matrix, и он имеет функцию takeDiag для извлечения диагонали.

Пример Data.Packed.Matrix

Например, если m является вашей матрицей

ghci> let m = (3><3) [1..]
ghci> :t m
m :: Matrix Double
ghci> m
(3><3)
 [ 1.0, 2.0, 3.0
 , 4.0, 5.0, 6.0
 , 7.0, 8.0, 9.0 ]

то вы можете извлечь его диагональ следующим образом:

ghci> takeDiag m
3 |> [1.0,5.0,9.0]