Haskell

Algebraic Data Types and Pattern Matching

ADTs allow you to define your own data structures. Pattern matching lets you deconstruct them elegantly.

data Maybe a = Nothing | Just a
 
safeHead :: [a] -> Maybe a
safeHead []    = Nothing
safeHead (x:_) = Just x

Recursive ADTs enable trees and more:

data Tree a = Leaf | Node a (Tree a) (Tree a)
 
treeSum :: Tree Int -> Int
treeSum Leaf = 0
treeSum (Node v l r) = v + treeSum l + treeSum r

Typeclasses and Instances

Typeclasses define interfaces; instances implement them for specific types.

class Eq a where
  (==) :: a -> a -> Bool
 
instance Eq Bool where
  True  == True  = True
  False == False = True
  _     == _     = False

You can create your own typeclasses and derive instances:

class Pretty a where
  pretty :: a -> String
 
instance Pretty Int where
  pretty = show

Functors, Applicatives, and Monads

Functor

A type that can be mapped over.

instance Functor Maybe where
  fmap _ Nothing  = Nothing
  fmap f (Just x) = Just (f x)

Laws:

fmap id = id
fmap (f . g) = fmap f . fmap g

Applicative

Allows function application within a context.

instance Applicative Maybe where
  pure = Just
  Nothing <*> _ = Nothing
  (Just f) <*> mx = fmap f mx

Laws: Identity, Homomorphism, Interchange, Composition

Monad

Allows sequencing of computations with context.

instance Monad Maybe where
  return = Just
  Nothing >>= _ = Nothing
  (Just x) >>= f = f x

Laws: Left identity, Right identity, Associativity

Idioms:

Use do notation for readable monadic code.
Use monads for error handling (Maybe, Either), side effects (IO), state (State), etc.

Monad Transformers

Combine effects from multiple monads.

import Control.Monad.Trans.Maybe
import Control.Monad.Trans.Class (lift)
 
findUser :: UserId -> MaybeT IO User
findUser uid = do
  mUser <- lift $ queryDatabase uid
  MaybeT $ return mUser

Stacking transformers allows you to handle, for example, IO and error handling together.

Property-Based Testing

Test properties for a wide range of inputs using QuickCheck.

import Test.QuickCheck
 
prop_sortIdempotent :: [Int] -> Bool
prop_sortIdempotent xs = sort (sort xs) == sort xs
 
-- Custom generator
genEven :: Gen Int
genEven = (*2) <$> arbitrary
 
prop_evenIsEven :: Property
prop_evenIsEven = forAll genEven even

Parser Combinators

Build complex parsers by combining simple ones.

import Text.Parsec
import Text.Parsec.String (Parser)
 
number :: Parser Int
number = read <$> many1 digit
 
commaSepNumbers :: Parser [Int]
commaSepNumbers = number `sepBy` char ','

Equational Reasoning

Prove properties and optimize code by substituting equals for equals.

Proof Example:

-- Prove: map f (map g xs) = map (f . g) xs

Optimization Example:

sum (filter p (xs ++ ys))
= sum (filter p xs ++ filter p ys)
= sum (filter p xs) + sum (filter p ys)

Evaluation Strategies

Haskell uses lazy evaluation by default.

naturals = [0..]         -- Infinite list, only evaluated as needed
take 5 naturals          -- [0,1,2,3,4]

Strictness:

sum' :: [Int] -> Int
sum' = go 0
  where
    go !acc []     = acc
    go !acc (x:xs) = go (acc + x) xs

Use seq or bang patterns to force evaluation and avoid space leaks.

Referential Transparency

Referential transparency is a property of expressions in programming and mathematics. An expression is referentially transparent if it can be replaced with its value without changing the program’s behavior.

Definition

An expression is referentially transparent if, whenever it appears in a program, it can be replaced by its result (value) without affecting the program’s meaning or outcome.

Example

-- This function is referentially transparent
add x y = x + y
 
-- The expression (add 2 3) can always be replaced with 5

In the above example, add 2 3 will always yield 5, no matter where or when it is evaluated.

Importance

Predictability: Code is easier to reason about, test, and debug.
Optimization: Compilers can safely cache or reorder computations.
Parallelism: Independent computations can be executed in parallel without side effects.

Contrast: Referential Opacity

If an expression’s value can change depending on context (e.g., due to side effects or mutable state), it is referentially opaque.

# Not referentially transparent
import random
def get_random():
    return random.randint(1, 10)
 
# get_random() may return different values each time

In Functional Programming

Referential transparency is a core concept in functional programming. Pure functions (without side effects) are referentially transparent, enabling many of the benefits of functional languages.

Quartz 4

Explorer