Por que é ghc avaliando minha lista infinita?

Question

Como o meu primeiro programa Haskell Eu estou tentando fazer isso - é a maneira mais difícil de obter 1 a 10. Eu estou construindo uma lista infinita de inteiros, e classificando-os, e tendo o primeiro 10. Minha intenção era me convencer de que eu poderia trabalhar com listas infinitas sem causar avaliação dos mesmos além do que era estritamente ( ahem ), necessários para o resultado exigido.

Meu código é ..

module Main where

import Data.List

minima n xs = take n (sort xs)

main = do
    let x = [1..] 
    print (minima 10 x)

Compilando com ghc e executar o executável resultante .. ele fica lá alocar até mortos.

Alguma dica?

Answer 1

O problema é que você está tentando classificar a lista infinita. A lista nunca pode ser totalmente ordenados até que todos os elementos da lista são conhecidos, então é por isso que está pendurado. Seu programa funciona bem com uma lista finita.

Além disso, como um menor de lado, você pode reescrever mínimos como

minima n = take n . sort

Por causa da aplicação parcial, minima n irá retornar uma função esperando uma lista.

Answer 2

É impossível classificar listas infinitas em tempo finito.

Como prova, considere que a classificação inclui encontrar o elemento mínimo, e para encontrar o mínimo de uma lista infinita você tem que verificar todos os elementos na lista, que vai levar tempo infinito.

No seu caso, no entanto, sabe que a lista já está classificado. Isto o torna um caso especial de classificação listas infinitas, ou seja, a triagem listas ordenadas. Este caso tem solução.

Answer 3

Você está tentando classificar uma lista infinita.