Pourquoi ghc évalue-t-il ma liste infinie?

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?

Source

2009-09-20 billt

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

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.

Source

2009-09-20 06:14:01

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

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

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

Vous essayez de trier une liste infinie.

Source

2009-09-20 06:34:00

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.

Source

2009-09-20 11:25:00 yairchu

Pourquoi ghc évalue-t-il ma liste infinie?

Répondre

Questions connexes