PowerPoint Presentation
Time and Space Complexity in Functional Programming, Part Two
Introduction to the Lambda Calculus
CS 345
Lecture 11
Functional programming
invites certain problems!
Recursion can cause…
Stack overflow!
Always passing data around as arguments to functions (instead of mutating it) leads to…
Copies, copies everywhere!
Only using recursive data structures (linked lists) leads to…
0(n) lookup times in linked lists compared to O(1) lookup times in arrays!
Functional languages also offer
unique solutions to these problems
To the problem of stack overflow:
Tail call recursion, and
tail call optimization
To the problem of excessive data copying, and O(n) lookup times:
Persistent data structures
Lists Arrays (“vectors”)
Implementation: A series of pairs where the cdr of one pair points to the rest of the list. A single contiguous block of memory cells with a fixed length.
Set or get the kth item:
Insert or delete an item at the beginning:
Inserting or deleting an item at position k:
Length:
Lists Arrays (“vectors”)
Implementation: A series of pairs where the cdr of one pair points to the rest of the list. A single contiguous block of memory cells with a fixed length.
Set or get the kth item: O(k) repeated cdrs. O(1) direct access.
Insert or delete an item at the beginning:
Inserting or deleting an item at position k:
Length:
Get the kth item:
let’s write it in Racket
Lists Arrays (“vectors”)
Implementation: A series of pairs where the cdr of one pair points to the rest of the list. A single contiguous block of memory cells with a fixed length.
Set or get the kth item: O(k) repeated cdrs. O(1) direct access.
Insert or delete an item at the beginning: O(1) cons or cdr. O(n) copy to a new and larger array.
Inserting or deleting an item at position k: O(k) to get to correct location, then cons or cdr. O(n) to copy to a new and
larger array.
Length: O(n) to count all cars. O(1) fixed at creation.
So, should you not program functionally (in certain cases)?
Well… as a practical reality…
Most real-life programs are multi-paradigm
Racket does offer arrays (called vectors) and even mutation (using set!), so you can appeal to them for efficiency, where it makes sense.
You can often gain many benefits of the functional paradigm, even in a strictly imperative language, by:
Avoiding state mutation
Writing “pure” functions
You can work with functional lists in, say, Racket, but remain mindful of performance issues with your algorithms
Cons-ing items to the head of the list is efficient, so you could prefer that, and then reverse the list as a final step if you need items in another order.
But! This is also really cool…
Recent functional programming languages (Clojure, Haskell) have innovated on the underlying implementation of vectors and other kinds of collections to maintain the core functional principle of immutability, while still improving time and space efficiency:
Persistent data structures
Immutability can have downsides
In a purely functional language (one which does not even allow “destructive updates”), data structures must be immutable
once created, they can’t be changed
Immutable data structures only modify their values by copying new values into a brand new data structure
could be space and time inefficient!
Clojure example
Persistent Data Structures
Persistent data structures are immutable; but also, when they are copied, they preserve old versions of themselves
This data preservation is so clever that it even boosts time and space efficiency
How persistent data structures work
Use trees to represent lists (and other data structures)
Update values using path copying
Refer to unchanged values using structural sharing
Introduction to
the Lambda Calculus
/docProps/thumbnail.jpeg