-- Lecture Notes 
-- Programming Languages and Types
 
-- October 22, 2009
-- Instructor: Sebastian Erdweg

-- Based on PLAI by Shriram Krishnamurthi and
-- "Why functional programming matters" by John Hughes



-- The programming language Haskell utilizes lazy evaluation, as
-- opposed to eagerly evaluated languages such as Scheme.

-- Lazy evaluation means, that expressions are not evaluated
-- until the result of that evaluation is actually needed.
-- 
-- On the other hand, with eager evaluation expressions are always
-- evaluated, regardless of whether the evaluation's result is actually
-- used. Consequently, errors within unused expressions do only occur
-- when eager evaluation is used:


ignore x = 42
maybeError = ignore (17 `div` 0)



-- Eager evaluation corresponds to
--   call-by-value semantics.
-- Lazy evaluation corresponds to
--   call-by-need semantics.

-- call-by-value:
--   Before a function call is evaluated, the argument has to be
--   evaluated. Hence, the function is called with a value.
--
-- call-by-name:
--   In a function call, the argument expression is not evaluated
--   but simply substituted into the function body.
--
-- call-by-need:
--   Like call-by-name, but the evaluation of the argument expression
--   is cached. Used to increase perfomance of call-by-name.


double x = x + x
doubleCall = double (1 + 2 + 3 + 4 + 5 + 6)



-- Laziness enables the use of infinite data structures by
-- looping (corecursive) definitions.

-- For example, the list of all natural numbers is given by

nats = 0 : map succ nats

-- nats =          0 : 1 : 2 : 3 : 4 : ...
--                +1  +1  +1  +1  +1
-- map succ nats = 1 : 2 : 3 : 4 : 5 : ...
-- nats =      0 : 1 : 2 : 3 : 4 : 5 : ...




-- More interestingly, the Fibonacci numbers can be defined
-- very concisely by

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

-- fibs =         1 : 1 : 2 : 3 : 5  : ...
--                +   +   +   +   +
-- tail fibs =    1 : 2 : 3 : 5 : 8  : ...
-- zipWith ... =  2 : 3 : 5 : 8 : 13 : ...
-- fibs = 1 : 1 : 2 : 3 : 5 : 8 : 13 : ...




-- More generally, laziness allows for modular design of programs
-- in a simple and very useful way.
--
-- In functional language, programs can composed such that the
-- output of the one program represents the input of the other one.


f n = map (2^) [1 .. n]
g = any (> 42)
prog = g . f





-- In lazily evaluated languages, only as much output is produced by the
-- first program, as input is required by the second one. Accordingly,
-- even if the former program is non-terminating, the composed program
-- halts if the second program only demands limited amount of input.
--
-- This enables the modular programming technique, in which one program
-- generates a possibly infinite number of proposed answers, and another
-- program selects the appropriate or interesting ones.


fibsFrom n = dropWhile (< n) fibs


-- nextFibs produces a list of subsequent Fibonacci numbers, where
-- the smallest one is larger than nextFibs' second argument, and
-- the list contains as many numbers as the first argument indicates.
nextFibs k = take k . fibsFrom