Does this Haskell example effectively demonstrate laziness?

Question

I'm new to Haskell, and I'm writing a paper on it for my Programming Languages class. I want to to demonstrate Haskell's laziness with some sample code, but I'm not sure if what I'm seeing is actually laziness.

doubleMe xs = [x*2 | x <- xs]

In ghci:

let xs = [1..10]
import Debug.Trace
trace (show lst) doubleMe (trace (show lst) doubleMe (trace (show lst) doubleMe(lst)))

Output:

[1,2,3,4,5,6,7,8,9,10]
[1,2,3,4,5,6,7,8,9,10]
[1,2,3,4,5,6,7,8,9,10]
[8,16,24,32,40,48,56,64,72,80]

Thanks for your time and help!

Answer 1

Your usage of trace here isn't particularly insightful, or in fact at all. All you do is print out the same list at four different points in the evaluation, that doesn't tell you anything about the actual state of the program. What actually happens here is that trace is forced in every doubling step before calculation even starts (when the result list is requested to weak head normal form). Which is pretty much the same as you would get in a language with fully strict evaluation.

To see some lazyness, you could do something like

Prelude Debug.Trace> let doubleLsTracing xs = [trace("{Now doubling "++show x++"}")$ x*2 | x<-xs]
Prelude Debug.Trace> take 5 $ doubleLsTracing [1 .. 10]
{Now doubling 1}
{Now doubling 2}
{Now doubling 3}
{Now doubling 4}
{Now doubling 5}
[2,4,6,8,10]

where you can see that only five numbers are doubled, because only five results were requested; even though the list that doubleLsTracing was given has 10 entries.

Note that trace is generally not a great tool to monitor "flow of execution", it's merely a hack to allow "looking into" local variables to see what's going on in some function.

Answer 2

Infinite streams are always a good example. You cannot obtain them in other languages without special constructs - but in Haskell they are very natural.

One example is the fibonacci stream:

fib = 0 : 1 : zipWith (+) fib (tail fib)

take 10 fib => [0,1,1,2,3,5,8,13,21,34]

Another one is obtaining the stream of prime numbers by using the trial division method:

primes = sieve [2..]
    where sieve (x:xs) = x : filter (not . (== 0) . (`mod` x)) (sieve xs)

take 10 primes => [2,3,5,7,11,13,17,19,23,29]

Also, implementing backtracking in Haskell is very simple, giving you the ability to obtain the list of solutions lazily, on demand:

http://rosettacode.org/wiki/N-queens_problem#Haskell

A more complex example, showing how you can implement min is the one found here:

Lazy Evaluation and Time Complexity

It basically shows how using Haskell's laziness you can obtain a very elegant definition of the minimum function (that finds the minimum in a list of elements):

minimum = head . sort

You could demonstrate Haskell's laziness by contrived examples. But I think it is far better to show how laziness helps you develop solutions to common problems that exhibit far greater modularity than in other languages.