--Lazy Evaluation

-- Infinite list of numbers from n:
ints :: (Num a) => a -> [a]
ints n = n : ints (n+1)

{-- Test it with:

let i0 = ints 0

head i0

head (tail i0)

head (drop 10 i0)

--}

nth :: [a] -> Integer -> a
nth (h:t) 1 = h
nth (h:t) n = nth t (n-1)

{-- Test it with:

nth [3,4,5,6] 3

nth i0 11

--}

-- Infinite Fibonacci sequence:
fib = fib' 0 1
        where fib' f1 f2 = f1 : fib' f2 (f1+f2)

{-- Test it with:

take 20 fib

--}

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

{-- Test it with:

take 20 fib'

--}


{--Avi's Pascal triangle--}
pascal row = row : pascal (zipWith (+) (0:row) (row++[0]))

{-- Test it with:

pt = pascal [1]

take 10 pt

nth pt 11

--}


--Infinite list of prime numbers using Eratosthenes' sieve
sieve :: (Integral a) => [a] -> [a]
sieve (x:xr) = x:sieve (filter (\y -> (y `mod` x /= 0)) xr)

primes :: (Integral a) => [a]
primes = sieve (ints 2)

{-- Test it with:

take 20 primes

--}

--List Comprehensions

lc1 = [(x,y) | x <- [1..10], y <- [1..x]]
lc2 = filter (\(x,y)->(x+y<=10)) lc1

lc3 = [(x,y) | x <- [1..10], y <- [1..x], x+y<= 10]

--Quicksort using list comprehensions
quicksort :: (Ord a) => [a] -> [a]
quicksort []    = []
quicksort (h:t) = quicksort [x | x <- t, x < h] ++
                  [h] ++
                  quicksort [x | x <-t, x >= h]
 
{-- Test it with:

quicksort [5,2,8,6]

--}