# Lists

`[1,2,3]` is syntactic sugar for `1:2:3:[]`. `[]` is an empty list.

Use `!!` to get an element out of a list by index

``````[1,2,3] || 0
--> 1
``````

To combine lists, use `++`. This will put the 2nd list on the end of the first list.

``````['w','o'] ++ ['o','t']
``````

Note: the `++` operator will need to walk thru all elements in list on left side.

To put something on the beginning of a list, use the `cons` operator `:`

``````'w' : ['o','o','t']
'w' : "oot"
``````

Note: putting element on front of list is instantaneous

## Common List Functions

``````[3,2,1] > [2,1,0]
True

[3,2,1] > [2,1,100]
True

[3,4,2] > [3,4]
True

[3,4,2] == [3,4,2]
True

5

tail [5,4,3]
[4,3]

last [5,4,3]
3

init [5,4,3]
[5,4]

length [5,4,3]
3

null [1,2,3]
False

null []
True

reverse [5,4,3,2]
[2,3,4,5]

take 3 [5,4,3,2]
[5,4,3]

-- take 0 get an empty list
take 0 [5,4,3]
[]

-- take more than elements than in the list, the list is returned
take 5 [1,2]
[1,2]

maximum [5,7,3,2]
7

minimum [5,7,3,2]
2
``````

Other list fn's: `sum`, `product`, `elem`

# Not Equals

use `/=` (unlike most other languages that use `!=`)

``````> 13 /= 13
False
``````

# Ranges

``````-- even numbers
[2,4..20]

-- lowercase letters
['a'..'z']

-- decrementing list
[20,19..1]

-- infinite lists
take 10 [13,26..]
[13,26,39,52,65,78,91,104,117,130]
``````

See also: `cycle`, `repeat`, `replicate`.

# Data Types (a.k.a Algebraic Data Types)

## Notation

The notation `v :: T` means that v is a value in the Type T. v "has the type" T.

``````False :: Bool
True  :: Bool
not   :: Bool --> Bool
``````

## Basic Types

• `Bool` :: can be `True` or `False`
• `Char` :: a list of chars is a string
``````'a', 'A', '3', '_'
``````
• `String` :: a list of chars
``````"abc", "1+2=3"
``````
• `Int`, Fixed Precision Int :: The Hugs system supports int values in the range of -231 to 231-1.
• `Integer`, Arbitrary Precision Int :: use as much memory as necessary for their storage. Slower performance than Fixed Precision, but no limits.
• `Float` :: a real floating point with single precision
• `Double` :: a real floating point with double the precision
• Lists :: Lazily evaluated so it's not uncommon for a list to have infinite length. The syntax [1,2,3,4] is shorthand. Under the hood, the literal syntax for lists is `(1 : (2 : (3 : (4 : []))))`. The colon `:` means `construct` or `cons`.
• Tuples :: Tuples can contain any number of components which is called arity. Tuple with 0 arity is the empty tuple, tuples with arity two are called pairs, tuples of arity 3 are called triples. Tuples with arity 1 are not valid (because parens are used to disambiguate operator precedence). Tuples must have finite arity.

## Type Variables

Type Variables are sort of like generics in other languages. Functions that have Type Variables are called `polymorphic functions`.

``````> :t head
``````

Type variables must be lowercase. They can be longer than a single letter, but usually single chars are used.

## Typeclasses

Sort of like an interface that defines some behavior. Think of them like Java Interfaces, but better.

``````> :t (==)
(==) :: Eq a => a -> a -> Bool
``````

Everything before `=>` is called a `class constraint`.

## Common Typeclasses

• `Eq` :: members implement `==` and `/=`
• `Ord` :: types that have ordering. `Ord` covers all the comparison functions (`<`, `>`, `<=`, and `>=`)
• `Show` :: the `show` presents things as strings
• `Read` :: the `read` function takes a string and returns a member of `Show`
• `Enum` :: members are sequentially ordered types. Can use `Enum` types in ranges
• `Bounded` :: members have upper and lower bound. Use `minBound` and `maxBound`
• `Num` :: numeric typeclass. Members can act like numbers. Members of `Num` must also be members of `Show` and `Eq`. Members include `Int`, `Integer`, `Float`, and `Double`
• `Integral` :: includes whole numbers. `Int` and `Integer` are members of `Integral` typeclass.
• `Floating` :: Includes types `Float`, and `Double`

## Explicit Type Annotations

The `read` function can't infer which type you want when you do something like `read "4"`. Do you want a Int? Integer? Char? Double?

Use explicit type annotations like so

``````read "4" :: Int
``````

## Number Conversions

It's possible to write a function that uses an argument that must have 2 conflicting types (such as Integral and Fractional). It took me a while to understand why this didn't work. Here's my stack overflow post.

What's the difference between Num and Integral? Awesome explanation here: https://www.haskell.org/tutorial/numbers.html

The type for the function `id` is `id :: a -> a` which contains an unconstrained type variable `a`. This means this function can be used in contexts requiring `Char -> Char` or `Integer -> Integer` or many other contexts. This is referred to as "Parametric Poloymorphism".

The type class `Eq` defines the function `==`. The `lookup` function, for example, constrains the type variable `a` to be of type class `Eq` in the type definition

``````lookup :: Eq a => a -> [(a,b)] -> Maybe b
``````
This is referred to as "ad hoc" polymorphism or "overloading". Meaning that `==` is a funciton defined differently for different types.

# Data Types

One way to make new Data Types is to use `data`.

``````data Bool = False | True
``````

Types can have constructors.

``````data Shape = Circle Float Float Float | Rectangle Float Float Float Float
``````

The `Circle` value constructor has 3 Float arguments. Value constructors are functions that return value of a Data Type. This is sort of strange because Value constructors represent values of Types, not Types!

## Derived Types

Use the `deriving` keyword to associate a Data Type with a Type Class. For example:

``````data Shape = Circle Float Float Float | Rectangle Float Float Float Float deriving (Show)
``````

## Record Syntax

``````data Person = Person { firstName :: String
, lastName :: String
, age :: Int
, height :: Float
, phoneNumber :: String
, flavor :: String
} deriving (Show)
``````

All types inside value constructors must be compatible with the typeclass. For example, the person type can derive Show because String, Int, Float already implement Show.

## Data Type Constructors and Type Parameters

Sort of like generics in java

``````data Maybe a = Nothing | Just a
``````

Usually not a good idea to put type constraints in data declarations because then it might force functions to specify the type constraint even when the constraint is not applicable.

## Type Synonyms

Use `type` to associate new synonyms with existing types. This can improve intentions thru types.

For example:

``````type PhoneNumber = String
type Name = String
type PhoneBook = [(Name,PhoneNumber)]
``````

Now we can do:

``````inPhoneBook :: Name -> PhoneNumber -> PhoneBook -> Bool
inPhoneBook name pnumber pbook = (name,pnumber) `elem` pbook
``````

## Partially Apply Type Params

You can partially apply type params and get new constructors (just the same as partially applying functions)

For example:

``````type IntMap v = Map Int v
``````
is the same as:
``````type IntMap v = Map Int v
``````

## Recursive Data Type

You can define data types recursively using the new type inside the definition.

# Typeclasses

A Typeclass defines behavior. (Remember, Haskell Typeclasses are not the same as concept of classes in Java or Python). Haskell Typeclasses are more conceptually similar to clojure protocols or Java Interfaces.

Here's an example, the "Eq" Typeclass:

``````class Eq a where
(==) :: a -> a -> Bool
(/=) :: a -> a -> Bool
x == y = not (x /= y)
x /= y = not (x == y)
``````

You can either use `derives` keyword. Or, for more control, use the `instance` keyword to associate a data type with a typeclass like so:

``````data TrafficLight = Red | Yellow | Green
instance Eq TrafficLight where
Red == Red = True
Green == Green = True
Yellow == Yellow = True
_ == _ = False
``````

Note: usually, we'd have to implement both `==` and `/=`, but we can get away with only implementing `==` in this case, because the class definition shows the relationship between `==` and `/=`.

Beware of `concrete types` vs `type constructors`! Only concrete types can be used to define instances.

## Kinds

Type of a Type is a Kind. Examine the kind of type using the `:k` command in ghci. A `*` means the type is a concrete type. A concrete type is a type that doesn't have an type parameters. Values can only have types that are concrete types.

Using `:k` on a type to get it's kind is similar to using `:t` on a value to get it's type.

# Modules

## Using Modules

Here's how to import modules from `.hs` files
``````import Data.List
import Data.set
``````

Here's how to import modules from ghci

``````:m + Data.List Data.Set
``````

Import specific functions from a module

``````import Data.List (nub, sort)
``````

Import all functions except a few

``````import Data.list hiding (nub)
``````

Use `qualified` to Handle name clashes

``````import qualified Data.Map
``````

Now we can access Data.Map.filter by fully qualifying. And still have access to Prelude's `filter`.

To add an alias for a module

``````import qualified Data.Map :as M
``````

## Making Modules

A Module exports functions.

``````module Geometry.Equations
( sphereVolume
, sphereArea
, cubeVolume
, cubeArea
, cuboidArea
, cuboidVolume
) where

-- function definitions here
``````

The `dot` notation in Modules must match the directory structure.

## Exporting Type Definitions

You can include Data Types in Modules and export those as well

``````module Shapes
( Point(..)
, Shape(..)
, surface
, nudge
, baseCircle
, baseRect
) where
``````

# Handy Modules

## Data.List

`intersperse` (like join or interpose), `intercalculate` (like join or interpose for lists), `transpose` transforms 2d grid from columns to rows.

`foldl'` and `foldl1'` are strict version of the lazy `foldl` and `foldl1`.

`concat` flattens (joins) a list. It will remove one level of nesting

`concatMap` is same as first mapping a funciton and then concatenting the list.

`and`, `or`, `any`, `all` are predicates that operate on lists

`iterate` takes function and starting value and applies the function to the result.

`takeWhile`, `dropWhile` do what you expect.

`span` is kind of like `takeWhile` except it returns pair of lists. `break` will return pair of lists split at first value that returns true.

Other useful functions: `sort`, `group`, `inits`, `tails`, `find`, `elemIndex`, `partition`, `elem` and `notElem`, `partition`, and lots more!

## Data.Char

Lots of predicates

`isControl`, `isSpace`, `isLower`, `isUpper`, `isAlpha`, `isUpper`, `isAlpha`, `isAlphaNum`, `isPrint`, `isAlphaNum`, `isPrint`, `isDigit`

`toUpper`, `toLower`, `toTitle`, `digitToInt`.

## Data.Map

Hashmap like structures, a.k.a. dictionaries, a.k.a association lists, a.k.a. key-value pairs

Import like so to avoid name clashes:

``````import Data.Map as Map
``````
`Map.fromList` converts list of key value Pairs into a internaldata structure.

`Map.empty` gives an empty map

`Map.insert` takes a key and a value and a map and returns new map with the new key/value inserted

`Map.null` checks if map is empty

`Map.size` gets size of map

Some other useful functions: `singleton`, `lookup`, `member`, `map`, `filter`, `toList`, `keys`, `elems`

`fromListWith` and `insertWith` help with transforming lists of pairs that might have duplicate keys.

# Defining Functions

Functions can't begin with an uppercase letter.

When a function doesn't take parameters, it's often referred to as a definition (or a name).

## Functions associate to the left

``````f x g y
``````

means

``````(((f x) g) y)
``````

This is the opposite of type declarations, which associate to the right.

## Infix Functions

`+, *, -` are examples of infix functions. You can use them as prefix functions by surrounding them with parenthesis.

``````2 + 2
(+) 2 2
``````

## Function Application using `\$`

The `\$` operator has the lowest precedence. Normal function application (with a space) is left associative. Function application with `\$` is right associative. When `\$` is used, the expression on the right is applied as parameter to the function on it's left. So, for example, instead of this:

``````sum (map sqrt [1..10])
``````

We can write:

``````sum \$ map sqrt [1..10]
``````

`\$` can also be used to map function application across functions

``````ghci> map (\$ 3) [(4+), (10*), (^2), sqrt]
[7.0,30.0,9.0,1.7320508075688772]
``````

## Conditional expressions

In Haskell, each if/then must have a corresponding else. if/then/else statements can be nested. if/then/else are expressions (meaning they always return a value)

``````safetail1 xs = if null xs then [] else tail xs
``````

## Guarded expressions

These are sort of like case or cond statements. Otherwise always evals to True.

``````safetail4 xs
| null xs = []
| otherwise = tail xs
``````

## Pattern Matching

Patterns are tested from top to bottom, so most general patterns should come last.

``````safetail [] = []
safetail xs = tail xs

``````
Remember that pattern matching variables must be unique. But don'tconfuse this with variables inside type expressions (which can andoften are the same).

You can Pattern Match in list comprehensions too

``````ghci> let xs = [(1,3), (4,3), (2,4), (5,3), (5,6), (3,1)]
ghci> [a+b | (a,b) <- xs]
[4,7,6,8,11,4]
``````

Surround things with parens if binding multiple variables. Pattern match on lists too

``````head' [] = []
``````

## As Patterns

Place a name and a `@` in front of a pattern in order to make reusable patterns. Here's an example:

``````capital :: String -> String
capital "" = "Empty string, whoops!"
capital all@(x:xs) = "The first letter of " ++ all ++ " is " ++ [x]
``````

## Where syntax

(note that `where` is not an expression, it's syntactic sugar)

The names defined inside `where` bindings are visible across guards. And names are only available inside the function (so won't pollute global namespace).

``````initials :: String -> String -> String
initials firstname lastname = [f] ++ ". " ++ [l] ++ "."
where (f:_) = firstname
(l:_) = lastname
``````

## Let expressions

`let` bindings are similar to `where` bindings except they don't apply across all guards.

`where` is syntactic sugar. `let` is a first class expression (so they can be put anywhere).

``````ghci> [let square x = x * x in (square 5, square 3, square 2)]
[(25,9,4)]
``````

You don't need the `in` part of the `let` when in list comprehensions

``````calcBmis :: (RealFloat a) => [(a, a)] -> [a]
calcBmis xs = [bmi | (w, h) <- xs, let bmi = w / h ^ 2, bmi >= 25.0]
``````

Using `let` to bind variables is convenient from the repl.

``````ghci> let foo x y z = x * y + z
ghci> foo 3 9 2
29
``````

## Case expressions

Case expressions and pattern matching are similar. Pattern Matching can only be used in function definitions. `case` expressions can be used pretty much anywhere. Pattern matching in functions is syntactic sugar for case expressions.

``````describeList :: [a] -> String
describeList xs = "The list is " ++ case xs of [] -> "empty."
[x] -> "a singleton list."
xs -> "a longer list."
``````

# Currying and Partial Function Application

Haskell functions typically only accept a single parameter. Currying is the illusion of a function accepting multiple parameters. A function will accept a single param and return a function which accepts another param and so on.

This makes it easy to use partial function application. For example:

``````compareWithHundred :: (Num a, Ord a) => a -> Ordering
compareWithHundred x = compare 100 x
``````

`compare` is a function that accepts a single param (in this case the arg is 100) and returns a function that accepts another param (in this case, `x`). This can be re-written:

``````compareWithHundred :: (Num a, Ord a) => a -> Ordering
compareWithHundred = compare 100
``````

Now `compareWithHundred` returns a function that accepts another param.

## Sections

(I don't really understand sections, other than they are a short hand for writing functions that take a single argument?)

Infix functions can be partially applied using sections.

``````divideByTen :: (Floating a) => a -> a
divideByTen = (/10)
``````

## Lambda (Anonymous) Expressions

`\x -> x + x`

The `backslash x` is Haskell's way of expressing a λ.

``````(\x -> x + 1) 4
5 :: Integer
``````

It's also possible to define anonymous functions with arguments:

``````(\x y -> x + y) 3 5
8 :: Integer
``````

## Function Composition

A function `f(x)` composed with a function `g(x)` is the same as calling `f(g(x))`.

In Haskell, use the `.` operator to compose functions.

You can only compose functions that take same number of params

The `.` can be used to write functions in `Pointfree` style.

Note: `Pointfree` has nothing to do with points (`.`)! The `Points` in `Pointfree` has to do with the values that functions operate on.

For example:

``````-- not Pointfree
fn x = ceiling (negate (tan (cos (max 50 x))))
-- Pointfree version
fn = ceiling . negate . tan . cos . max 50
``````

# Higher Order Functions

## Useful Higher Order Functions

`map`, `filter`, `foldl`, `foldl1`, `foldr`, `foldr1`, `zipWith`

`scanl`, and `scanr` are like `foldl` and `foldr` except that they report all intermediate accumulator states.

# Recursion

2. Enumerate the cases
3. Define simple cases. Usually this will be the base cases. For example the product of empty list of numbers is 1.
4. Define other cases
5. Generalize and Simplify

# foldr

Nice way to think about `foldr` is replacing each cons operator in a list by the function `f`, and the empty list at the end by the value `v`. For example, applying the function `foldr (+) 0` to the list `1:(2:(3:[]))` gives the result `1+(2+(3+0))`

# foldr vs foldl

Note that the positional arguments for `foldl` and `foldr` have different meanings. `foldl acc next` vs `foldr next acc` where `acc` is the accumulator value.

# Dollar Sign (\$)

The \$ operator is for avoiding parenthesis. Anything appearing after it will take precedence over anything that comes before.

# List Comprehensions

``````-- doubles of all natural numbers from 1 to 10
> [x*2 | x <- [1..10]]
[2,4,6,8,10,12,14,16,18,20]
-- with a predicate
> [x*2 | x <- [1..10], x*2 > 12]
[14,16,18,20]
``````

Here's an example of using a list comprehension (and a lambda expression) to define a function named "evens".

``````evens = \xs -> [x | x <- xs, even x]
``````

List comprehensions can operate on multiple lists.

``````>  [ x*y | x <- [2,5,10], y <- [8,10,11]]
[16,20,22,40,50,55,80,100,110]
``````

# Tuples

A tuple of 2 elements is called a `pair`. A tuple of 3 elements is called a `triple`. A tuple of 4 elements is called a `4-tuple`.

``````[(1,2), (8,11), (4,5)]
``````

You can compare 2 tuples as long as they're both the same size.

Useful functions for pairs include `fst`, `snd`.

`zip` is a function that produces pairs.

``````> zip [1..] ["Bob", "Jenny", "Jake"]
[(1,"Bob"),(2,"Jenny"),(3,"Jake")]
``````

# Lazy Evaluation

There are multiple ways to evaluate an expression. Different Pieces of an expression that can be reduced are called `reducible expressions`, or, `redex` for short.

For example, the expression: `(1+2)*(3+5)` contains 3 redexes: `(1+2)`, `(3+5)`, and `(1+2)*(3+5)`.

## Innermost Evaluation (call-by-value)

One way to evaluate expressions is to evaluate from innermost redex to outermost. If there are multiple innermost redexes, then evaluate from left to right. This is called `call-by-value`.

• call-by-value is guaranteed to require the least number of reductionsteps.
• call-by-value doesn't always guarantee that an expression will terminate.

## Outermost Evaluation (call-by-name)

Another way to evaluate expressions is to evaluate from outermost redex to innermost, moving from left to right. This is called `call-by-name`.

• call-by-name has the nice property that if an evaluation can terminate, then call-by-name will ensure that it does terminate (whereas call-by-value might run infinitely).
• call-by-name might have to repeat steps, whereas call-by-value will always do the least number of steps.

But, we can work around the problem where `call-by-name` might repeat steps by storing pointers to duplicate steps (and then only having to evaluate each step once).

Haskell uses `call-by-name` in conjunction with sharing, a.k.a, lazy evaluation.

# Type Conversion

Integer to String

``````map intToDigit (take 3 (repeat 9))
``````

String to Integer

``````fst (head (reads "999" :: [(Integer, String)]))
``````

# GHCI

Display time and memory usage

``````:set +s
``````

# Hugs

## Display results of IO

See Here

``````:set +I
``````

# Compiling and Running Haskell code

``````ghc --make file.hs
``````

You can also use `runhaskell`

``````runhaskell file.hs
``````