Por que a avaliação preguiçosa é útil?

119

Há muito tempo me pergunto por que a avaliação preguiçosa é útil. Ainda não tenho ninguém que me explique de uma forma que faça sentido; na maioria das vezes, acaba se resumindo a "confiar em mim".

Nota: não quero dizer memoização.

Joel McCracken
fonte

Respostas:

96

Principalmente porque pode ser mais eficiente - os valores não precisam ser calculados se não forem usados. Por exemplo, posso passar três valores para uma função, mas dependendo da sequência de expressões condicionais, apenas um subconjunto pode realmente ser usado. Em uma linguagem como C, todos os três valores seriam calculados de qualquer maneira; mas em Haskell, apenas os valores necessários são calculados.

Também permite coisas legais como listas infinitas. Não posso ter uma lista infinita em uma linguagem como C, mas em Haskell, isso não é problema. Listas infinitas são usadas com bastante frequência em certas áreas da matemática, portanto, pode ser útil ter a habilidade de manipulá-las.

mipadi
fonte
6
Python avalia lentamente listas infinitas por meio de iteradores
Mark Cidade
4
Na verdade, você pode emular uma lista infinita em Python usando geradores e expressões geradoras (que funcionam de maneira semelhante a uma compreensão de lista): python.org/doc/2.5.2/ref/genexpr.html
John Montgomery
24
Os geradores facilitam as listas preguiçosas no Python, mas outras técnicas de avaliação preguiçosas e estruturas de dados são visivelmente menos elegantes.
Peter Burns
3
Receio não concordar com essa resposta. Eu costumava pensar que preguiça tinha a ver com eficiência, mas tendo usado Haskell uma quantidade substancial e depois mudado para Scala e comparando a experiência, devo dizer que preguiça importa com frequência, mas raramente por causa da eficiência. Acho que Edward Kmett aponta os verdadeiros motivos.
Owen,
3
Eu discordo da mesma forma, embora não haja nenhuma noção explícita de uma lista infinita em C por causa da avaliação estrita, você pode facilmente fazer o mesmo truque em qualquer outra linguagem (e de fato, na maioria das implementações reais de linguagem preguiçosa) usando thunks e passando a função ponteiros para trabalhar com um prefixo finito da estrutura infinita produzida por expressões semelhantes.
Kristopher Micinski
71

Um exemplo útil de avaliação preguiçosa é o uso de quickSort:

quickSort [] = []
quickSort (x:xs) = quickSort (filter (< x) xs) ++ [x] ++ quickSort (filter (>= x) xs)

Se agora queremos encontrar o mínimo da lista, podemos definir

minimum ls = head (quickSort ls)

Que primeiro classifica a lista e, em seguida, obtém o primeiro elemento da lista. No entanto, por causa da avaliação preguiçosa, apenas a cabeça é computada. Por exemplo, se pegarmos o mínimo da lista, [2, 1, 3,]quickSort filtrará primeiro todos os elementos menores que dois. Em seguida, ele faz quickSort sobre isso (retornando a lista de singleton [1]) que já é suficiente. Por causa da avaliação preguiçosa, o resto nunca é classificado, economizando muito tempo computacional.

É claro que este é um exemplo muito simples, mas a preguiça funciona da mesma maneira para programas muito grandes.

No entanto, há uma desvantagem em tudo isso: fica mais difícil prever a velocidade do tempo de execução e o uso de memória de seu programa. Isso não significa que programas preguiçosos sejam mais lentos ou ocupem mais memória, mas é bom saber.

Chris Eidhof
fonte
19
Mais geralmente, take k $ quicksort listleva apenas um tempo O (n + k log k), onde n = length list. Com uma classificação de comparação não preguiçosa, isso sempre levaria O (n log n) tempo.
efemiente
@ephemient você não quer dizer O (nk log k)?
MaiaVictor
1
@Viclib Não, eu quis dizer o que disse.
efêmero
@ephemient então eu acho que não entendi, infelizmente
MaiaVictor
2
@Viclib Um algoritmo de seleção para encontrar os k principais elementos de n é O (n + k log k). Quando você implementa o quicksort em uma linguagem preguiçosa e apenas avalia o suficiente para determinar os primeiros k elementos (parando a avaliação depois), ele faz exatamente as mesmas comparações que um algoritmo de seleção não preguiçoso faria.
efêmero
70

Considero a avaliação preguiçosa útil para várias coisas.

Em primeiro lugar, todas as linguagens preguiçosas existentes são puras, porque é muito difícil raciocinar sobre os efeitos colaterais em uma linguagem preguiçosa.

Linguagens puras permitem raciocinar sobre definições de funções usando raciocínio equacional.

foo x = x + 3

Infelizmente, em uma configuração não preguiçosa, mais instruções falham ao retornar do que em uma configuração preguiçosa, portanto, isso é menos útil em linguagens como ML. Mas em uma linguagem preguiçosa você pode raciocinar com segurança sobre igualdade.

Em segundo lugar, muitas coisas como a 'restrição de valor' em ML não são necessárias em linguagens preguiçosas como Haskell. Isso leva a uma grande organização de sintaxe. Linguagens como ML precisam usar palavras-chave como var ou fun. Em Haskell, essas coisas se resumem a uma única noção.

Terceiro, a preguiça permite que você escreva um código muito funcional que pode ser entendido em partes. Em Haskell, é comum escrever um corpo de função como:

foo x y = if condition1
          then some (complicated set of combinators) (involving bigscaryexpression)
          else if condition2
          then bigscaryexpression
          else Nothing
  where some x y = ...
        bigscaryexpression = ...
        condition1 = ...
        condition2 = ...

Isso permite que você trabalhe 'de cima para baixo' por meio da compreensão do corpo de uma função. As linguagens do tipo ML forçam você a usar um letque é avaliado de forma estrita. Consequentemente, você não ousa 'elevar' a cláusula let para o corpo principal da função, porque se ela for cara (ou tiver efeitos colaterais), você não quer que ela seja sempre avaliada. Haskell pode 'empurrar' os detalhes para a cláusula where explicitamente porque sabe que o conteúdo dessa cláusula só será avaliado conforme necessário.

Na prática, tendemos a usar proteções e reduzi-las para:

foo x y 
  | condition1 = some (complicated set of combinators) (involving bigscaryexpression)
  | condition2 = bigscaryexpression
  | otherwise  = Nothing
  where some x y = ...
        bigscaryexpression = ...
        condition1 = ...
        condition2 = ...

Quarto, às vezes a preguiça oferece uma expressão muito mais elegante de certos algoritmos. Uma 'classificação rápida' preguiçosa em Haskell é uma linha única e tem a vantagem de que, se você olhar apenas os primeiros itens, pagará apenas custos proporcionais ao custo de selecionar apenas esses itens. Nada impede que você faça isso estritamente, mas provavelmente você terá que recodificar o algoritmo a cada vez para obter o mesmo desempenho assintótico.

Quinto, a preguiça permite que você defina novas estruturas de controle na linguagem. Você não pode escrever uma nova construção 'if .. then .. else ..' em uma linguagem estrita. Se você tentar definir uma função como:

if' True x y = x
if' False x y = y

em uma linguagem estrita, ambos os ramos seriam avaliados independentemente do valor da condição. Fica pior quando você considera os loops. Todas as soluções restritas requerem que a linguagem forneça algum tipo de citação ou construção lambda explícita.

Finalmente, nessa mesma linha, alguns dos melhores mecanismos para lidar com os efeitos colaterais no sistema de tipos, como as mônadas, só podem ser expressos efetivamente em um ambiente preguiçoso. Isso pode ser testemunhado comparando a complexidade dos fluxos de trabalho do F # com as mônadas de Haskell. (Você pode definir uma mônada em uma linguagem estrita, mas infelizmente você frequentemente falhará em uma ou duas leis de mônada devido à falta de preguiça e os Fluxos de Trabalho, em comparação, pegam uma tonelada de bagagem estrita.)

Edward KMETT
fonte
5
Muito agradável; essas são as verdadeiras respostas. Eu costumava pensar que se tratava de eficiência (atrasar cálculos para mais tarde) até que usei Haskell em uma quantidade significativa e vi que essa não é a razão de modo algum.
Owen,
11
Além disso, embora não seja tecnicamente verdade que uma linguagem preguiçosa deva ser pura (R como exemplo), é verdade que uma linguagem preguiçosa impura pode fazer coisas muito estranhas (R como exemplo).
Owen,
4
Claro que existe. Em uma linguagem estrita, recursivo leté uma besta perigosa; no esquema R6RS, ele permite que aleatórios #fapareçam em seu termo onde quer que o nó estritamente leve a um ciclo! Sem trocadilhos, mas letligações estritamente mais recursivas são adequadas em uma linguagem preguiçosa. A rigidez também exacerba o fato de quewhere não há como ordenar os efeitos relativos, exceto pelo SCC, é uma construção no nível da instrução, seus efeitos podem acontecer em qualquer ordem estritamente, e mesmo se você tiver uma linguagem pura, acabará com o #fquestão. Estrita whereenigmas seu código com preocupações não-locais.
Edward KMETT
2
Você poderia explicar como a preguiça ajuda a evitar a restrição de valor? Eu não fui capaz de entender isso.
Tom Ellis
3
@PaulBone Do que você está falando? A preguiça tem muito a ver com estruturas de controle. Se você definir sua própria estrutura de controle em uma linguagem estrita, ela terá que usar um monte de lambdas ou algo semelhante, ou será uma merda. Porque ifFunc(True, x, y)vai avaliar tanto xe ao yinvés de apenas x.
ponto
28

Há uma diferença entre a avaliação de ordem normal e a avaliação preguiçosa (como em Haskell).

square x = x * x

Avaliando a seguinte expressão ...

square (square (square 2))

... com avaliação ansiosa:

> square (square (2 * 2))
> square (square 4)
> square (4 * 4)
> square 16
> 16 * 16
> 256

... com avaliação de pedido normal:

> (square (square 2)) * (square (square 2))
> ((square 2) * (square 2)) * (square (square 2))
> ((2 * 2) * (square 2)) * (square (square 2))
> (4 * (square 2)) * (square (square 2))
> (4 * (2 * 2)) * (square (square 2))
> (4 * 4) * (square (square 2))
> 16 * (square (square 2))
> ...
> 256

... com avaliação preguiçosa:

> (square (square 2)) * (square (square 2))
> ((square 2) * (square 2)) * ((square 2) * (square 2))
> ((2 * 2) * (2 * 2)) * ((2 * 2) * (2 * 2))
> (4 * 4) * (4 * 4)
> 16 * 16
> 256

Isso ocorre porque a avaliação preguiçosa olha para a árvore de sintaxe e faz transformações de árvore ...

square (square (square 2))

           ||
           \/

           *
          / \
          \ /
    square (square 2)

           ||
           \/

           *
          / \
          \ /
           *
          / \
          \ /
        square 2

           ||
           \/

           *
          / \
          \ /
           *
          / \
          \ /
           *
          / \
          \ /
           2

... enquanto a avaliação normal de pedidos só faz expansões textuais.

É por isso que, ao usar a avaliação preguiçosa, ficamos mais poderosos (a avaliação termina com mais frequência do que outras estratégias), enquanto o desempenho é equivalente à avaliação ansiosa (pelo menos em notação O).

Thomas Danecker
fonte
25

A avaliação lenta relacionada à CPU da mesma forma que a coleta de lixo relacionada à RAM. O GC permite que você finja que tem uma quantidade ilimitada de memória e, portanto, solicite quantos objetos na memória forem necessários. O tempo de execução recuperará automaticamente os objetos inutilizáveis. O LE permite que você finja que possui recursos computacionais ilimitados - você pode fazer quantos cálculos precisar. O tempo de execução simplesmente não executará cálculos desnecessários (para determinado caso).

Qual é a vantagem prática desses modelos "fingidos"? Ele libera o desenvolvedor (até certo ponto) do gerenciamento de recursos e remove algum código clichê de suas fontes. Mas o mais importante é que você pode reutilizar com eficiência sua solução em um conjunto mais amplo de contextos.

Imagine que você tem uma lista de números S e um número N. Você precisa encontrar o mais próximo do número N número M da lista S. Você pode ter dois contextos: único N e alguma lista L de Ns (ei para cada N em L você procura o M mais próximo em S). Se você usar a avaliação preguiçosa, pode classificar S e aplicar a pesquisa binária para encontrar o M mais próximo de N. Para uma boa classificação preguiçosa, serão necessários O (tamanho (S)) etapas para N único e O (ln (tamanho (S)) * (tamanho (S) + tamanho (L))) etapas para L. igualmente distribuído. Se você não tem uma avaliação preguiçosa para atingir a eficiência ideal, você deve implementar o algoritmo para cada contexto.

Alexey
fonte
A analogia com o GC me ajudou um pouco, mas você pode dar um exemplo de "remove algum código clichê", por favor?
Abdul
1
@Abdul, um exemplo familiar para qualquer usuário ORM: carregamento lento de associação. Ele carrega a associação do banco de dados "na hora certa" e, ao mesmo tempo, libera o desenvolvedor da necessidade de especificar explicitamente quando carregá-lo e como armazená-lo em cache (quero dizer, esse é o padrão). Aqui está outro exemplo: projectlombok.org/features/GetterLazy.html .
Alexey de
25

Se você acredita em Simon Peyton Jones, a avaliação preguiçosa não é importante per se mas apenas como uma 'camisa de cabelo' que forçou os designers a manter a linguagem pura. Acho que simpatizo com esse ponto de vista.

Richard Bird, John Hughes e, em menor grau, Ralf Hinze são capazes de fazer coisas incríveis com avaliação preguiçosa. Ler o trabalho deles o ajudará a apreciá-lo. Um bom ponto de partida é o magnífico solucionador de Sudoku de Bird e o artigo de Hughes sobre Por que a programação funcional é importante .

Norman Ramsey
fonte
Isso não apenas os forçou a manter a linguagem pura, mas também permitiu que eles o fizessem, quando (antes da introdução da IOmônada) a assinatura de mainseria String -> Stringe você já pudesse escrever programas interativos apropriadamente.
esquerda por volta de
@leftaroundabout: O que impede uma linguagem estrita de forçar todos os efeitos em uma IOmônada?
Tom Ellis,
13

Considere um programa tic-tac-toe. Isso tem quatro funções:

  • Uma função de geração de movimento que pega um tabuleiro atual e gera uma lista de novos tabuleiros, cada um com um movimento aplicado.
  • Em seguida, há uma função "mover árvore" que aplica a função de geração de movimento para derivar todas as posições do tabuleiro possíveis que poderiam resultar desta.
  • Existe uma função minimax que percorre a árvore (ou possivelmente apenas parte dela) para encontrar o melhor movimento seguinte.
  • Existe uma função de avaliação do tabuleiro que determina se um dos jogadores ganhou.

Isso cria uma boa e clara separação de interesses. Em particular, a função de geração de movimento e as funções de avaliação do tabuleiro são as únicas que precisam entender as regras do jogo: a árvore de movimento e as funções do minimax são totalmente reutilizáveis.

Agora vamos tentar implementar o xadrez em vez do jogo da velha. Em uma linguagem "ansiosa" (isto é, convencional), isso não funcionará porque a árvore de movimentação não caberá na memória. Portanto, agora as funções de avaliação do tabuleiro e geração de movimentos precisam ser combinadas com a árvore de movimentos e a lógica do minimax, porque a lógica do minimax deve ser usada para decidir quais movimentos gerar. Nossa estrutura modular limpa e agradável desaparece.

No entanto, em uma linguagem preguiçosa, os elementos da árvore de movimentação são gerados apenas em resposta às demandas da função minimax: a árvore de movimentação inteira não precisa ser gerada antes de deixarmos o minimax solto no elemento superior. Portanto, nossa estrutura modular limpa ainda funciona em um jogo real.

Paul Johnson
fonte
1
[Em uma linguagem "ansiosa" (isto é, convencional) isso não funcionará porque a árvore de movimentação não caberá na memória] - para o jogo da velha certamente irá. Existem no máximo 3 ** 9 = 19683 posições para armazenar. Se armazenarmos cada um em extravagantes 50 bytes, isso dá quase um megabyte. Isso não é nada ...
Jonas Kölker
6
Sim, esse é o meu ponto. Linguagens ávidas podem ter uma estrutura limpa para jogos triviais, mas precisam comprometer essa estrutura para qualquer coisa real. Linguagens preguiçosas não têm esse problema.
Paul Johnson
3
Para ser justo, porém, a avaliação preguiçosa pode levar a seus próprios problemas de memória. Não é incomum que as pessoas perguntem por que o haskell está apagando sua memória para algo que, em uma avaliação ansiosa, teria um consumo de memória de O (1)
RHSeeger
@PaulJohnson Se você avalia todas as posições, não faz diferença se você as avalia com entusiasmo ou preguiçoso. O mesmo trabalho deve ser feito. Se você parar no meio e avaliar apenas metade das posições, também não faz diferença, porque em ambos os casos metade do trabalho tem que ser feito. A única diferença entre as duas avaliações é que o algoritmo parece melhor, se escrito preguiçosamente.
ceving
12

Aqui estão mais dois pontos que, creio, ainda não foram levantados na discussão.

  1. A preguiça é um mecanismo de sincronização em um ambiente concorrente. É uma maneira leve e fácil de criar uma referência para alguns cálculos e compartilhar seus resultados entre muitos threads. Se vários threads tentarem acessar um valor não avaliado, apenas um deles irá executá-lo e os outros irão bloquear de acordo, recebendo o valor assim que estiver disponível.

  2. A preguiça é fundamental para amortizar estruturas de dados em um ambiente puro. Isso é descrito por Okasaki em Purely Functional Data Structures em detalhes, mas a ideia básica é que a avaliação preguiçosa é uma forma controlada de mutação crítica para nos permitir implementar certos tipos de estruturas de dados com eficiência. Embora muitas vezes falemos de preguiça nos forçando a usar o hairshirt puro, o outro caminho também se aplica: eles são um par de características de linguagem sinérgica.

Edward Z. Yang
fonte
10

Quando você liga seu computador e o Windows se abstém de abrir todos os diretórios do seu disco rígido no Windows Explorer e evita de iniciar todos os programas instalados no computador, até que você indique que um determinado diretório é necessário ou um determinado programa é necessário, isso é avaliação "preguiçosa".

A avaliação "preguiçosa" está realizando operações quando e conforme são necessárias. É útil quando é um recurso de uma linguagem de programação ou biblioteca porque geralmente é mais difícil implementar uma avaliação preguiçosa por conta própria do que simplesmente calcular tudo antecipadamente.

Yfeldblum
fonte
1
Algumas pessoas podem dizer que isso é realmente "execução preguiçosa". A diferença é realmente imaterial, exceto em linguagens razoavelmente puras como Haskell; mas a diferença é que não é apenas o cálculo atrasado, mas também os efeitos colaterais associados a ele (como abrir e ler arquivos).
Owen,
8

Considere isto:

if (conditionOne && conditionTwo) {
  doSomething();
}

O método doSomething () será executado apenas se conditionOne for verdadeiro e conditionTwo for true. No caso em que conditionOne é falso, por que você precisa calcular o resultado de conditionTwo? A avaliação de conditionTwo será uma perda de tempo neste caso, especialmente se sua condição for o resultado de algum processo de método.

Esse é um exemplo de interesse preguiçoso de avaliação ...

Romain Linsolas
fonte
Achei que era um curto-circuito, não uma avaliação preguiçosa.
Thomas Owens
2
É uma avaliação lenta, pois a condiçãoDoisé calculada apenas se for realmente necessária (ou seja, se a CondiçãoOne for verdadeira).
Romain Linsolas
7
Suponho que o curto-circuito seja um caso degenerado de avaliação preguiçosa, mas definitivamente não é uma maneira comum de pensar sobre isso.
rmeador
19
O curto-circuito é, na verdade, um caso especial de avaliação preguiçosa. A avaliação preguiçosa abrange muito mais do que apenas curto-circuito, obviamente. Ou o que o curto-circuito tem além da avaliação preguiçosa?
yfeldblum
2
@Juliet: Você tem uma definição forte de 'preguiçoso'. Seu exemplo de uma função que recebe dois parâmetros não é o mesmo que uma instrução if de curto-circuito. Uma instrução if de curto-circuito evita cálculos desnecessários. Acho que uma comparação melhor com o seu exemplo seria o operador "andalso" do Visual Basic, que força ambas as condições a serem avaliadas
8
  1. Pode aumentar a eficiência. Este é o que parece óbvio, mas não é realmente o mais importante. (Observe também que a preguiça também pode matar a eficiência - esse fato não é imediatamente óbvio. No entanto, ao armazenar muitos resultados temporários em vez de calculá-los imediatamente, você pode usar uma grande quantidade de RAM.)

  2. Ele permite que você defina construções de controle de fluxo em código normal de nível de usuário, em vez de ser embutido na linguagem. (Por exemplo, Java tem forloops; Haskell tem uma forfunção. Java tem tratamento de exceção; Haskell tem vários tipos de mônada de exceção. C # tem goto; Haskell tem a mônada de continuação ...)

  3. Ele permite que você desacople o algoritmo para gerar dados do algoritmo para decidir quantos dados gerar. Você pode escrever uma função que gere uma lista de resultados nocionalmente infinita e outra função que processe essa lista tanto quanto for necessário. Mais especificamente, você pode ter cinco funções geradoras e cinco funções de consumidor, e pode produzir qualquer combinação com eficiência - em vez de codificar manualmente 5 x 5 = 25 funções que combinam as duas ações ao mesmo tempo. (!) Todos nós sabemos que a dissociação é uma coisa boa.

  4. Ele mais ou menos força você a projetar uma linguagem funcional pura . É sempre tentador pegar atalhos, mas em uma linguagem preguiçosa, a menor impureza torna seu código totalmente imprevisível, o que milita fortemente contra a tomada de atalhos.

Orquídea Matemática
fonte
6

Um grande benefício da preguiça é a capacidade de escrever estruturas de dados imutáveis ​​com limites amortizados razoáveis. Um exemplo simples é uma pilha imutável (usando F #):

type 'a stack =
    | EmptyStack
    | StackNode of 'a * 'a stack

let rec append x y =
    match x with
    | EmptyStack -> y
    | StackNode(hd, tl) -> StackNode(hd, append tl y)

O código é razoável, mas anexar duas pilhas xey leva O (comprimento de x) tempo nos casos melhor, pior e médio. Anexar duas pilhas é uma operação monolítica, ela toca todos os nós na pilha x.

Podemos reescrever a estrutura de dados como uma pilha preguiçosa:

type 'a lazyStack =
    | StackNode of Lazy<'a * 'a lazyStack>
    | EmptyStack

let rec append x y =
    match x with
    | StackNode(item) -> Node(lazy(let hd, tl = item.Force(); hd, append tl y))
    | Empty -> y

lazyfunciona suspendendo a avaliação do código em seu construtor. Uma vez avaliado usando .Force(), o valor de retorno é armazenado em cache e reutilizado em cada.Force() .

Com a versão preguiçosa, appends são uma operação O (1): ele retorna 1 nó e suspende a reconstrução real da lista. Ao obter o cabeçalho desta lista, ele avaliará o conteúdo do nó, forçando-o a retornar o cabeçalho e criar uma suspensão com os elementos restantes, portanto, assumir o cabeçalho da lista é uma operação O (1).

Então, nossa lista preguiçosa está em um estado constante de reconstrução, você não paga o custo para reconstruir esta lista até que você atravesse todos os seus elementos. Usando preguiça, esta lista suporta O (1) consing e appending. Curiosamente, uma vez que não avaliamos os nós até que eles sejam acessados, é totalmente possível construir uma lista com elementos potencialmente infinitos.

A estrutura de dados acima não requer que os nós sejam recalculados em cada travessia, portanto, eles são distintamente diferentes dos IEnumerables tradicionais no .NET.

Julieta
fonte
5

Este snippet mostra a diferença entre avaliação preguiçosa e não preguiçosa. É claro que essa função de fibonacci poderia ser otimizada e usar avaliação preguiçosa em vez de recursão, mas isso estragaria o exemplo.

Vamos supor que PODEMOS ter que usar os 20 primeiros números para alguma coisa, sem avaliação preguiçosa, todos os 20 números devem ser gerados antecipadamente, mas, com avaliação preguiçosa, eles serão gerados apenas conforme necessário. Assim, você pagará apenas o preço de cálculo quando necessário.

Saída de amostra

Geração não preguiçosa: 0,023373
Geração preguiçosa: 0,000009
Saída não lenta: 0,000921
Saída lenta: 0,024205
import time

def now(): return time.time()

def fibonacci(n): #Recursion for fibonacci (not-lazy)
 if n < 2:
  return n
 else:
  return fibonacci(n-1)+fibonacci(n-2)

before1 = now()
notlazy = [fibonacci(x) for x in range(20)]
after1 = now()
before2 = now()
lazy = (fibonacci(x) for x in range(20))
after2 = now()


before3 = now()
for i in notlazy:
  print i
after3 = now()

before4 = now()
for i in lazy:
  print i
after4 = now()

print "Not lazy generation: %f" % (after1-before1)
print "Lazy generation: %f" % (after2-before2)
print "Not lazy output: %f" % (after3-before3)
print "Lazy output: %f" % (after4-before4)
Vinko Vrsalovic
fonte
5

A avaliação lenta é mais útil com estruturas de dados. Você pode definir uma matriz ou vetor, especificando indutivamente apenas alguns pontos na estrutura e expressando todos os outros em termos de toda a matriz. Isso permite gerar estruturas de dados de forma muito concisa e com alto desempenho em tempo de execução.

Para ver isso em ação, você pode dar uma olhada em minha biblioteca de rede neural chamada instinto . Faz uso pesado de avaliação preguiçosa para elegância e alto desempenho. Por exemplo, eu me livro totalmente do cálculo de ativação tradicionalmente imperativo. Uma simples expressão preguiçosa faz tudo por mim.

Isso é usado, por exemplo, no função de ativação e também no algoritmo de aprendizado de retropropagação (só posso postar dois links, então você mesmo precisará procurar a learnPatfunção no AI.Instinct.Train.Deltamódulo). Tradicionalmente, ambos requerem algoritmos iterativos muito mais complicados.

ertes
fonte
4

Outras pessoas já deram todos os grandes motivos, mas acho que um exercício útil para ajudar a entender por que a preguiça é importante é tentar escrever um ponto fixo função de em uma linguagem estrita.

Em Haskell, uma função de ponto fixo é super fácil:

fix f = f (fix f)

isso se expande para

f (f (f ....

mas, como Haskell é preguiçoso, essa cadeia infinita de computação não é problema; a avaliação é feita "de fora para dentro", e tudo funciona perfeitamente:

fact = fix $ \f n -> if n == 0 then 1 else n * f (n-1)

É importante ressaltar que não importa que fixseja preguiçoso, mas que fseja preguiçoso. Uma vez que você já recebeu um estrito f, você pode jogar as mãos para o alto e desistir ou eta expandi-lo e desordenar as coisas. (Isso é muito parecido com o que Noah estava dizendo sobre ser a biblioteca que é estrita / preguiçosa, não a linguagem).

Agora imagine escrever a mesma função em Scala estrito:

def fix[A](f: A => A): A = f(fix(f))

val fact = fix[Int=>Int] { f => n =>
    if (n == 0) 1
    else n*f(n-1)
}

Obviamente, você obtém um estouro de pilha. Se quiser que funcione, você precisa usar o fargumento call-by-need:

def fix[A](f: (=>A) => A): A = f(fix(f))

def fact1(f: =>Int=>Int) = (n: Int) =>
    if (n == 0) 1
    else n*f(n-1)

val fact = fix(fact1)
Owen
fonte
3

Não sei como você pensa sobre as coisas, mas acho útil pensar na avaliação preguiçosa como um problema de biblioteca em vez de um recurso de linguagem.

Quero dizer que em linguagens restritas, posso implementar a avaliação preguiçosa construindo algumas estruturas de dados, e em linguagens preguiçosas (pelo menos Haskell), posso pedir rigor quando eu quiser. Portanto, a escolha do idioma não torna seus programas preguiçosos ou não preguiçosos, mas simplesmente afeta o que você obtém por padrão.

Depois de pensar nisso dessa forma, pense em todos os lugares onde você escreve uma estrutura de dados que você pode usar mais tarde para gerar dados (sem olhar muito antes disso), e você verá muitos usos para preguiçoso avaliação.

Noah Lavine
fonte
1
Implementar a avaliação preguiçosa em linguagens estritas costuma ser um Turing Tarpit.
itsbruce,
2

A exploração mais útil da avaliação preguiçosa que usei foi uma função que chamou uma série de subfunções em uma ordem específica. Se qualquer uma dessas subfunções falhou (retornou falso), a função de chamada precisava retornar imediatamente. Então, eu poderia ter feito desta forma:

bool Function(void) {
  if (!SubFunction1())
    return false;
  if (!SubFunction2())
    return false;
  if (!SubFunction3())
    return false;

(etc)

  return true;
}

ou a solução mais elegante:

bool Function(void) {
  if (!SubFunction1() || !SubFunction2() || !SubFunction3() || (etc) )
    return false;
  return true;
}

Depois de começar a usá-lo, você verá oportunidades para usá-lo com cada vez mais frequência.

Marc Bernier
fonte
2

Sem uma avaliação preguiçosa, você não terá permissão para escrever algo como isto:

  if( obj != null  &&  obj.Value == correctValue )
  {
    // do smth
  }
peeles
fonte
Bem, imo, é uma má ideia fazer isso. Embora esse código possa estar correto (dependendo do que você tenta alcançar), é difícil de ler, o que é sempre ruim.
Brann,
12
Acho que não. É uma construção padrão em C e seus parentes.
Paul Johnson
Este é um exemplo de avaliação de curto-circuito, não avaliação preguiçosa. Ou isso é efetivamente a mesma coisa?
RufusVS
2

Entre outras coisas, as linguagens preguiçosas permitem estruturas de dados infinitas multidimensionais.

Embora o schema, python, etc. permitam estruturas de dados infinitas unidimensionais com fluxos, você só pode atravessar ao longo de uma dimensão.

A preguiça é útil para o mesmo problema marginal , mas vale a pena observar a conexão das corrotinas mencionada naquele link.

shapr
fonte
2

A avaliação preguiçosa é o raciocínio equacional do pobre (que se poderia esperar, idealmente, que deduzisse propriedades de código a partir de propriedades de tipos e operações envolvidas).

Exemplo em que funciona muito bem: sum . take 10 $ [1..10000000000] . Que não nos importamos em ser reduzido a uma soma de 10 números, em vez de apenas um cálculo numérico direto e simples. Sem a avaliação preguiçosa, é claro, isso criaria uma lista gigantesca na memória apenas para usar seus primeiros 10 elementos. Certamente seria muito lento e poderia causar um erro de falta de memória.

Exemplo onde não é tão grande como gostaríamos: sum . take 1000000 . drop 500 $ cycle [1..20]. O que na verdade vai somar os 1 000 000 de números, mesmo que em um loop em vez de em uma lista; ainda assim, deve ser reduzido a apenas um cálculo numérico direto, com poucas condicionais e poucas fórmulas. O que seria muito melhor do que somar os 1 000 000 de números. Mesmo se em um loop, e não em uma lista (ou seja, após a otimização do desmatamento).


Outra coisa é que ele torna possível codificar no estilo contras do módulo de recursão da cauda e simplesmente funciona .

cf. resposta relacionada .

Will Ness
fonte
1

Se por "avaliação preguiçosa" você quer dizer como em booleanos combinados, como em

   if (ConditionA && ConditionB) ... 

então a resposta é simplesmente que quanto menos ciclos de CPU o programa consome, mais rápido ele será executado ... e se um conjunto de instruções de processamento não tiver impacto no resultado do programa, será desnecessário (e, portanto, um desperdício de tempo) para realizá-los de qualquer maneira ...

se otoh, você quer dizer o que eu conheço como "inicializadores lazy", como em:

class Employee
{
    private int supervisorId;
    private Employee supervisor;

    public Employee(int employeeId)
    {
        // code to call database and fetch employee record, and 
        //  populate all private data fields, EXCEPT supervisor
    }
    public Employee Supervisor
    { 
       get 
          { 
              return supervisor?? (supervisor = new Employee(supervisorId)); 
          } 
    }
}

Bem, esta técnica permite o código do cliente usando a classe para evitar a necessidade de chamar o banco de dados para o registro de dados do Supervisor, exceto quando o cliente que usa o objeto Employee requer acesso aos dados do supervisor ... isso torna o processo de instanciar um Employee mais rápido, e ainda quando você precisar do Supervisor, a primeira chamada para a propriedade Supervisor irá acionar a chamada do Banco de Dados e os dados serão buscados e disponibilizados ...

Charles Bretana
fonte
0

Trecho de funções de ordem superior

Vamos encontrar o maior número abaixo de 100.000 divisível por 3829. Para fazer isso, vamos apenas filtrar um conjunto de possibilidades nas quais sabemos que está a solução.

largestDivisible :: (Integral a) => a  
largestDivisible = head (filter p [100000,99999..])  
    where p x = x `mod` 3829 == 0 

Primeiro, fazemos uma lista de todos os números inferiores a 100.000, em ordem decrescente. Em seguida, o filtramos por nosso predicado e, como os números são classificados de maneira decrescente, o maior número que satisfaz nosso predicado é o primeiro elemento da lista filtrada. Nem mesmo precisamos usar uma lista finita para nosso conjunto inicial. Isso é preguiça em ação novamente. Como acabamos usando apenas o cabeçalho da lista filtrada, não importa se a lista filtrada é finita ou infinita. A avaliação pára quando a primeira solução adequada é encontrada.

onmyway133
fonte