[SOLVED] CS Haskell algorithm Higher Order Functions in Haskell

Higher Order Functions in Haskell

Today:
Lazy Evaluation

Evaluation Strategy
A programming languages policy on when to compute an expression that is being passed as an argument

Before being passed?Or after?
Definitely going to evaluate?
Or perhaps not?

Eager/Strict/Applicative Order Evaluation
All arguments are evaluated, and they are evaluated before passing them to a subroutine.

Circle is called once.

Evaluation order?
Eager / Strict / Applicative

(b.b(x.y.x a.a))

(b.by.a.a)

y.a.a
Lazy / Non-strict / Normal

(b.b(x.y.x a.a))

(x.y.x a.a)

y.a.a

(b.b(x.y.x a.a))

Normal Order Evaluation
A representation of the unevaluated argument is passed to the subroutine, and then each is evaluated at the last possible moment as many times as it appears:

(sum-of-squares (+ 5 1) (* 5 2))
(+ (square (+ 5 1)) (square (* 5 2)))
(+ (* (+ 5 1)(+ 5 1)) (* (* 5 2)(* 5 2)))
(+ (* 6 6) (* 10 10))
(+ 36 100)
136

Lazy Evaluation
A representation of the unevaluated argument is passed to the subroutine, and then evaluated at the last possible moment.

When an argument is finally evaluated in a lazy language, the result of the evaluation is saved (memoized). Further uses of the argument in the function use the saved value.

Thus the original argument is evaluated at most one time, and as well see, possibly not at all.Lazy is a sub-category of normal order, but is as efficient as applicative order evaluation.

(sum-of-squares (+ 5 1) (* 5 2))
(+ (square (+ 5 1)) (square (* 5 2)))
(+ (* (+ 5 1)(+ 5 1)) (* (* 5 2)(* 5 2)))
(+ (* 6 6) (* 10 10))
(+ 36 100)
136

Haskell laziness
> head []
*** Exception: Prelude.head: empty list
> ( x -> x + 1) 3
4
> ( x -> 3) (head [])

8
First results are shown on student handouts.

Haskell laziness
> head []
*** Exception: Prelude.head: empty list
> ( x -> x + 1) 3
4
> ( x -> 3) (head [])
3

9

Why be lazy? Part One
Like people, sometimes a language can delay computational work to the point of not having to do it at all.

So laziness is in large part about efficiency: not having to do more work than necessary.

For Example
Heres a code snippet in Scala, which is a multi-paradigm language that evaluates eagerly by default, but can evaluate lazily if you explicitly ask it to.Here, its evaluating eagerly.

What is the output?

called
no result

For Example
SHOULD the output have been calledno result?

Arguably not: compute(5) did not actually need to be evaluated.

In the Boolean expression (if x > 5 && temp > 10), the value of temp and therefore the result of compute(5) is not needed, because x is 4.

For Example
This is the same code, except now I have annotated the temp variable with the word lazy.Here, we are taking advantage of Scalas ability to evaluate lazily when explicitly asked to do so.The variable temp will not be evaluated until necessary.

So what will the output be?

no result

In other words, compute was never evaluated.It didnt have to be!

The moral of the previous Scala example was: if you can ignore computation, you can save work and ignoring computation is only possible with a lazy evaluation strategy.

The efficiency of lazy evaluation is particularly clear in this example, using Haskell:

f x y = if unlikely condition
then mod y 2
else x + 2

As we know, under the hood, this Haskell function is really:

f =x ->y -> if unlikely condition
then mod y 2
else x + 2

Now, what if we called:

f 5 (2935792) ?Holy moly, that exponent is a lot of work.

If Haskell followed applicative order evaluation, we would always have to evaluate the argument y, even though y is rarely used.But because Haskell is lazy, in fact (2935792) is passed unevaluated and rarely ends up getting computed at all.

Why be lazy? Part Two
Laziness in Haskell allows for certain kinds of computation on infinite lists!Since laziness only evaluates as much as is actually needed, infinite data is only generated as it is consumed, and not impossibly all at once.

Heres how you write infinite lists:
[1..]
[1,3..]
No upper bound.

17

> ones = 1 : ones
> ones

17

sum[1..]

Just doesnt work: you cant sum an infinite list.

18

Infinite lists
Really, infinite lists are most practical when you separate control from data, where your data is infinite and its the control that limits it:

take 3 [1..]
[1,2,3]

Why couldnt you do this with an eager language?

Because the [1..] would have to be evaluated and then passed into take, which is impossible.

Lets see why this works in Haskell.

Why does take 3 [1..] work, lazily?
First, lets implement take:

Participation Quiz

Why does take 3 [1..] work, lazily?
First, lets implement take:

myTake :: Int -> [a] -> [a]
myTake 0 _ = []
myTake _ [] = []
myTake n (x:xs) = x : myTake (n-1) xs

Next, lets see how take 3 [1..] traces (on board).

If you dont have (good) notes on this, here is a great online resource:

Why be lazy? Part Three
Because it enables modularity!Modularity is the ability to break a program into parts that can be put back together.Modularity makes code reusable, which is always a good thing.

Example:
Newton-Raphson algorithm for approximating the square root of a number
Lazy functional languages let you separate the looping condition from the body of the loop!

Not modular, applicative and imperative code for finding square root
squareRt(c, tol):
t = c
while( abs(t c/t) > tol*t):
t = (c/t + t)/2
return t

Not modular, because cant separate the condition from the loop body.

Modular code for finding square root: lazy and functional

/docProps/thumbnail.jpeg