At the edge of infinity

I couldn’t resist a catchy title for this one, as CIS 194 is all about lazy evaluation, which in turn can be used to create (virtually) infinite data structures.

Lazy evaluation is one of those features of Haskell that gets often mentioned when somebody asks why Haskell is so interesting language. In essence, it means that computations aren’t evaluated until needed or explicitly forced. And it turns out that needing is funny concept:

f :: Integer -> Integer -> Integer
f a b = error "faulty"

g :: t -> [t]
g x = [x]

h = g $ f 1 2

f will error every single time it’s called, regardless of the parameters. However, using it as part of computation of h doesn’t error, because it doesn’t get evaluated. There’s just a promise to calculate the value when it’s needed. When h is eventually evaluated (for printing it on screen for example), error will be raised. If h will never get evaluated, no error will happen.

As far as I understand, h will be evaluated if it’s printed on screen (or file or somesuch), pattern matched or used somewhere where the value is really needed (list comprehension, if and so on).

There’s some neat consequences about this. First of all, one can’t really be completely sure when something will get evaluated. This in turn means that functions can’t rely on anything outside what was passed in as parameters. Likewise, functions can’t really change anything, just return a value. There’s way to access files, keyboard and screen as shown earlier, but it’s a bit different approach than most other languages have chosen.

Secondly, since things get evaluated only when needed (or specifically requested), adding new control structures is as simple as defining a function that does the work. In lisps (Hy for example), control structures have to be added by using macros, because the way the language evaluates function parameters.

Thirdly, one can define data structures that are virtually infinite (hence name of the blog post). Recursive lists that are defined in terms of themselves are possible too, as shown in the fibonacci routine I found at Haskell wiki:

fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Or how about a stream that doesn’t even allow finity:

data Stream a = Cons a (Stream a)

Stream is something followed by a Stream of same type.

Turning Stream into a regular list (which also has to be infinite and display it on screen) doesn’t actually require much:

streamToList :: Stream a -> [a]
streamToList (Cons x xs) = x : streamToList xs

instance Show a => Show (Stream a) where
  show = show . (take 20) . streamToList

One would assume that streamToList traverses through the whole infinite Stream when turning it into a list. This is what it does of course, but not in one go. Only the part that is required is traversed. So in Show first 20 elements are evaluated, so that they can be turned into a list and printed on screen. Mapping function over a Stream or interleaving two Streams together works in similar principle:

streamMap :: (a -> b) -> Stream a -> Stream b
streamMap f (Cons x xs) = Cons (f x) $ streamMap f xs

interleaveStreams :: Stream a -> Stream a -> Stream a
interleaveStreams (Cons x xs) (Cons y ys) = Cons x $ Cons y $ interleaveStreams xs ys

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s