Контроллинг массив заполнить Haskell

Question

Допустим, у меня есть простой рекурсивной функции

Z(i,j) = Sum(Z(i, k), k = 0..j-1) + Sum(Z(k, j), k = 0..i-1) 
Z(0,0) = 1 

Если вы кладете это в таблице, с (0,0) в левом нижнем углу и (I, J) на в верхнем правом углу вы можете видеть, что в целом все ячейки зависят только от каждой из ячеек слева и внизу, а диагонали сверху вниз и внизу справа могут быть вычислены параллельно.

Для языка как C, я мог бы реализовать динамическую заливку программирования, начиная с нижнего левого и работает мой путь вверх по столбцам:

// for Z[n][m] 
for(i = 0; i <= n; i++) { 
for(j = 0; j <= m; j++) { 
    for(k = 0; k < j; k++) { 
    Z[i,j] += Z(i, k) 
    } 
    for(k = 0; k < i; k++) { 
    Z[i,j] += Z(k, j) 
    } 
} 
} 

Если бы я хотел распараллелить это, я мог бы просто собрать индексы диагонали, которые в настоящее время работают, а затем отправляют соответствующую функцию по каждому из индексов.

В Haskell я мог бы сделать что-то вроде:

z = array ((0,0), (10,10)) 
     [((i, j), 1 + (sum (map (\x -> z ! (i, x)) [0..j-1])) + 
       (sum (map (\x -> z ! (x, j)) [0..i-1]))) | i <- [0..10], j <- [0..10]] 

Есть несколько вещей, которые я не люблю об этом. 1: сложнее читать и менее ясно, что происходит. 2: Я не контролирую порядок исполнения. Как узнать, может ли Haskell заполнять массив наиболее эффективным способом? Есть ли способ реализовать это в Haskell, так что он легко читается, и я контролирую вычислительный поток?

Answer 1

От the docs:

array строго по аргументу границ и по индексам списка ассоциаций, но нестрого в значениях.

Таким образом, ваше выражение будет вычислять только те записи, которые вы фактически используете. Ваш z фактически представляет собой таблицу заметок для рекурсивной функции, указанной в верхней части вашего вопроса, и порядок оценки времени выполнения, естественно, контролируется зависимостями данных в вашей работе с кодом. Другими словами, z ! (i, j) будет эффективно вычисляться бесплатно, благодаря лени.

Что касается читаемости вашего кода: я считаю, что ваша функциональная реализация гораздо читабельна, чем ваша процедурная. Код Haskell намного ближе к спецификации, которую вы дали, используя язык программирования maths: в то время как ваш C-код говорит об увеличении индексов и суммировании итогов, в Haskell вы на самом деле говорите о том, чтобы сделать рекурсивные вызовы на z в диапазоне значений и суммирования результатов. Вы можете использовать списки, а не map, чтобы они выглядели еще более похожими на математические обозначения:

z = array ((0,0), (10,10)) 
     [((i, j), 1 + sum [z ! (i, k) | k <- [0..j-1]] 
        + sum [z ! (k, j) | k <- [0..i-1]]) | i <- [0..10], j <- [0..10]]