{-
HASKELL - LAZY EVALUATION AND INFINITE DATA STRUCTURES
CSE 341, Autumn 2008
-}
module InfiniteDataStructures
where
{- Since Haskell uses lazy evaluation, we can have infinite data structures --
we only produce as much of the structure as is needed. We've seen various
examples of this, for example
[1.. ]
[1,3 ..]
verylargetree (from TypesNotes.hs)
-}
my_member :: Eq a => a -> [a] -> Bool
my_member x [] = False
my_member x (y:z) | x==y = True
| otherwise = my_member x z
-- this works: my_member 10 [1..]
-- this searches forever: my_member 3 [10..]
-- MEMBER FUNCTION FOR SORTED LISTS
sorted_member :: Ord a => a -> [a] -> Bool
sorted_member x [] = False
sorted_member x (y:z) | x==y = True
| x<y = False
| x>y = sorted_member x z
{- this version of member will always terminate. For example
sorted_member 3 [10..]
terminates immediately
-}
-- SQUARE ROOT
sqt x = head (filter close_enough (approximations x))
where approximations a = a : approximations ((a + x/a)/2)
close_enough root = abs (x-root*root) < 1.0e-6
-- to show the list of successive approximations:
trial_roots x = approximations x
where approximations a = a : approximations ((a + x/a)/2)
-- INFINITE LIST OF PRIME NUMBERS
factors n = [k | k <- [1..n], n `mod` k == 0]
dullprimes = filter isprime [2..]
where
isprime p = (factors p == [1,p])
{- Fibonacci numbers (clear but inefficient recursive version) -}
rec_fib 1 = 1
rec_fib 2 = 1
rec_fib n = rec_fib (n-1) + rec_fib (n-2)
{- map2 is like map but takes a 2-argument function (we'll use it
for another version of Fibonacci numbers) -}
map2 :: (a -> b -> c) -> [a] -> [b] -> [c]
map2 f [] [] = []
map2 f (x:xs) (y:ys) = f x y : map2 f xs ys
map2 f [] (y:ys) = error "different length lists to map2"
map2 f (x:xs) [] = error "different length lists to map2"
{- some would argue that better style would be to replace the last two
definitions with
map2 f xs ys = error "different length lists to map2"
This has one less pattern, but depends on the order in which they are given
(the other version is order-independent). -}
{- Infinite list of Fibonacci numbers. This uses a common pattern for
Haskell infinite list definitions, in which you have a prime-the-pump
sort of recursive definition. -}
fibs = 1 : 1 : map2 (+) fibs (tail fibs)
{- HAMMING NUMBERS
The Hamming numbers are defined as the list of all numbers of the form
2^a * 3^b * 5*c
for non-negative integers a, b, and c; in other words, numbers whose
only prime factors are 2, 3. and 5. -}
my_merge (x:a) (y:b) | x<y = x : my_merge a (y:b)
| x==y = y : my_merge a b
| x>y = y : my_merge (x:a) b
ham = 1: my_merge ham2 (my_merge ham3 ham5)
ham2 = map (*2) ham
ham3 = map (*3) ham
ham5 = map (*5) ham
{-
take 100 ham
evaluates to:
[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36,
40, 45, 48, 50, 54, 60, 64, 72, 75, 80, 81, 90, 96, 100, 108, 120, 125,
128, 135, 144, 150, 160, 162, 180, 192, 200, 216, 225, 240, 243, 250, 256,
270, 288, 300, 320, 324, 360, 375, 384, 400, 405, 432, 450, 480, 486, 500,
512, 540, 576, 600, 625, 640, 648, 675, 720, 729, 750, 768, 800, 810, 864,
900, 960, 972, 1000, 1024, 1080, 1125, 1152, 1200, 1215, 1250, 1280, 1296,
1350, 1440, 1458, 1500, 1536]
-}
{- Infinite list of prime numbers using the Sieve of Eratosthenes.
See http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes -}
interestingprimes = sieve [2..]
where
sieve (p:x) = p : sieve [n | n <- x, n `mod` p > 0]
{- Why Infinite Lists?
Are infinite lists (and other infinite data structures) simply curiosities
or something more important?
Simon Thompson in "The Craft of Functional Programming" argues that they
are more important, for two reasons:
First, an infinite version of a program can be more abstract and simpler to
write, since we don't need to know in advance how long to make the list
(e.g. the fibonacci number list).
Second, we can often modularize the generation of values, and separate out
some transformations we perform on them. We can then link process-style
programs that involve recursion. (Thompson gives a simulation example.)
-}
