list - 在 Haskell 中对列表进行三角化

Question

我有兴趣编写一个高效的 Haskell 函数 triangularize :: [a] -> [[a]]这需要一个(可能是无限的)列表并将其“三角化”为列表列表。例如，triangularize [1..19]应该返回

[[1,  3,  6,  10, 15]
,[2,  5,  9,  14]
,[4,  8,  13, 19]
,[7,  12, 18]
,[11, 17]
,[16]]

高效，我的意思是我希望它在 O(n) 中运行时间n是列表的长度。

请注意，这在 Python 这样的语言中很容易做到，因为追加到列表(数组)的末尾是一个恒定时间操作。完成此任务的一个非常必要的 Python 函数是:

def triangularize(elements):
    row_index = 0
    column_index = 0
    diagonal_array = []
    for a in elements:
        if row_index == len(diagonal_array):
            diagonal_array.append([a])
        else:
            diagonal_array[row_index].append(a)
        if row_index == 0:
            (row_index, column_index) = (column_index + 1, 0)
        else:
            row_index -= 1
            column_index += 1
    return diagonal_array

这是因为我一直在使用 Haskell 在 On-Line Encyclopedia of Integer Sequences 中编写一些“表格”序列。 (OEIS)，并且我希望能够以这种方式将普通(一维)序列转换为(二维)序列序列。

也许有一些聪明(或不那么聪明)的方法来 foldr在输入列表中，但我无法对其进行排序。

Answer 1

制作越来越大的 block :

chunks :: [a] -> [[a]]
chunks = go 0 where
    go n [] = []
    go n as = b : go (n+1) e where (b,e) = splitAt n as

然后只需转置两次:

diagonalize :: [a] -> [[a]]
diagonalize = transpose . transpose . chunks

在 ghci 中尝试:

> diagonalize [1..19]
[[1,3,6,10,15],[2,5,9,14],[4,8,13,19],[7,12,18],[11,17],[16]]