COMP1130 PAL Week 3: Side Effects & Lambdas

Side Effects

One important aspect of Haskell is that it is a side-effect free language. But what does this mean?

Definition

There are three main characteristics to side-effect free functions:

  • Same output for given input
  • Does not rely on variables (during computation)
  • Does not write to memory

Example

Side effect-free world: “If it rains today, the ground will be wet” Side effecting world: “If it rains today, the ground is wet and ANU campus is closed”

Questions

Which of these is side effect free? Think about it in the context of the room, not necessarily the world at large.

  • I write 5 on a whiteboard
  • I think of the sentence “Hello World”
  • Edmund pays Tina $10
  • I dance alone in my room
  • Robin gets a girlfriend
  • Edmund loses a pen

Draw a table with two headings: Side Effect-Free and Side Effecting, and fill in each of the examples underneath. For each example, create a corresponding example for the other heading. e.g. “I write 5 on a whiteboard” is side effecting, a side effect-free example could be “I think of the number 5”.

Philosophy

If a program changes state but no one is there to see it, is it side effecting? Computer Science says yes.

Lambda Calculus

Lambda calculus is the basis for all functional programming languages and some would argue that it is intrinsic to an understanding of computer science and the core components of any programming language. λ-calculus is essentially very high level mathematics. Haskell is built almost entirely on the concepts found here!

Basic λ Syntax

let x = e1 in e2 is short for (λx.e2) e1

From λ to Maths & English

Let’s convert these lambda expressions into either a mathematical or plain English statement. Hint: Remember that λy basically means “for all y”.

  1. λy.(λx.xy)
  2. (λx.y)x
  3. λx.(λy.x)x
  4. λx.x*x
  5. λ(hosking).(hosking + 57)

From Maths & English to λ

Now for something slightly down the deep end - here’s your turn to create your own lambdas. Convert the following mathematical/plain English formulas into Lambda expressions. You may find it helpful to convert the plain English statements into Maths first - λ is much closer to the Maths you are accustomed to than you might expect!

  1. x2 + 3y ∀x, y
  2. x2 + y2 ∀x, y
  3. x3 - 7x - 10 ∀x
  4. The Pythagoras’ Theorem (given 2 sides of a right-angled triangle, find the 3rd side). Hint: You are allowed to use √
  5. The Manhattan Distance

"mmmmm manhattan"