Linguagens de ordem aplicável não suportam gravações de matriz de tempo constante? Se não, por que não?

Estou lendo o "The Algorithm Design Manual", de Steven Skiena, e em uma de suas histórias de guerra na página 155, ele afirma:

A eficiência é um grande desafio no Mathematica, devido ao seu modelo aplicacional de computação (não suporta operações de gravação em tempo constante para matrizes) e a sobrecarga de interpretação (em oposição à compilação).

Já li o SICP, por isso estou familiarizado com a diferença entre as linguagens de ordem normal e de aplicativo (ou seja, que as linguagens de ordem normal atrasam a avaliação dos argumentos do procedimento até que sejam necessárias, enquanto as linguagens de ordem do aplicativo as avaliam assim que o procedimento é chamado). Mas a frase de Skiena acima parece vincular a idéia de linguagens de ordem aplicativa à idéia de gravações em matriz com tempo pior que constante. Não me lembro de Abelson e Sussman mencionando isso em seu texto, então isso foi uma surpresa.

Se verdadeiro, quais são as razões subjacentes às quais as linguagens de ordem do aplicativo não gravam em matrizes em tempo constante? Por que a ordem da avaliação importa na determinação do tempo de gravação da matriz?

Também estou curioso para saber qual é o desempenho de gravação do Big-O nesse caso, mas imagino que isso depende da implementação da linguagem, então vou pular essa pergunta, a menos que haja uma resposta definitiva.

Skiena não disse " ordem de aplicação ", apenas "aplicação". Isso às vezes é usado como significando algo como "puramente funcional" ou uma linguagem que é avaliada por meio da aplicação de funções em oposição à execução de comandos de manipulação de estado. O Mathematica (pelo menos hoje em dia) não é puramente funcional, mas parece que incentiva fortemente um estilo de programação puramente funcional.

Em uma linguagem puramente funcional, como Haskell, você aplica funções a valores e produz novos valores, assim como na matemática. Como a matemática, nessa linguagem, variáveis ​​são apenas nomes de valores. Se você disser "seja seja ", e serão intercambiáveis ​​em todos os lugares. Não faz mais sentido falar em "mutar" para ser do que dizer definir como . Para matriz, isso significa que, para "atualizar" uma matriz, você cria uma nova matriz com as alterações. Obviamente, construir uma cópia inteira de uma matriz, exceto a única entrada que você está alterando, é caro. Este é quase certamente o assunto a que Skiena se refere.$x$$1$$x$$1$$x$$2$$1$$2$

Que eu saiba, não existe uma resposta totalmente satisfatória para isso. Ou seja, não existe uma estrutura de dados puramente funcional que forneça pesquisa de tempo constante e atualizações para todas as versões . Você pode criar estruturas de dados puras (externamente) que fornecem pesquisa e atualização constantes para os últimosversões, mas o acesso a versões mais antigas da matriz se torna mais lento. Você pode usar mônadas ou tipos de exclusividade para impor o uso de matrizes que permitem que o compilador use atualizações no local, mas isso equivale a usar uma abordagem imperativa (embora de maneira controlada e contida). Na prática, programadores em linguagens puramente funcionais simplesmente não usam matrizes tanto quanto programadores imperativos e, quando usam matrizes, tendem a usar operações em massa. Se você deseja tocar em todos os elementos de uma matriz de qualquer maneira, o custo de cópia da matriz é constante por elemento.

Embora existam momentos em que as limitações da programação puramente funcional tornam a implementação eficiente não óbvia, na maioria das vezes é apenas uma questão de aplicar técnicas diferentes de design e implementação que são típicas / práticas em linguagens imperativas. A pureza também oferece garantias que tornam muitos projetos, otimizações e, às vezes, tecnologias inteiras práticos. Para a primeira, as estruturas de dados mais puramente funcionais são projetadas para compartilhar o máximo possível. Para o segundo, uma técnica importante para melhorar o desempenho de operações em massa é a fusão, que combina várias operações em massa em uma para evitar intermediários. Por último,