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

Question

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

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

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

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

РЕДАКТИРОВАТЬ: На самом деле более любопытный запрос, чем домашняя работа,здесь не преподают функциональное программирование в технических университетах (я думаю, это жалко), но я оставлю тег.

Answer 1

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

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

Answer 2

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

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) раз. (В качестве бонуса он также работает с прямоугольными матрицами и не зависит от базы индексации.)

Answer 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]