Por que as listas de diferenças são mais eficientes que a concatenação regular?

No momento, estou trabalhando no livro Learn you a haskell on-line e cheguei a um capítulo em que o autor explica que algumas concatenações de lista podem ser ineficazes: por exemplo,

((((a ++ b) ++ c) ++ d) ++ e) ++ f 

É supostamente ineficiente. A solução que o autor apresenta é usar ‘listas de diferenças’ definidas como

 newtype DiffList a = DiffList {getDiffList :: [a] -> [a] } instance Monoid (DiffList a) where mempty = DiffList (\xs -> [] ++ xs) (DiffList f) `mappend` (DiffList g) = DiffList (\xs -> f (g xs)) 

Eu estou lutando para entender por que o DiffList é mais computacionalmente eficiente do que uma simples concatenação em alguns casos. Alguém poderia me explicar em termos simples porque o exemplo acima é tão ineficiente e de que maneira o DiffList resolve esse problema?

O problema em

 ((((a ++ b) ++ c) ++ d) ++ e) ++ f 

é o aninhamento. As aplicações de (++) são aninhadas, e isso é ruim; aninhamento direito

 a ++ (b ++ (c ++ (d ++ (e ++f)))) 

não seria um problema. Isso é porque (++) é definido como

 [] ++ ys = ys (x:xs) ++ ys = x : (xs ++ ys) 

então, para descobrir qual equação usar, a implementação deve mergulhar na tree de expressão

  (++) / \ (++) f / \ (++) e / \ (++) d / \ (++) c / \ ab 

até descobrir se o operando da esquerda está vazio ou não. Se não estiver vazia, sua cabeça é levada e borbulhada para o topo, mas a cauda do operando esquerdo fica intocada, então quando o próximo elemento da concatenação é exigido, o mesmo procedimento é iniciado novamente.

Quando as concatenações estão aninhadas à direita, o operando à esquerda de (++) está sempre no topo, e a verificação de vazios / subida da cabeça é O (1).

Mas quando as concatenações são aninhadas, n camadas profundas, para alcançar o primeiro elemento, n nós da tree devem ser percorridos, para cada elemento do resultado (vindo da primeira lista, n-1 para aqueles que vêm do segundo etc).

Vamos considerar a = "hello" em

 hi = ((((a ++ b) ++ c) ++ d) ++ e) ++ f 

e queremos avaliar take 5 hi . Então, primeiro, deve ser verificado se

 (((a ++ b) ++ c) ++ d) ++ e 

está vazia. Para isso, deve ser verificado se

 ((a ++ b) ++ c) ++ d 

está vazia. Para isso, deve ser verificado se

 (a ++ b) ++ c 

está vazia. Para isso, deve ser verificado se

 a ++ b 

está vazia. Para isso, deve ser verificado se

 a 

está vazia. Ufa Não é, então podemos nos levantar novamente, montando

 a ++ b = 'h':("ello" ++ b) (a ++ b) ++ c = 'h':(("ello" ++ b) ++ c) ((a ++ b) ++ c) ++ d = 'h':((("ello" ++ b) ++ c) ++ d) (((a ++ b) ++ c) ++ d) ++ e = 'h':(((("ello" ++ b) ++ c) ++ d) ++ e) ((((a ++ b) ++ c) ++ d) ++ e) ++ f = 'h':((((("ello" ++ b) ++ c) ++ d) ++ e) ++ f) 

e para o 'e' , devemos repetir, e para os 'l' s também …

Desenhando uma parte da tree, o borbulhar é assim:

  (++) / \ (++) c / \ 'h':"ello" b 

torna-se primeiro

  (++) / \ (:) c / \ 'h' (++) / \ "ello" b 

e depois

  (:) / \ 'h' (++) / \ (++) c / \ "ello" b 

todo o caminho de volta ao topo. A estrutura da tree que se torna o filho direito do nível superior (:) , finalmente, é exatamente igual à estrutura da tree original, a menos que a lista mais à esquerda esteja vazia, quando a

  (++) / \ [] b 

nós é recolhido para apenas b .

Portanto, se você tiver concatenações aninhadas à esquerda de listas curtas, a concatenação se tornará quadrática, porque obter a cabeça da concatenação é uma operação O (aninhamento de profundidade). Em geral, a concatenação de um aninhamento esquerdo

 (...((a_d ++ a_{d-1}) ++ a_{d-2}) ...) ++ a_2) ++ a_1 

é O(sum [i * length a_i | i < - [1 .. d]]) para avaliar completamente.

Com listas de diferenças (sem o wrapper newtype para simplicidade de exposição), não é importante se as composições são aninhadas à esquerda

 ((((a ++) . (b ++)) . (c ++)) . (d ++)) . (e ++) 

ou nesteds à direita. Depois de ter percorrido o aninhamento para alcançar o (a ++) , esse (++) é içado para o topo da tree de expressão, de modo que obter em cada elemento de a é novamente O (1).

Na verdade, toda a composição é associada a listas de diferenças, assim que você precisar do primeiro elemento,

 ((((a ++) . (b ++)) . (c ++)) . (d ++)) . (e ++) $ f 

torna-se

 ((((a ++) . (b ++)) . (c ++)) . (d ++)) $ (e ++) f (((a ++) . (b ++)) . (c ++)) $ (d ++) ((e ++) f) ((a ++) . (b ++)) $ (c ++) ((d ++) ((e ++) f)) (a ++) $ (b ++) ((c ++) ((d ++) ((e ++) f))) a ++ (b ++ (c ++ (d ++ (e ++ f)))) 

e depois disso, cada lista é o operando esquerdo imediato do nível superior (++) após a lista anterior ter sido consumida.

O importante é que a function prepending (a ++) pode começar a produzir seu resultado sem inspecionar seu argumento, de modo que a reassociação de

  ($) / \ (.) f / \ (.) (e ++) / \ (.) (d ++) / \ (.) (c ++) / \ (a ++) (b ++) 

através da

  ($)--------- / \ (.) ($) / \ / \ (.) (d ++) (e ++) f / \ (.) (c ++) / \ (a ++) (b ++) 

para

  ($) / \ (a ++) ($) / \ (b ++) ($) / \ (c ++) ($) / \ (d ++) ($) / \ (e ++) f 

não precisa saber nada sobre as funções compostas da lista final f , então é apenas uma reescrita de O(depth) . Então o nível superior

  ($) / \ (a ++) stuff 

torna-se

  (++) / \ a stuff 

e todos os elementos de a podem ser obtidos em um passo. Neste exemplo, onde tivemos aninhamento esquerdo puro, apenas uma reescrita é necessária. Se, em vez de (por exemplo) (d ++) a function naquele local fosse uma composição aninhada à esquerda, (((g ++) . (h ++)) . (i ++)) . (j ++) (((g ++) . (h ++)) . (i ++)) . (j ++) , a reassociação de nível superior deixaria isso intocado e isso seria reassociado quando se tornasse o operando esquerdo do nível superior ($) após todas as listas anteriores terem sido consumidas.

O trabalho total necessário para todas as reassociações é O(number of lists) , portanto, o custo geral da concatenação é O(number of lists + sum (map length lists)) . (Isso significa que você pode trazer um desempenho ruim para isso também, inserindo muito profundamente nested à esquerda ([] ++) .)

o

 newtype DiffList a = DiffList {getDiffList :: [a] -> [a] } instance Monoid (DiffList a) where mempty = DiffList (\xs -> [] ++ xs) (DiffList f) `mappend` (DiffList g) = DiffList (\xs -> f (g xs)) 

apenas envolve isso para que seja mais conveniente manipular abstratamente.

 DiffList (a ++) `mappend` DiffList (b ++) ~> DiffList ((a ++) . (b++)) 

Observe que isso é eficiente apenas para funções que não precisam inspecionar seu argumento para começar a produzir saída, se funções arbitrárias forem DiffList em DiffList s, você não tem essas garantias de eficiência. Em particular, acrescentar ( (++ a) , empacotado ou não) pode criar trees aninhadas à esquerda de (++) quando compostas de DiffList direito, assim você pode criar o comportamento de concatenação O(n²) com isto se o construtor DiffList for exposto.

Pode ajudar a olhar para a definição de concatenação:

 [] ++ ys = ys (x:xs) ++ ys = x : (xs ++ ys) 

Como você pode ver, para concatenar duas listas você precisa passar por cima da lista da esquerda e criar uma “cópia” dela, só assim você pode mudar o seu final (isso é porque você não pode mudar diretamente o fim do antigo lista, devido à imutabilidade).

Se você fizer suas concatenações da maneira associativa correta, não haverá problema. Uma vez inserida, uma lista nunca mais precisará ser tocada (observe como a definição de ++ nunca inspeciona a lista à direita), de modo que cada elemento da lista é inserido apenas “uma vez” por um tempo total de O (N).

 --This is O(n) (a ++ (b ++ (c ++ (d ++ (e ++ f))))) 

No entanto, se você fizer a concatenação de uma maneira associativa à esquerda, a lista “atual” terá que ser “demolida” e “reconstruída” “toda vez que você adicionar outro fragment da lista ao final. Cada elemento da lista será iterado quando ele é inserido e sempre que futuros fragments são anexados também! É como o problema que você recebe em C se você ingenuamente chamar strcat várias vezes seguidas.


Quanto às listas de diferenças, o truque é que elas mantêm um “buraco” explícito no final. Quando você converter um DList de volta para uma lista normal, você passa o que você quer estar no buraco e ele estará pronto para ir. As listas normais, por outro lado, sempre conectam o buraco no final com [] então se você quiser alterá-lo (ao concatenar), então você precisa abrir a lista para chegar a esse ponto.

A definição de listas de diferenças com funções pode parecer intimidante no começo, mas na verdade é bem simples. Você pode visualizá-los a partir de um ponto de vista Orientado a Objetos pensando neles como objects opacos “toList” método que recebe a lista que você deve inserir no buraco no final retorna o prefixo interno do DL mais a cauda que foi fornecida. É eficiente porque você só conecta o “buraco” no final depois que você terminar de converter tudo.