Triangularizando uma lista em Haskell

Estou interessado em escrever uma função Haskell eficiente triangularize :: [a] -> [[a]]que pega uma lista (talvez infinita) e a "triangulariza" em uma lista de listas. Por exemplo, triangularize [1..19]deve retornar

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

Por eficiente, quero dizer que quero que ele seja executado no O(n)tempo em que nestá o comprimento da lista.

Observe que isso é bastante fácil de fazer em uma linguagem como Python, porque anexar ao final de uma lista (matriz) é uma operação de tempo constante. Uma função Python muito imperativa que realiza isso é:

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

Isso ocorreu porque eu tenho usado Haskell para escrever algumas seqüências "tabl" na Enciclopédia On-line de Sequências Inteiras (OEIS) e quero poder transformar uma sequência comum (unidimensional) em uma (2- dimensional) sequência de seqüências exatamente dessa maneira.

Talvez exista uma maneira inteligente (ou não tão inteligente) de foldrultrapassar a lista de entradas, mas não consegui resolver isso.

Faça pedaços de tamanho crescente:

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

Transponha apenas duas vezes:

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

Experimente em ghci:

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

Isso parece estar diretamente relacionado ao argumento da teoria dos conjuntos, provando que o conjunto de pares inteiros está em correspondência um-para-um com o conjunto de números inteiros ( denumerável ). O argumento envolve a chamada função de emparelhamento Cantor .

Então, por curiosidade, vamos ver se conseguimos uma diagonalizefunção dessa maneira. Defina a lista infinita de pares Cantor recursivamente em Haskell:

auxCantorPairList :: (Integer, Integer) -> [(Integer, Integer)]
auxCantorPairList (x,y) =
    let nextPair = if (x > 0) then (x-1,y+1) else (x+y+1, 0)
    in (x,y) : auxCantorPairList nextPair

cantorPairList :: [(Integer, Integer)]
cantorPairList = auxCantorPairList (0,0)

E tente isso dentro do ghci:

 λ> take 15 cantorPairList
[(0,0),(1,0),(0,1),(2,0),(1,1),(0,2),(3,0),(2,1),(1,2),(0,3),(4,0),(3,1),(2,2),(1,3),(0,4)]
 λ> 

Podemos numerar os pares e, por exemplo, extrair os números dos pares que possuem uma coordenada zero x:

 λ> 
 λ> xs = [1..]
 λ> take 5 $ map fst $ filter (\(n,(x,y)) -> (x==0)) $ zip xs cantorPairList
[1,3,6,10,15]
 λ> 

Reconhecemos que esta é a linha superior do resultado do OP no texto da pergunta. Da mesma forma, para as próximas duas linhas:

 λ> 
 λ> makeRow xs row = map fst $ filter (\(n,(x,y)) -> (x==row)) $ zip xs cantorPairList
 λ> take 5 $ makeRow xs 1
[2,5,9,14,20]
 λ> 
 λ> take 5 $ makeRow xs 2
[4,8,13,19,26]
 λ> 

A partir daí, podemos escrever nosso primeiro rascunho de uma diagonalizefunção:

 λ> 
 λ> printAsLines xs = mapM_ (putStrLn . show) xs
 λ> diagonalize xs = takeWhile (not . null) $ map (makeRow xs) [0..]
 λ> 
 λ> printAsLines $ diagonalize [1..19]
[1,3,6,10,15]
[2,5,9,14]
[4,8,13,19]
[7,12,18]
[11,17]
[16]
 λ> 

EDIT: atualização de desempenho

Para uma lista de 1 milhão de itens, o tempo de execução é de 18 segundos e 145 segundos para 4 milhões de itens. Como mencionado por Redu, isso parece com a complexidade de O (n√n).

Distribuir os pares entre as várias sublistas de destino é ineficiente, pois a maioria das operações de filtro falha.

Para melhorar o desempenho, podemos usar uma estrutura Data.Map para as sublistas de destino.

{-#  LANGUAGE  ExplicitForAll       #-}
{-#  LANGUAGE  ScopedTypeVariables  #-}

import qualified  Data.List  as  L
import qualified  Data.Map   as  M

type MIL a = M.Map Integer [a]

buildCantorMap :: forall a.  [a] -> MIL a
buildCantorMap xs = 
    let   ts     =  zip xs cantorPairList -- triplets (a,(x,y))
          m0     = (M.fromList [])::MIL a
          redOp m (n,(x,y)) = let  afn as = case as of
                                              Nothing  -> Just [n]
                                              Just jas -> Just (n:jas)
                              in   M.alter afn x m
          m1r = L.foldl' redOp m0 ts
    in
          fmap reverse m1r

diagonalize :: [a] -> [[a]]
diagonalize xs = let  cm = buildCantorMap xs
                 in   map snd $ M.toAscList cm

Com essa segunda versão, o desempenho parece ser muito melhor: 568 ms para a lista de 1 milhão de itens, 2669 ms para a lista de 4 milhões de itens. Portanto, é próximo à complexidade O (n * Log (n)) que poderíamos esperar.

Pode ser uma boa ideia criar um combfiltro.

Então, o que o combfiltro faz ..? É como splitAtmas em vez de divisão em um único índice que tipo de zips a determinada lista infinita com o pente dado para separar os itens coressponding para Truee Falseno pente. De tal modo que;

comb :: [Bool]  -- yields [True,False,True,False,False,True,False,False,False,True...]
comb = iterate (False:) [True] >>= id

combWith :: [Bool] -> [a] -> ([a],[a])
combWith _ []          = ([],[])
combWith (c:cs) (x:xs) = let (f,s) = combWith cs xs
                         in if c then (x:f,s) else (f,x:s)

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

Agora, tudo o que precisamos fazer é pentear nossa lista infinita, pegar fsta primeira linha e continuar penteando snda mesma comb.

Vamos fazer isso;

diags :: [a] -> [[a]]
diags [] = []
diags xs = let (h,t) = combWith comb xs
           in h : diags t

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

também parece ser preguiçoso também :)

λ> take 5 . map (take 5) $ diags [1..]
[ [1,3,6,10,15]
, [2,5,9,14,20]
, [4,8,13,19,26]
, [7,12,18,25,33]
, [11,17,24,32,41]
]

Eu acho que a complexidade pode ser como O (n√n), mas não posso ter certeza. Alguma ideia..?