¿Por qué es GHC evaluando mi lista infinita?

Question

Como mi primer programa Haskell estoy tratando de hacer esto - es la manera más difícil de conseguir 1 a 10. Estoy construyendo una lista infinita de números enteros, y clasificación de ellos, y tomando el primer 10. Mi intención era convencer a mí mismo que podía trabajar con listas infinitas sin causar evaluación de los mismos más allá de lo estrictamente ( ejem ) requerido para el resultado exigido.

Mi código es ..

module Main where

import Data.List

minima n xs = take n (sort xs)

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

Compilar con GHC y ejecutar el ejecutable resultante .. se sienta allí hasta que la asignación de muertos.

¿Alguna pista?

Answer 1

El problema es que usted está tratando de ordenar la lista infinita. La lista no puede ser totalmente ordenadas hasta que se conozcan todos los elementos de la lista, así que por eso está colgado. Su programa funciona bien con una lista finita.

Además, como un menor de edad a un lado, se puede reescribir como mínimos

minima n = take n . sort

Debido a la aplicación parcial, minima n devolverá una función que espera una lista.

Answer 2

Es imposible ordenar las listas infinitas en un tiempo finito.

Como prueba, tenga en cuenta que la clasificación incluye encontrar el elemento mínimo, y para encontrar el mínimo de una lista infinita que tiene que comprobar cada elemento de la lista, que se llevará a tiempo infinito.

En su caso, sin embargo, se sabe que la lista ya está ordenada. Esto hace que sea un caso especial de clasificación de listas infinitas, a saber, la clasificación listas ordenadas. Este caso tiene solución.

Answer 3

Usted está tratando de ordenar una lista infinita.