Purely Functional Languages
Racket vs. Haskell
What do we mean by "functional"?
Think Scheme and λ-calculus
Everything is a function
A programming paradigm
Recursion and higher-order functions
What do we mean by "pure"?
A pure function has no side-effects
If we call a pure function with the same arguments, we get the same result back every time
Usually what we mean when we talk about a mathematical function [f(x) = x2]
Some examples
(define (add-one x)� (+ 1 x))
Some examples
(define (make-incrementor x)� (lambda (num) (+ num x))
Some examples
; Returns a random number uniformly�; distributed between a and b�(define (uniform a b)� (+ a � (* (random) (- b a))))
Some examples
(require racket/file)��; returns true if there are more than �; max-lines in the given file�(define (too-big? file-path max-lines)� (< max-lines� (length (file->lines file-path))))
Some examples
(define speed 10)��(define (distance time)� (* time speed))
Some examples
(print (distance 10)) ; 100�(set! speed 5)�(print (distance 10)) ; 50
What does this mean?
Clearly, Racket is not a purely functional language.
Haskell is a purely functional language:
factorial 0 = 1�factorial n = n * factorial (n - 1)
Referential transparency
Haskell has referential transparency.
x = func 35
Anywhere we see func 35 we can replace it with x
The Good
No side-effects! (strictly enforced)
Optimizations!
Infinite lists and other lazy data structures!
Parallelization! (potentially)
The Bad Interesting
Lazy evaluation
Make new lists/data structures instead of modifying old ones*
* Scheme already does this
The Ugly
Any significant program can't avoid the outside world (state):
Same inputs to same outputs is very restrictive.
... or is it?
Solution: put the state of the world in a box.
We then chain pure functions together that work on data inside of the box.
All the evils of state and the mutable world are contained (no non-pure functions needed).
Monads
Monads are a convenient abstraction to represent this "world in a box" strategy.
Example
The IO monad in Haskell with do syntactic sugar:
copyFile input output = do
contents <- readFile input
writeFile output contents
Let's de-sugar that
copyFile :: String -> String -> IO ()
copyFile input output =
readFile input >>= (\contents ->
writeFile output contents)
What's a monad exactly?
class Monad m where
return :: a -> m a
(>>=) :: m a -> (a -> m b) -> m b