Notes from 9 Sep

The repl.it environment requires there to be a main function, even if you only want to experiment with other functions. This isn’t too much of a problem, you can just define

main = putStrLn "Okay"

but the minimal main function is actually

main = return ()

so use that as a placeholder if you don’t need it to do anything at all.

This refers to specifying an infix operator with only one argument, which then becomes a function of the other argument. For example:

• (/3) is a section of the division operator, where the numerator is the next argument.
• (3/) is also a section of the division operator, but now the denominator is the next argument.

Usage:

λ> boo = (/3)
λ> moo = (3/)
λ> boo 10
3.3333333333333335
λ> moo 10
0.3
λ> boo 12
4.0
λ> moo 12
0.25

We can define functions this way, without ever referring to the arguments:

half = (/2)
square = (**2)
twice = (*2)

In algebra, we sometimes use a small circle as an operator that can compose two functions. The rule is:

\[ (f\circ g)(x) = f(g(x)) \]

So it’s like a pipeline of the two functions – first apply \(g\) to the argument \(x\), and then apply \(f\) to that result. So if:

\[ f(x) = 2x+1 \]

and

\[ g(x) = \sqrt{\frac{x}{2}} \]

Then:

\[ (f\circ g)(x) = 2\sqrt{\frac{x}{2}} + 1\]

and:

\[ (g\circ f)(x) = \sqrt{\frac{2x+1}{2}} \]

Note that the function to the right of the operator is applied first!

In Haskell, the function composition operator is a single dot (period) character. We usually put spaces around the dot, although that isn’t strictly necessary. Here are some examples:

λ> (half . square) 10
50.0
λ> (square . half) 10
25.0
λ> (square . half . square) 10
2500.0
λ> (half.square.half) 10
12.5

In some situations, it may be more intuitive for a sequence of functions to be applied left-to-right instead of right-to-left. We can define a different composition operator for that purpose, simply like this:

(|>) = flip (.)

The pre-defined flip function takes any function with two parameters and switches the order of the parameters:

λ> (-) 9 2
7
λ> flip (-) 9 2
-7

Once we flip the composition operator, the function on the left will be applied first:

λ> (half |> square) 10
25.0
λ> (square |> half) 10
50.0
λ> (square |> half |> square) 10
2500.0
λ> (half |> square |> half) 10
12.5

For symmetry, we can provide an alias for composition in the standard right-to-left order:

(<|) = (.)

Functions can be defined with multiple clauses – different expressions that apply to different cases. One way to do this is with pattern guards, which are introduced with a pipe/bar character (|) before the equals sign:

collatz n
  | even n = n `div` 2
  | otherwise = 3*n + 1

Following each bar is a Boolean expression, called a guard. The first guard that results in True indicates the expression that is will be executed. The keyword otherwise will match if no previous guard matched.

Here are some derivations using the sample function above:

collatz 18 ↪
  -- plug in 18 for n in the guards
  -- evaluate: even 18 ↪ True
18 `div` 2 ↪
9

collatz 5 ↪
  -- plug in 5 for n in the guards
  -- evaluate: even 5 ↪ False
  -- move on to otherwise case
3*5 + 1 ↪
15 + 1 ↪
16

Let’s define a few more numeric functions this way:

fact n
  | n < 0 = error "Negative argument"
  | n == 0 = 1
  | otherwise = n * fact (n-1)

pow x n
  | n < 0 = error "Negative argument"
  | n == 0 = 1
  | otherwise = x * pow x (n-1)

The error function signals a run-time error. It will look something like this:

*** Exception: Negative argument
CallStack (from HasCallStack):
  error, called at <interactive>:60:1 in interactive:Ghci44

In Haskell we usually try pretty hard to avoid generating run-time errors. Later we can explore some techniques for ensuring they don’t happen.

Let’s attempt to derive the values of expressions using these guarded recursive functions.

fact 5 ↝
  -- substitute 5 for n in guards
  -- evaluate: 5 < 0 ↝ False
  -- evaluate: 5 == 0 ↝ False
  -- move on to otherwise case
5 * fact (5-1) ↝    -- just arithmetic
5 * fact 4 ↝
  -- substitute 4 for n in guards
  -- evaluate: 4 < 0 ↝ False
  -- evaluate: 4 == 0 ↝ False
  -- move on to otherwise case
5 * 4 * fact (4-1) ↝          -- arithmetic
5 * 4 * fact 3 ↝              -- otherwise case
5 * 4 * 3 * fact 2 ↝          -- arithmetic, otherwise
5 * 4 * 3 * 2 * fact 1 ↝      -- arithmetic, otherwise
5 * 4 * 3 * 2 * 1 * fact 0 ↝  -- arithmetic
  -- evaluate: 0 < 0 ↝ False
  -- evaluate: 0 == 0 ↝ True, use that case
5 * 4 * 3 * 2 * 1 * 1 ↝
20 * 3 * 2 * 1 * 1 ↝
60 * 2 * 1 * 1 ↝
120 * 1 * 1 ↝
120 * 1 ↝
120

pow 2 6 ↝
2 * pow 2 5 ↝
2 * 2 * pow 2 4 ↝
2 * 2 * 2 * pow 2 3 ↝
2 * 2 * 2 * 2 * pow 2 2 ↝
2 * 2 * 2 * 2 * 2 * pow 2 1 ↝
2 * 2 * 2 * 2 * 2 * 2 * pow 2 0 ↝
2 * 2 * 2 * 2 * 2 * 2 * 1 ↝
4 * 2 * 2 * 2 * 2 * 1 ↝
8 * 2 * 2 * 2 * 1 ↝
16 * 2 * 2 * 1 ↝
32 * 2 * 1 ↝
64 * 1 ↝
64

Exercise: why is it helpful to have a case for n < 0 in these functions? What happens if we omit that case and we try to evaluate fact (-1)?

For the palindrome function, you basically need reverse and the equality operator (=)= (double equals, like in many programming languages). The reverse function just reverses the order of a list (or string):

λ> reverse [1..4]
[4,3,2,1]
λ> reverse "liart"
"trail"

Here are some of the operators that generate Booleans:

• && is the logical AND (same as in C++)
• || is logical OR (same as C++)
• not is logical negation (! in C++)
• == is equality of two values (same as C++)
• /= is not-equals (!= in C++)
• <=, <, >, >= are inequality operators, as in C++
• even and odd take integers and return True if they are even/odd respectively.

To manipulate characters for the rot13 problem, we need to add or subtract 13 from a character. You can’t directly add a character and an integer (like in C), but you could apply succ or pred 13 times:

λ> ( succ . succ . succ . succ . succ . succ . succ . succ
   . succ . succ . succ . succ . succ) 'F'
'S'

Of course, that’s pretty ugly. A more elegant way is to use ord and chr from Data.Char module, to convert to integer and back:

Then you can add in between:

λ> ord 'F'
70
λ> chr 70
'F'
λ> chr (ord 'F' + 13)
'S'

The other thing we’ll need for rot13 is to determine if the letter is in the front half or back half of the alphabet. The elem function is a good tool for that, it simply determines whether an element is contained in a list:

λ> elem 5 [1..10]
True
λ> elem 10 [1..5]
False
λ> elem 'k' "apple"
False
λ> elem 'p' "apple"
True
λ> elem 'S' ['N'..'Z']
True