Functional Programming Notes

Motivation

• Software development is hard; functional programming aims to make it easier.
• Functional programming focuses on writing programs that emphasize meaning over action.
• Aims for programs that are easy to read, understand, maintain, and modify.
• Functional programs are easy to debug and test due to the absence of global variables.
• Enables examining components separately, promoting self-documenting code and easier optimization.

Functional Programming Languages

• Haskell is used in this module.
• Alternative languages include Scheme and ML.
• Functional programming can be done in any language but might not be efficient.
• Examples in C#:
  • C# 3.0: Lambda expressions
  • C# 7.0: Pattern matching
  • C# 12.0: Set comprehension

Haskell

• 1987: Development of Haskell, a standard lazy functional language, began.
• 1990s: Type classes and monads were developed.
• 2003: Haskell Report was published defining a stable language.
• GHC (Glasgow Haskell Compiler) is both an interpreter and compiler.
• Hugs is an interpreter.
• NHC is a compiler.

What is Functional Programming?

• A programming paradigm that treats computation as the evaluation of mathematical functions.
• Avoids changing state and mutable data.
• Opposite of imperative programming.
• Denotative programming: Self-documenting code.

Statelessness

• Calculates internal state without directly mutating it.
• Allows for complete referential transparency: same inputs, same output.
• Facilitates easier parallelization.

Evaluation

• Eager evaluation: expressions are evaluated immediately when bound to a variable
• Lazy evaluation: expressions are evaluated only when their values are needed and depending upon a defined evaluation strategy.

Statically Typed

• The compiler knows the type of each piece of code at compile time.
• Catches many potential errors during compilation.

Comments in Haskell

• Single-line comments: -- comment
• Multi-line comments: {- comment -}

Naming Requirements

• Function and argument names must begin with lowercase letters.
• List arguments often have an s suffix (e.g., xs, ns).
• Definitions in a sequence must begin in the same column.
• The layout rule avoids explicit syntax for grouping definitions.

Basic Data Models

• Numbers
• Characters
• Boolean
• List and List Comprehension
• Tuple

Numbers and Types

• Haskell infers the type of numbers.
• Type declarations use ::.

Characters

• Represented using single quotes.
• Strings are lists of characters.

String

• A collection of characters represented with double quotation marks.

Boolean

• True and False
• Haskell is case-sensitive (true is different from True).

List

• Lists are homogeneous; all elements must be of the same type.
• Example: [1,2,3,4,5]

List Comprehension

• Uses mathematical notation to construct new lists from old lists.
• Example: [x^2 | x <- [1..5]]

Comprehensions

• x <- [1..5] is a generator.
• Multiple generators can be used, separated by commas.
• Changing the order of generators changes the order of elements.

Dependant Generators

• Later generators can depend on earlier generators.
• Example: [(x,y) | x <- [1..3], y <- [x..3]]

Tuple

• Tuples are immutable and can contain different types of data.
• Represented by single parentheses: (1, 1, 'a')

Functions

• Functions are usually prefix.
• Called using the function name followed by parameters, separated by spaces.
• Example: min 3 4

Boolean Operators

• < (less than)
• > (greater than)
• <= (less than or equal to)
• >= (greater than or equal to)

Recap: Naming Requirements

• Function and argument names must begin with a lowercase letter.
• List arguments usually have an s suffix.

Recap: The Layout Rule

• Definitions must begin in the same column.
• Avoids explicit syntax for grouping definitions.

Recap: Set Comprehensions

• Uses mathematical notation to construct new sets from old sets.
• Example: {x^2 | x ∈ {1...5}}

Syntactic sugar

• https://en.wikibooks.org/wiki/Haskell/Syntactic_sugar

Recap: Lists comprehension

• [x^2 | x  [1..5]]

Recap: List comprehension

• > [(x,y) | x  [1,2,3], y  [4,5]]

Generators

• > [(x,y) | y  [4,5], x  [1,2,3]]

Dependant Generators

• [(x,y) | x  [1..3], y  [x..3]]

Function Application

• In Haskell, function applications are denoted using space, and multiplication is denoted using *.
• Example: f a b + c*d
• Function applications have higher priority than other operators.

Haskell Scripts

• New functions are defined within a script (text file with .hs suffix).
• Use an editor and GHCi to develop scripts.
• Use :reload command in GHCi to update the script.

Useful GHCi Commands

• :load name: load script
• :reload: reload current script
• :set editor name: set editor
• :edit name: edit script
• :type expr: show type
• :?: show all commands
• :quit: quit GHCi

Guards

• List comprehensions can use guards to restrict values.
• Example: [x | x <- [1..10], even x]

The zip function

• zip :: [a]  [b]  [(a,b)]
• > zip [’ a ’ , ’b’ , ’ c ’] [1,2,3,4]
• [(’ a ’,1),(’b’,2),(’ c ’,3)]

Functional Programming Principles

• Opposite of imperative programming.
• Pure functions return the same result for identical calls.
• Statelessness: no global or hidden variables.

Types in Haskell

• Type: a name for a collection of related values.
• Type error: applying a function to arguments of the wrong type.
• e :: t: expression e has type t.
• Type inference: automatic calculation of type at compile time.
• Type errors are found at compile time.

Basic Haskell Types

• Bool: logical values (True, False)
• Char: single characters
• String: strings of characters
• Int: fixed-precision integers
• Integer: arbitrary-precision integers
• Float: floating-point numbers

List Types

• [t]: type of lists with elements of type t.
• The type of a list says nothing about its length.

Tuple Types

• (t1, t2, ..., tn): type of n-tuples.
• The type of a tuple encodes its size.

String

• String comprehensions
• `