Why is ghc evaluating my infinite list?

Question

As my first haskell program I'm trying to do this - it's the hard way to get 1 to 10. I'm constructing an infinite list of integers, and sorting them, and taking the first 10. My intention was to convince myself that I could work with infinite lists without causing evaluation of them beyond what was strictly (ahem) required for the demanded result.

My code is..

module Main where

import Data.List

minima n xs = take n (sort xs)

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

Compiling with ghc and running the resulting executable.. it sits there allocating until killed.

Any hints?

Answer 1

The problem is that you're trying to sort the infinite list. The list can never be fully sorted until all elements in the list are known, so that's why it's hanging. Your program works fine with a finite list.

Also, as a minor aside, you can rewrite minima as

minima n = take n . sort

Because of partial application, minima n will return a function expecting a list.

Answer 2

You're trying to sort an infinite list.

Answer 3

It's impossible to sort infinite lists in finite time.

As a proof, consider that sorting includes finding the minimum element, and to find the minimum of an infinite list you have to check every element in the list, which will take infinite time.

In your case, however, you know that the list is already sorted. This makes it a special case of sorting infinite lists, namely, sorting sorted lists. This case is solvable.