Functional Languages

Chapter 11

  • First-class functions and higher order functions
  • Extensive Polymorphism
  • List types and operations
  • Garbage Collection

In modern languages, the lines between language families and often have a lot of overlap.

First-class Functions

  • Functions can be passed as values

Higher Order Functions

Functions that accept functions as parameters

setTimeout(() => console.log('1 second has passed'), 1000)

Each

  • Executes a function on each item in a list
  • Returns nothing
;[1, 2, 3].forEach(i => console.log(i))
for (i of [1, 2, 3]) {
  console.log(i)
}

Map

  • Executes a function on each item in a list
  • Returns a new list of the results
// Square a list
;[1, 2, 3].map(i => i * i)

Filter

  • Executes a function on each item in a list
  • Returns a new list containing only items where the function evaluated to true
// Remove negative numbers
;[-1, 0, 1, 2].filter(i => i >= 0)

Every

  • Executes a function on every item in a list
  • Returns true if the function always evaluates to true
// Confirm that all values are positive
;[1, 2, 3].every(i => i > 0)

Reduce

  • Executes a function on each item in a list and accumulates a single value
  • Returns the final accumulated value
// Sum values in a list
;[1, 2, 3].reduce((i, a) => i + a, 0)

Purity

  • A function is said to be “pure” if it has no side effects
  • Side effects may include changing global state or performing I/O
  • Benefits include consistency and testability
# A pure function
def fib(n):
    if n <= 1:
        return n

    return fib(n-1) + fib(n-2)

Memoization

  • We can sometimes optimize the performance of pure functions by caching their outputs
from functools import lru_cache

# By caching results, we can improve the performance of our algorithm
@lru_cache()
def fib(n):
    if n <= 1:
        return n

    return fib(n-1) + fib(n-2)

History

Lambda Calculus

  • Formal mathematical basis for computation introduced by Alonozo Church
  • Provably equivalent to a Turing Machine (see Church-Turing thesis)
  • Not a programming language, but provides framework for computation and functional programming

Lisp

  • First functional language (1958)
  • Designed by John McCarthy and implemented by others (Steve Russell created the first working interpreter)
  • Lisp is still used today in various forms (Scheme, Common Lisp, Clojure, etc)
  • Lisp influenced many other modern languages (JavaScript, Python, Ruby, etc)

Miranda and Haskell

  • Emerged in the 80s as modern functional languages
  • Haskell is open and used for functional programming research

Python

  • Emerged in 1991 and was heavily influenced by Haskell
  • Multi-paradigm language incorporating ideas from various programming languages

JavaScript

  • Created in 1995
  • Brendan Eich was hired by Mozilla to implement Scheme for use in web pages
  • This project quickly shifted to the creation of Javascript
  • Glue language with Java syntax
  • Includes first-class functions and closures

JS Example