wiki/haskell/courses/upenn_cs194/week_1.page

---
title: Week One Notes
toc: no
format: markdown
...

# Week One - Haskell Basics

## What Is Haskell?

  * Created in late 1980s by academics
  * Functional
  * Pure
  * Lazy
  * Statically Typed

## Course Themes

  * Types
  * Abstraction
  * Wholemeal Programming

## Literate Haskell

  * Only lines preceded by '>' are code
  * All other lines are comments

## Declarations of Variables

~~~ {.haskell}
x :: Int
x = 3
~~~

  * Declares a variable `x` of type `Int`
  * Defines the value of the variable `x` to be `3`
  * `=` is *definition*, not *assignment*
  * variables are just names for values

## Basic Types

  * `Int` - Machine-sized integers
  * `Integer` - Arbitrary-precision integers
  * `Double` - Double-precision floating point
  * `Bool` - Booleans
  * `Char` - Unicode characters
  * `String` - Lists of characters with special syntax

## GHCi

  * A Haskell Read Eval Print Loop (REPL)
  * `:load` - load a haskell file
  * `:reload` - reload the file
  * `:type` - return the type of an expression
  * `:?` - give a list of commands

## Arithmetic

  * Infix operators, `+`, `-`, `*`, `\`, `^`
  * Negation needs parens: `(-3)`
  * `div` for integer division
  * `mod` for integer remainder
  * Backticks turn named functions to infix operators
  * Operands must have the same type - no implicit coercion
  * `fromIntegral` converts from any integral type to any numeric type
  * `round`, `floor`, `ceiling` convert from floating point numbers to
    Int or Integer

## Boolean Logic

  * Type is `Boolean`
  * Infix operators: `&&`, `||`
  * `not` for negation
  * Equality comparison: `==`, `/=`
  * Order comparison: `<`, `>`, `<=`, `>=`
  * Conditional: `if` *boolean* `then` *t_exp* `else` f_exp*
  * Both *t_exp* and *f_exp* must have the same type

## Defining Basic Functions

  * Definition by cases
  * `sumtorial :: Integer -> Integer` means "function from Integer to
    Integer"
  * Clauses are checked from top to bottom, first match chosen
  * Values must be the same to match, variables match anything
  * Choice by Boolean expression can be made by *guards*
  * `otherwise` is a synonym for `True`
  * Don't use conditional or guards to pick `True` or `False`; just
    use the conditional directly

## Pairs

  * Syntax for type and value is `(` *x* `,` *y* `)`
  * Types of *x* and *y* don't have to be the same
  * Extract values via pattern-matching
  * *n*-tuples for *n* > 2 also exist, but recommend against them

## Using Functions, Multiple Arguments

  * Application via juxtaposition of function with arguments.
  * Multi-argument function types look like `Int -> Int -> Int -> Int`
  * Reason for the arrows to be revealed later
  * Function application is **higher precedence** than any infix
    operators

## Lists

  * List types look like `nums :: [Integer]` which is a "list of Integers"
  * List value syntax sugar: `[1,2,3]`
  * Ranges: `[1..100]`; `[2,4..100]` enumerates only evens
  * Type `String` means the same as `[Char]`
  * Value `"hello"` means the same as `['h','e','l','l','o']`

## Constructing Lists

  * Empty list: `[]`
  * *cons* operator: *x* `:` *xs* where *xs* is a list of values of
    the same type as *x*, possibly the empty list.
  * Value `[2,3,4]` is the same as `2 : 3 : 4 : []`

## Functions on Lists

  * Define by cases; one for empty list, the other for a cons operator
  * The pattern `_` can be used in place of a variable when the value
    won't be used.

## Combining Functions

  * Build complex functions by combining simple ones
  * Lazy evaluation means list elements are only calculated as needed
  * Don't be afraid to write small functions that transform entire
    structures and combine them; it's not as inefficient as it might
    seem

## A Word About Error Messages

  * **Don't fear error messages**
  * How to interpret type match errors

# Homework Assignment

The first problem involves validating credit card numbers.

  1. Find the digits of a number; write the functions:

    ~~~ {.haskell}
    toDigits    :: Integer -> [Integer]
    toDigitsRev :: Integer -> [Integer]
    ~~~

  2. Double every other digit *from the right*

    ~~~ {.haskell}
    doubleEveryOther :: [Integer] -> [Integer]
    ~~~

  3. Sum the digits

    ~~~ {.haskell}
    sumDigits :: [Integer] -> Integer
    ~~~

  4. The number is valid iff the remainder when the sum is divided by
     10 is 0

    ~~~ {.haskell}
    validate :: Integer -> Bool
    ~~~

The second problem is to solve the Towers of Hanoi puzzle.

~~~ {.haskell}
type Peg = String
type Move = (Peg, Peg)
hanoi :: Integer -> Peg -> Peg -> Peg -> [Move]
~~~