Pourquoi ma liste GHC évalue infinie?

Question

Comme mon premier programme haskell Je suis en train de le faire - c'est la façon difficile d'obtenir 1 à 10. Je suis la construction d'une liste infinie d'entiers et de les trier, et en prenant la première 10. Mon intention était de me convaincre que je pouvais travailler avec des listes infinies sans provoquer leur évaluation au-delà de ce qui était strictement ( ahem ) requis pour le résultat demandé.

Mon code est ..

module Main where

import Data.List

minima n xs = take n (sort xs)

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

Compiler avec GHC et l'exécution de l'exécutable résultant .. il est assis là jusqu'à l'allocation tué.

Les conseils?

Answer 1

Le problème est que vous essayez de trier la liste infinie. La liste ne peut jamais être entièrement triée jusqu'à ce que tous les éléments de la liste sont connus, de sorte que c'est pourquoi il est suspendu. Votre programme fonctionne très bien avec une liste finie.

En outre, en tant que mineur à part, vous pouvez réécrire minima comme

minima n = take n . sort

En raison de l'application partielle, minima n retourne une fonction attendant une liste.

Answer 2

Il est impossible de trier les listes infini dans le temps fini.

Comme preuve, considèrent que le tri consiste notamment à trouver l'élément minimal, et de trouver le minimum d'une liste infinie vous devez vérifier chaque élément de la liste, ce qui prendra du temps infini.

Dans votre cas, cependant, vous savez que la liste est déjà triée. Cela en fait un cas particulier de tri des listes infinies, à savoir, le tri des listes triées. Ce cas est résoluble.

Answer 3

Vous essayez de trier une liste infinie.