Por que as listas de contras estão associadas à programação funcional?

22

Percebi que a maioria das linguagens funcionais emprega uma lista vinculada individual (uma lista de "contras") como seus tipos de lista mais fundamentais. Exemplos incluem Common Lisp, Haskell e F #. Isso é diferente dos idiomas principais, onde os tipos de lista nativos são matrizes.

Por que é que?

Para o Common Lisp (sendo digitado dinamicamente), tenho a ideia de que os contras são gerais o suficiente para também serem a base de listas, árvores etc. Isso pode ser uma pequena razão.

Para linguagens de tipo estaticamente, no entanto, não consigo encontrar um bom raciocínio, posso até encontrar contra-argumentos:

  • O estilo funcional incentiva a imutabilidade; portanto, a facilidade de inserção da lista vinculada é menos uma vantagem,
  • O estilo funcional incentiva a imutabilidade, assim como o compartilhamento de dados; é mais fácil compartilhar "parcialmente" que uma lista vinculada,
  • Você também pode fazer a correspondência de padrões em uma matriz regular e ainda melhor (você pode facilmente dobrar da direita para a esquerda, por exemplo),
  • Além disso, você obtém acesso aleatório gratuitamente,
  • E (uma vantagem prática) se o idioma for digitado estaticamente, você poderá empregar um layout de memória regular e obter um aumento de velocidade no cache.

Então, por que preferir listas vinculadas?

programming-languages functional-programming list linked-list Kos
fonte
4
Vindo dos comentários na resposta de @ sepp2k, acho que an array is easier to share "partially" than a linked listprecisa de esclarecimentos sobre o que você quer dizer. Devido à sua natureza recursiva, o oposto é verdadeiro como eu o entendo - você pode compartilhar parcialmente uma lista vinculada mais facilmente passando qualquer nó nela, enquanto uma matriz precisaria gastar tempo fazendo uma nova cópia. Ou em termos de compartilhamento de dados, duas listas vinculadas podem apontar para o mesmo sufixo, o que simplesmente não é possível com matrizes.
Izkata 29/01
Se uma matriz se definir como um buffer de offset, comprimento e triplo, você poderá compartilhar uma matriz criando um novo com buffer de offset + 1, length-1. Ou tenha um tipo especial de matriz como subarray.
Dobes Vandermeer
@ Izkata Quando falamos de matrizes, raramente queremos dizer um buffer, como um ponteiro para o início da memória contígua em C. Normalmente, queremos dizer algum tipo de estrutura que armazena o comprimento e um ponteiro no início de um buffer agrupado. Sob esse sistema, uma operação de fatiamento pode retornar uma sub-matriz, cujo ponteiro de buffer aponta no meio do buffer (no primeiro elemento da sub-matriz) e cuja contagem é tal que a contagem de start + fornece o último elemento. Tais operações de corte são O (1) no tempo e no espaço
Alexander - Restabeleça Monica

Respostas:

22

O fator mais importante é que você pode anexar uma lista vinculada imutável individualmente em O (1), o que permite criar recursivamente listas de elementos n em O (n), desta maneira:

// Build a list containing the numbers 1 to n:
foo(0) = []
foo(n) = cons(n, foo(n-1))

Se você fizesse isso usando matrizes imutáveis, o tempo de execução seria quadrático, pois cada consoperação precisaria copiar toda a matriz, levando a um tempo de execução quadrático.

O estilo funcional incentiva a imutabilidade, assim como o compartilhamento de dados; é mais fácil compartilhar uma matriz "parcialmente" do que uma lista vinculada

Eu suponho que, compartilhando "parcialmente", você quer dizer que pode pegar um subarray de uma matriz no tempo O (1), enquanto que nas listas vinculadas você pode pegar o rabo no tempo O (1) e todo o resto precisa de O (n). Isso é verdade.

No entanto, levar o rabo é suficiente em muitos casos. E você deve levar em conta que ser capaz de criar sub-matrizes de maneira barata não ajuda se você não tiver como criar matrizes de maneira barata. E (sem otimizações inteligentes do compilador), não há como criar uma matriz barata passo a passo.

sepp2k
fonte
Isso definitivamente não é verdade. Você pode anexar às matrizes em O (1) amortizado.
DeadMG
10
@DeadMG Sim, mas não para matrizes imutáveis .
precisa saber é
"compartilhamento parcial" - acho que as duas listas de contras podem apontar para a mesma lista de sufixos (não sei por que você desejaria isso) e que você pode passar um ponto médio em vez do início da lista para outra função sem precisar copiar (eu fiz isso muitas vezes)
Izkata
@ Izkata O OP estava falando sobre compartilhar parcialmente matrizes, não listas. Também nunca ouvi falar do que você está descrevendo como compartilhamento parcial . Isso é apenas compartilhar.
sepp2k
1
@ Izkata O OP usa o termo "matriz" exatamente três vezes. Uma vez dizer que os idiomas FP usam listas vinculadas onde outros idiomas usam matrizes. Uma vez para dizer que as matrizes são melhores no compartilhamento parcial do que as listas vinculadas e uma vez para dizer que as matrizes podem ter o mesmo padrão de correspondência (como listas vinculadas). Em todos os casos, ele contrasta matrizes e listas vinculadas (para mostrar que matrizes seriam mais úteis como uma estrutura de dados primária do que listas vinculadas, levando à sua pergunta por que as listas vinculadas são preferidas no FP), então não vejo como ele poderia estar usando os termos de forma intercambiável.
precisa saber é
4

Eu acho que tudo se resume a listas sendo facilmente implementadas em código funcional.

Esquema:

(define (cons x y)(lambda (m) (m x y)))

Haskell:

data  [a]  =  [] | a : [a]

Matrizes são mais difíceis e não são tão bonitas de implementar. Se você quiser que eles sejam extremamente rápidos, eles terão que ser escritos em baixo nível.

Além disso, a recursão funciona muito melhor em listas do que em matrizes. Considere o número de vezes que você consumiu / gerou recursivamente uma lista e indexou uma matriz.

Pubby
fonte
Eu não diria que é preciso chamar a versão do seu esquema de implementação de listas vinculadas. Você não poderá usá-lo para armazenar nada além de funções. Além disso, as matrizes são mais difíceis (na verdade, impossíveis) de implementar em qualquer idioma que não possua suporte interno para elas (ou blocos de memória), enquanto as listas vinculadas exigem apenas algo como estruturas, classes, registros ou tipos de dados algébricos para implementar. Isso não é específico para linguagens de programação funcionais.
sepp2k
@ sepp2k O que você quer dizer com "armazenar nada além de funções" ?
Pubby
1
O que eu quis dizer foi que as listas definidas dessa maneira não podem armazenar nada que não seja uma função. Isso não é verdade, no entanto. Não sei, por que eu pensei isso. Me desculpe por isso.
sepp2k
2

Uma lista vinculada individualmente é a estrutura de dados persistente mais simples .

Estruturas de dados persistentes são essenciais para uma programação puramente funcional e de alto desempenho.

ziggystar
fonte
1
este parece meramente ponto repeat feito e explicado no topo resposta que foi publicado mais de 4 anos atrás
mosquito
3
@gnat: A resposta principal não menciona estruturas de dados persistentes, ou que as listas vinculadas individualmente são a estrutura de dados persistentes mais simples ou que são essenciais para o desempenho de uma programação puramente funcional. Não encontro nenhuma sobreposição com a resposta principal.
Michael Shaw
2

Você pode usar nós Contras facilmente apenas se tiver um idioma coletado pelo lixo.

Contras Os nós correspondem muito ao estilo de programação funcional de chamadas recursivas e valores imutáveis. Portanto, ele se encaixa bem no modelo do programador mental.

E não se esqueça de razões históricas. Por que eles ainda são chamados Nós de Contras e, pior ainda, usam carro e cdr como acessadores? As pessoas aprendem isso com livros e cursos e depois o usam.

Você está certo, no mundo real, as matrizes são muito mais fáceis de usar, consomem apenas metade do espaço de memória e têm muito desempenho devido a falhas no nível do cache. Não há razão para usá-los com linguagens imperativas.

Lothar
fonte
1

As listas vinculadas são importantes pelo seguinte motivo:

Depois de pegar um número como 3 e convertê-lo para a sequência sucessora como succ(succ(succ(zero)))e, em seguida, use a substituição com {succ=List node with some memory space}e{zero = end of list} você terminará com uma lista vinculada (de tamanho 3).

A parte importante é números, substituição e espaço na memória e zero.

tp1
fonte