2009-09-20 7 views
4

Comme mon premier programme de haskell j'essaye de faire ceci - c'est la manière dure d'obtenir 1 à 10. Je construis une liste infinie d'entiers, et les classant, et prenant le premier 10. Mon intention était de convaincre moi-même que je pourrais travailler avec des listes infinies sans causer d'évaluation d'eux au-delà de ce qui était strictement (ahem) requis pour le résultat demandé.Pourquoi ghc évalue-t-il ma liste infinie?

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) 

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

Des indices?

+0

plutôt que le tri, essayez d'élévation au carré chaque valeur: prendre 10 $ map (^ 2) [1 ..] –

Répondre

12

Le problème est que vous essayez de trier la liste infinie. La liste ne peut jamais être entièrement triée tant que tous les éléments de la liste ne sont pas connus, c'est pourquoi elle est suspendue. Votre programme fonctionne 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 renverra une fonction attendant une liste.

+3

Bien sûr que la version partiellement appliquée est exactement équivalente à la fonction d'origine et encore accrocher une liste infinie . (Je sais que vous le savez - je ne fais que le souligner pour ceux qui jouent à la maison.) – Chuck

+0

Ah oui - assez évident rétrospectivement que je ne pouvais pas m'attendre à ce que l'implémentation ne continue pas à chercher une valeur plus petite. * blush * Lorsque j'essaie votre autre suggestion, je reçois ce qui suit. Je ne comprends pas encore mais je vais continuer à creuser, merci! test.hs: 6: 21: Impossible de faire correspondre le type attendu '[a] ' au type inféré' [a1] -> [a1]' Dans le second argument de '($) ',' '' sort ' Dans l'expression: take n $ sort Dans la définition de 'minima': minima n = take n $ sort – billt

+0

Mark a corrigé sa réécriture. Cela aurait dû être un point (composition de fonction) plutôt qu'un $ (application de fonction). – Chuck

2

Vous essayez de trier une liste infinie.

7

Il est impossible de trier les listes infinies en temps fini. À titre de preuve, considérons que le tri inclut la recherche de l'élément minimum, et pour trouver le minimum d'une liste infinie, vous devez vérifier chaque élément de la liste, ce qui prendra un 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.