Com que frequência o seq é usado no código de produção Haskell?

23

Tenho alguma experiência em escrever pequenas ferramentas em Haskell e acho muito intuitivo usar, especialmente para escrever filtros (usando interact) que processam sua entrada padrão e a canalizam para a saída padrão.

Recentemente, tentei usar um desses filtros em um arquivo que era cerca de 10 vezes maior que o normal e recebi um Stack space overflowerro.

Depois de fazer algumas leituras (por exemplo, aqui e aqui ), identifiquei duas diretrizes para economizar espaço na pilha (haskellers experientes, corrija-me se escrever algo que não esteja correto):

  1. Evite chamadas de função recursivas que não são recursivas de cauda (isso é válido para todos os idiomas funcionais que oferecem suporte à otimização de chamada de cauda).
  2. Introduzir seqpara forçar a avaliação antecipada das subexpressões para que as expressões não cresçam muito antes de serem reduzidas (isso é específico para Haskell, ou pelo menos para idiomas usando avaliação lenta).

Depois de introduzir cinco ou seis seqchamadas no meu código, minha ferramenta roda sem problemas novamente (também nos dados maiores). No entanto, acho que o código original era um pouco mais legível.

Como não sou um programador experiente da Haskell, gostaria de perguntar se a introdução seqdessa maneira é uma prática comum e com que frequência a pessoa verá normalmente seqno código de produção da Haskell. Ou existem técnicas que permitem evitar o uso com seqmuita frequência e ainda usam pouco espaço na pilha?

Giorgio
fonte
1
Otimizações como a que você descreveu quase sempre tornam o código um pouco menos elegante.
Robert Harvey
@ Robert Harvey: Existem técnicas alternativas para manter baixo o uso da pilha? Quero dizer, imagino que tenho que reescrever minhas funções de maneira diferente, mas não tenho idéia se existem técnicas bem estabelecidas. Minha primeira tentativa foi usar funções recursivas de cauda, ​​o que ajudou, mas não me permitiu resolver completamente o meu problema.
Giorgio

Respostas:

17

Infelizmente, há casos em que é preciso usar seqpara obter um programa eficiente / que funcione bem para grandes dados. Portanto, em muitos casos, você não pode ficar sem ele no código de produção. Você pode encontrar mais informações no Mundo Real Haskell, Capítulo 25. Criação de perfil e otimização .

No entanto, existem possibilidades de como evitar o uso seqdireto. Isso pode tornar o código mais limpo e mais robusto. Algumas ideias:

  1. Use conduítes , tubos ou iterados em vez de interact. O IO preguiçoso é conhecido por ter problemas com o gerenciamento de recursos (não apenas a memória) e os iterados são projetados exatamente para superar isso. (Sugiro evitar E / S preguiçosas no todo, independentemente do tamanho dos seus dados - consulte O problema com E / S preguiçosa .)
  2. Em vez de usar seqdiretamente (ou criar o seu próprio) combinadores, como foldl ' ou foldr' ou versões estritas de bibliotecas (como Data.Map.Strict ou Control.Monad.State.Strict ) projetadas para cálculos estritos.
  3. Use a extensão BangPatterns . Permite substituir seqcom uma correspondência estrita de padrões. Declarar campos estritos do construtor também pode ser útil em alguns casos.
  4. Também é possível usar estratégias para forçar a avaliação. A biblioteca de estratégias é voltada principalmente para cálculos paralelos, mas possui métodos para forçar um valor para WHNF ( rseq) ou NF completo ( rdeepseq) também. Existem muitos métodos utilitários para trabalhar com coleções, combinar estratégias etc.
Petr Pudlák
fonte
+1: Obrigado pelas dicas e links úteis. O ponto 3 parece bastante interessante (e a solução mais fácil para eu usar agora). Em relação à sugestão 1, não vejo como evitar E / S preguiçosas pode melhorar as coisas: Tanto quanto eu entendo, E / S preguiçosas deve ser melhor para um filtro que supostamente processa um fluxo de dados (possivelmente muito longo).
Giorgio
2
@Giorgio Adicionei um link para o Haskell Wiki sobre problemas com o Lazy IO. Com o IO preguiçoso, você pode ter muita dificuldade em gerenciar recursos. Por exemplo, se você não ler completamente a entrada (como devido a uma avaliação lenta), o identificador de arquivo permanecerá aberto . E se você fechar o identificador de arquivo manualmente, geralmente acontece que, devido à leitura lenta da avaliação, ele é adiado e você fecha o identificador antes de ler toda a entrada. E, muitas vezes, é bastante difícil evitar problemas de memória com E / S preguiçosas.
Petr Pudlák
Recentemente, tive esse problema e meu programa estava ficando sem descritores de arquivo. Então, substituí IO preguiçoso por IO estrito usando strict ByteString.
Giorgio