Welcome + Haskell Ramp-Up

Reduction, values, types, expressions, function definitions

Haskell Ramp-Up (Part 2)

Algebraic data types, type classes

Domain-Specific Languages (DSLs)

Modules, abstract data types, shallow + deep embedding of DSLs

Lazy Evaluation

Reduction, weak head normal form (WHNF), infinite lists

[updated Dec 5, 2019: simplified isort]

Functors and Applicatives

Haskell's type classes Functor and Applicative (also: kinds and Monoids)

Monads

Haskell's type class Monad, the "programmable semicolon"

The Hello, World! of Haskell.

1. Compile with Haskell compiler ghc via ghc --make chewie.hs, execute on the command line with ./chewie.
2. Load into REPL ghci via ghci chewie.hs, then evaluate function main.

Prime number test. Efficient thanks to lazy evaluation of factors (a comparison with the empty list [] can be decided once the first element of factors has been found).

Demonstrates the definition of user-defined operator ~=~.

Compute the factorial n! of natural number n. Defines two equivalent variants of the function that demonstrate the use of conditional expressions (if...then...else...) and guards.

Two equivalent formulations of an efficient power computation. Demonstrates the use of guards, local definitions (where, let … in) and explicit layout syntax using {,} and;.

A demonstration of type synonyms (type t₁ = t₂) and list processing (determine the bit list of an Integer value).

A reimplementation of the sum built-in function: sum all elements of a list. Two formulations: guards and pattern matching.

A reimplementation of the built-in take function: extract a prefix (of given length) from a list.

An implementation of MergeSort in Haskell. Builds on the merge function developed in the lecture.

Definition of and functions over sum data types (Weekday, Move, Outcome). Uses deriving to define basic operations like equality, ordering, showing, ...

Definition and functions over product type Sequence.

Defines algebraic data type List a and shows that it is isomorphic to the builtin type constructor [a]. Uses lifting to lift regular list-processing functions from [a] to List a.

Defines abstract syntax trees for simple arithmetic expressions Exp a and implements an interpreter (≡ evaluation function eval), compiler (compile) and mini stack-based virtual machine (run).

Interpreter as well as compiler and VM are related:

∀ e :: Num a => Exp a: (run [] . compile) e == eval e

Function searchFor performs a lookup in a key/value-dictionary, provided that the key type supports equality comparisons.

(An equivalent function is already built into Haskell's Prelude: lookup.)

First version of the IntegerSet DSL with fully exposed implementation details. 🙁

Imports module SetLanguageShallow (or SetLanguageShallowCard) to demonstrate that representation details remain hidden.

Re-implementation of the IntegerSet DSL with representation details (characteristic functions with type Integer -> Bool) hidden inside a module.

Module is imported by set-language-shallow.hs.

A shallow embedding of IntegerSet based on characteristic functions. This module includes a cardinality observer for sets.

Imports module SetLanguageDeep (or SetLanguageDeepCard) to demonstrate a deep embedding of the integer set DSL.

A deep embedding of IntegerSet.

A deep embedding of IntegerSet. This module includes a cardinality observer for sets.

A simple deeply embedded DSL over values of type Integer and Bool. Permits the construction of il-typed expressions.

Imports module ExprDeep and builds one well-typed and one ill-typed expression.

Uses GADTs to define a deeply embedded DSL over Integer and Bool values that detects ill-typed expressions at compile time.

Imports module ExprDeepGADTTyped and demonstrates the well-typed construction and evaluation of expressions.

Define type class Expr a that describes a simple language over Integers with let...in-bindings. Three instances of this class define two shallow and one deep embedding of this language.

[ Additional material — not discussed in the lecture. ]

Imports module ExprEmbeddings to test all three instances of the Expr a language.

[ Additional material — not discussed in the lecture. ]

Defines a DSL that describes string patterns. Pattern matching returns (a possible empty) list of matches:

type Pattern a = String -> [(a, String)]
                    ↑        ↑     ↑
                input     result   residual string

Imports module PatternMatching to test-drive the pattern matchers.

Demonstrates that normal order reduction finds the normal form of an expression regardless of the presence of undefined values (function bomb has value ⊥).

Uses trace (module Debug.Trace) to demonstrate that Haskell employs graph reduction (redex sharing) during evaluation.

Demonstrates the strict semantics of pattern matching in Haskell.

Implements list minimum as the composition head . isort to demonstrate that lazy evaluation (to WHNF) can make declarative specifications of algorithms efficient to execute.

Caveat: this depends on the interaction of head and isort and does not work for arbitrary sorting algorithms.

Modular program whose parts communicate via infinite lists.

Approximate the square root of x using the Newton-Raphson series. Composes iterate with within, where the latter inspects a finite prefix of the potentially infinite list generated by the former. Haskell's evaluation to WHNF glues both together so that a result is produced in finite time.

Modular program whose parts communicate via infinite lists.

Approximate the square of function f within interval [x₁,x₂]. Divide the interval until f is close to linear in the subdivision. Keep subdividing until the sum of subdivided integrals converges. Interval subdivision (subdivide) keeps generating new integral approximations until test within decides that we have reached the desired accuracy.

Demonstrates the use of partially applied binary type constructors to form new unary type constructors:

type Flagged = (,) Bool

Builds on the fact that Either String is an instance of Functor to build a composition of functions that propagates error messages.

Use a growing chain of fmap compositions to "reach into" and manipulate a complex value at desired depth in a nested value build out of functors.

Defines a Functor instance for an algebraic data type (a deeply embedded DSL over Booelans) and demonstrates that functor laws are satisfied/violated when we get the implementation of fmap right/wrong.

Use Haskell's newtype to create specific variants of existing types. No runtime overhead!

(Module) Represent computations that are accompanied with an error context. Defines Functor and Applicative instances.

Uses module Validation.hs to perform username/password validation that is not cluttered with error log accumulation.

Defines the (>=>) left-to-right composition operator (Kleisli composition) for partial functions of type a -> Maybe b and puts that to use.

Defines the (>=>) left-to-right composition operator (Kleisli composition) for exception-generating functions of type a -> Exc b ≡ a -> Either Error b and puts that to use.

Defines the (>=>) left-to-right composition operator (Kleisli composition) for stateful functions of type a -> ST b ≡ a -> State -> (State, b) and puts that to use.

Define a composition based on partial functions a -> Maybe b based on the Monad instance for Maybe. Sequencing is based on monadic bind ((>>=)). Compare this to file sequence-Maybe.hs.