Flashback to July 2016!

Peruvian ITiCSE

Peruvian ITiCSE

Dear students,

Today we begin our foray in the Haskell language, which is very different from the Java and C that you have been steeped in. I want to introduce its craziness by just solving some problems. We’ll see what we encounter.

Here are the tasks I will ask you to complete with a neighbor:

- MajorityWrite in a language of your choice a function that calculates how many people are needed to make up a majority? What do you need to know?
- CircletweenYou are given two points. How can you identify a circle on whose perimeter they lie?

We solve these in Haskell below:

*Problem 1*: Let’s write a function to calculate how many people make up a majority. What do we need to know to calculate this? How do we calculate it?

Here’s our first attempt at a Haskell function:

majority n = n / 2 + 1

What happens when we run this?

> majority 100 51.0 > majority 101 51.5

We see that `/`

doesn’t perform integer division. But we didn’t discover this until after we ran our code. What are some ways that we could have made this issue manifest earlier in the process? Recall our discussion of static versus dynamic decision making. In order to discover certain kinds of errors earlier, we need to give more power to the compiler. We need type declarations!

In many situations, Haskell can infer the types for you. Let’s see what is inferred for `majority`

right now:

> :t majority majority :: Fractional a => a -> a

We ready this as “`majority`

has the type of turning an `a`

into an `a`

, where `a`

is some type that belongs to the `Fractional`

typeclass.” But we didn’t didn’t declare this. The type constraints came from the `/`

operator:

> :t (/) (/) :: Fractional a => a -> a -> a

The `/`

operator takes a first `a`

and a second `a`

, and produces a third `a`

. Technically the `+`

had something to say in the matter too, but it didn’t constrain the types any further. The result is a `Fractional`

.

So, how do we get it to yield something not `Fractional`

? We must use the `div`

function:

majority n = div n 2 + 1

While we’re talking about `div`

, let’s make some observations. When you write your own programming language, your universe starts to collapse in some mind-boggling ways. You learn…

- That variables are just functions taking no parameters and always yielding the same value.
- That objects are just dictionaries whose indices are the field names. In Javascript, for instance, we can access a field in two different ways:
`console.log(hero.name); console.log(hero['name']);`

- That arrays are just dictionaries whose indices are integers.
- That operators are just non-void methods of arity 1 or 2.
`+`

is`operator+(int a, int b)`

, for instance. Parameters are operands, and both yield values.

Certainly in Haskell, operators are functions and vice versa. We can treat `div`

as an infix operator:

majority n = n `div` 2 + 1

We can mimic Python’s `//`

to perform integer division by adding a new operator:

a // b = a `div` b

Let’s make sure this works. What do we expect as the value of the following expression?

100 `div` 10 // 2

We expect `(div 100 10) // 2`

, which is 5. But we get `div 100 (10 // 2)`

, which is 20. What went wrong? Operator precedence. When we create a new operator, it is given very high precedence by default. We can change that. But how? Let’s first inspect the precedence level of `/`

:

> :info / class Num a => Fractional a where (/) :: a -> a -> a ... -- Defined in ‘GHC.Real’ infixl 7 /

That last line tells us that the `/`

operator has precedence 7, and that its left associative, meaning that `a / b / c`

will parse as `(a / b) / c`

instead of `a / (b / c)`

.

Many of our operators are left associative. Can you think of any that are right associative? `man operator`

lists a few: the assignment operators and unary operators like negation, dereferencing, casting, and address-of.

*Problem 2*: Let’s generate a circle between two 2D points. A very natural thing to do is start off with something like this:

circletween x1 y1 x2 y2 = ...

What’s not so great about this is that all the parameters are loose. `x1`

and `y1`

really belong together. As do `x2`

and `y2`

. We’d like to treat them as such. For that, we can use tuples! On the calling side, we can say:

circletween (0, 0) (1, 1)

Then on the definition side, we can return a tuple of the circle:

circletween a b = (fst b - fst a, snd b - snd a, 0.5 * sqrt ((fst a - fst b) ** 2 + (snd a - snd b) ** 2)

Ick. In any other language, we’d break this code up and introduce some local variables. We can and should do the same in Haskell. Let’s use a `where`

clause:

circletween a b = (x, y, radius) where x1 = fst a y1 = snd a x2 = fst b y2 = snd b x = (x1 + x2) * 0.5 y = (y1 + y2) * 0.5 deltaX = x2 - x1 deltaY = y2 - y1 radius = 0.5 * sqrt (deltaX ** 2 + deltaY ** 2)

This is still longer than it needs to be. To clean it up further, we will use on of Haskell’s most beautiful features: pattern matching. We can use it to automatically decompose values into their components:

circletween (x1, y1) (x2, y2) = (x, y, radius) where x = (x1 + x2) * 0.5 y = (y1 + y2) * 0.5 deltaX = x2 - x1 deltaY = y2 - y1 radius = 0.5 * sqrt (deltaX ** 2 + deltaY ** 2)

Here’s your TODO list:

- Install the Haskell tools. On Ubuntu, run this:
sudo apt-get install haskell-platform

- Read chapters 1 and 2 of Learn You a Haskell for a Great Good!, which can be read freely online. On a quarter sheet, write function
`clamp`

which accepts a number, an upper bound, and a lower bound. Clamp the number within the numeric range. For example,`clamp -10 0 100`

yields 0,`clamp 101 0 100`

yields 100, and`clamp 47 0 100`

yields 47.

See you next time!

Sincerely,

- May 2017
- April 2017
- March 2017
- February 2017
- January 2017
- December 2016
- November 2016
- October 2016
- September 2016
- August 2016
- July 2016
- June 2016
- May 2016
- April 2016
- March 2016
- February 2016
- January 2016
- December 2015
- November 2015
- October 2015
- September 2015
- August 2015
- June 2015
- May 2015
- April 2015
- March 2015
- February 2015
- January 2015
- December 2014
- November 2014
- October 2014
- September 2014
- August 2014
- July 2014
- June 2014
- May 2014
- April 2014
- March 2014
- February 2014
- January 2014
- December 2013
- November 2013
- October 2013
- September 2013
- August 2013
- July 2013
- June 2013
- May 2013
- April 2013
- March 2013
- February 2013
- January 2013
- December 2012
- November 2012
- October 2012
- September 2012
- August 2012
- July 2012
- June 2012
- May 2012
- April 2012
- March 2012
- February 2012
- January 2012
- December 2011
- November 2011
- October 2011
- September 2011
- July 2011
- January 2011

- 3d
- algorithms
- aphasia
- art
- blackbox
- blender
- buster
- code
- courses
- cs145
- cs245
- cs318
- cs330
- cs352
- cs396
- cs436
- cs455
- cs491 mobile
- exams
- experiments
- failures
- fall 2011
- fall 2012
- fall 2013
- fall 2014
- fall 2015
- fall 2016
- fish vision
- gallery
- gamedev for learning
- gamedev_cse
- gamedev2
- gamedev3
- games
- git
- graphics
- honors 304.503
- honors gamedev
- howto
- keystrokes
- labs
- lectures
- madeup
- meta
- mobile
- mutt
- nature
- nbsn
- outreach
- pop computer science
- postmortems
- programming languages
- public
- ratorvaders
- reader animated
- reading
- research
- responses
- semesters
- software
- specchecker
- specifications
- spring 2012
- spring 2013
- spring 2014
- spring 2015
- spring 2016
- spring 2017
- talks
- teaching
- travel
- Uncategorized
- unity
- vim
- writing
- wrong number

## Leave a Reply