Haskell script em execução fora do espaço

Question

Eu estou usando projeto Euler ensinar-me Haskell, e eu estou tendo alguns problemas de raciocínio sobre como meu código está sendo executado por Haskell. O segundo problema tem me calcular a soma de todos os números pares de Fibonacci até 4 milhões. Meu script esta aparência:

fibs :: [Integer]
fibs =  1 : 2 : [ a+b | (a,b) <- zip fibs (tail fibs)]

evens  :: Integer -> Integer -> Integer
evens x sum | (even x)   = x + sum
            | otherwise  = sum

main = do
  print (foldr evens 0 (take 4000000 fibs))

Hugs dá o erro "A coleta de lixo não consegue recuperar espaço suficiente", que eu suponho que significa que os itens da lista não são liberados como eles são consumidos por foldr.

O que eu preciso fazer para corrigir isso? Eu tentei escrever uma versão cauda-recursivo (eu acho) que acumuladores usados, mas não conseguiu que quer trabalhar.

Answer 1

Uma série de observações / sugestões:

• as x + sums de ainda não estão sendo avaliadas até o fim
• Você está dando os primeiros 4.000.000 mentiras, não as mentiras até 4.000.000
• Existe uma maneira mais fácil de fazer isso

Editar em resposta ao comentário

Eu não vou dizer o que a maneira mais fácil é, já que é a diversão de problemas de projeto Euler. Mas eu vou pedir-lhe um monte de perguntas:

• Quantas mentiras, mesmo que você pode ter em uma linha?
• Quanto tempo você pode ir sem uma lorota mesmo?
• Se você somar todos os até mesmo mentiras e todas as mentiras ímpares (fazer isso manualmente), o que você observa sobre as somas?

Answer 2

Em primeiro lugar, você não deve usar abraços. É um brinquedo apenas para fins de ensino.

GHC, no entanto, é um compilador otimizado rápido, multicore-pronto para Haskell. obtê-lo aqui . Em particular, ele faz análise de rigor, e compila para código nativo.

A principal coisa que se destaca sobre o seu código é o uso de foldr em uma lista muito grande. Provavelmente você quer um ciclo recursiva cauda. Como assim:

import Data.List

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

evens x sum | even x    = x + sum
            | otherwise = sum

-- sum of even fibs in first 4M fibs
main = print (foldl' evens 0 (take 4000000 fibs))

Além de tudo isso, os primeiros 4M até mesmo mentiras vai usar uma boa quantidade de espaço, por isso vai demorar um pouco.

Aqui está a soma do primeiro 400k até mesmo mentiras , para salvar -lhe algum tempo (21s). : -)

Answer 3

Você entendeu errado problema. A real problema quer que você somar todos os números pares de Fibonacci tal que o Fibonacci número que em si não exceder 4 milhões (que passa a ser apenas os primeiros 33 números de Fibonacci).

Answer 4

Você está avaliando quatro milhões de elementos de fibs. Esses números crescem exponencialmente. Eu não sei quantos bytes são necessários para representar o número Fibonacci milionésimo; apenas a um milésimo de números de Fibonacci tem 211 dígitos decimais, de modo que vai levar 22 palavras de 32 bits apenas para manter os dígitos, não importa o que quer que impõe gmp gerais. E estes crescer exponencialmente.

Exercício:. Calculuate a quantidade de memória necessária para manter quatro milhões de números de Fibonacci

Answer 5

ter um olhar para as funções Prelude TakeWhile, filtro, mesmo, e soma

TakeWhile (<40) [0 ..]
filtro de até US $ TakeWhile (<40) [0 ..]

colocá-los juntos:

= soma ans $ filtro mesmo TakeWhile $ (<4 * 10 ^ 6) mentiras