Transcript Clojure 3

Clojure 3
Recursion, Higher-order-functions
28-Mar-16
Running Clojure

C:\Users\Dave>cd C:\Programs\clojure-1.2.0
C:\Programs\clojure-1.2.0>java -cp clojure.jar clojure.main
Clojure 1.2.0
user=> (load-file "E:/Programming/Clojure programs on E/test.clj")
#'user/fruit
user=>


IDEs for Clojure






The response, #'user/fruit, is because “fruit” was the last thing defined on this file
Clooj
Eclipse and Counterclockwise
Netbeans and Enclojure
Light Table (Instarepl)
Emacs, Textmate, Sublime Text
Comments:


A “doc” string is a string that goes just before the parameter list
Other comments start with a semicolon (;) and extend to the end of the line
Functions

The syntax to define a named function is:
(defn function_name docstring? [arguments]


The value of the function is the value of the last expression evaluated
The syntax of a function call is
(function arguments)



expressions)
Notice that the function being called is the first thing inside the parentheses
This need not be the name of a function; it can be any expression that results in a
function
A Clojure function can be overloaded (have different bodies for different
parameter lists)

Syntax:
(defn function_name docstring?
([arguments] expressions)
. . .
([arguments] expressions) )
3
Tail recursion


A recursive function is one that calls itself
A recursive function typically has three parts:
1.
2.
3.

One or more base cases that solve the simplest cases of the problem
without recurring
Recursive calls to solve subproblems that are simpler but of the same
type as the given problem
Code to augment solutions to subproblems into solutions of the given
problem
A function is tail recursive if the recursive call is the very last
thing that the function does


In other words, part 3 above is empty—no additional work need be done
If the function has multiple exits, it is tail recursive only if every
recursive call returns without doing additional work
Façades

A façade is a function that provides a different
(usually better) interface to another function


In Clojure it’s easy to define a function within
another function


Often this means supplying arguments that are only used
for initialization
This allows an “uglier” version of the function to be hidden
Functions can also be overloaded
5
Tail recursion (Erlang)

Non-tail recursive function to find the length of a list:
len([]) -> 0;
len([_ | T]) -> 1 + len(T).

Tail recursive function to find the length of a list:
len(L) -> len(0, L).
len(N, []) -> N;
len(N, [_ | T]) -> len(N + 1, T).
Tail recursion (Clojure)

Non-tail recursive function to find the length of a list:
(defn len-1 [lst]
(if (empty? lst)
0
(inc (len-1 (rest lst))) ) )

Tail recursive function to find the length of a list:
(defn len-2
([lst] (len-2 0 lst))
([n lst]
(if (empty? lst)
n
(len-2 (inc n) (rest lst)) ) ) )
recur



The previous function, len-2, is tail-recursive, but the
compiler doesn’t optimize it into a loop
Clojure runs on the JVM, which doesn’t optimize tail
recursion
Workaround:
(defn len-2
([lst] (len-2 0 lst))
([n lst]
(if (empty? lst)
n
(recur (inc n) (rest lst))) ) )
Tail recursion (Erlang)

Non-tail recursive function to find the factorial:
factorial(1) -> 1;
factorial(N) -> N * factorial(N - 1).

Tail recursive function to find the factorial:
factorial(N) -> factorial(1, N).
factorial(Acc, 1) -> Acc;
factorial(Acc, N) -> factorial(N * Acc, N - 1).
Tail recursion (Clojure)

Non-tail recursive function to find the factorial:
(defn factorial-1 [n]
(if (= n 1)
1
(* n (factorial-1 (dec n))) )

Tail recursive function to find the factorial:
(defn factorial-2
([n]
(factorial-2 1 n))
([acc n]
(if (= n 1)
acc
(recur (* n acc) (dec n)) ) ) )
Functions that take functions


Functional programming languages allow you to use a
function as a parameter to another function
Almost all functional programming languages provide
these three extremely useful functions:



map applies a function to every element of a sequence, giving
a sequence of the results
filter applies a predicate to every element of a sequence,
giving a sequence of the results
reduce (or fold) applies a binary operation “between” each
pair of elements, giving a single (non-sequence) result

There are often different versions for left- and right-associative
operations, and for providing or not providing an initial value
11
map

(def fruit '((apple red) (banana yellow) (cherry red)))

user=> (map first fruit)
(apple banana cherry)

(defn my-map [f lst]
(if (empty? lst)
()
(cons (f (first lst)) (my-map f (rest lst))) ) )

user=> (my-map first fruit)
(apple banana cherry)
Anonymous functions

An anonymous function has the syntax:
(fn [parameters] body)

Example:
(fn [x] (* x x))

Anonymous functions are used when


The function body is short and simple, and
It is only needed in one place
filter

(def fruit '((apple red) (banana yellow) (cherry red)))

user=> (filter (fn [x] (= (second x) 'red)) fruit)
((apple red) (cherry red))

(defn my-filter [p lst]
(cond
(empty? lst) ()
(p (first lst))
(cons (first lst) (my-filter p (rest lst)))
:else (my-filter p (rest lst)) ) )

user=> (my-filter (fn [x] (= (second x) 'red)) fruit)
((apple red) (cherry red))
Speaking of maps…

A map or hash is a sequence of key/value pairs, enclosed in
braces, for example,
{:ace 1, :deuce 2, "trey" 3}



A map is also a function:



Elements are separated by whitespace or commas
It is helpful to use commas between key/value pairs
user=> (def cards {:ace 1, :deuce 2, "trey" 3})
#'user/cards
user=> (cards :deuce)
2
Keywords are also functions:

user=> (:deuce
2
cards)
reduce

user=>
(defn my-reduce [f init lst]
(cond
(empty? lst) init
:else (recur f (f init (first lst)) (rest lst)) ) )
#'user/my-reduce

user=>
(my-reduce + 0 '(11 22 33))
66

user=>
(my-reduce * 1 '(2 3 4))
24
Functions that return functions



A closure is a function that contains and works with, not
only its parameters, but values from the scope in which
it was defined
Currying creates a new function with fewer arguments
than the original function
Function composition combines two or more functions
into a new function
17
Closures I

user=> (defn rangechecker [min max]
(fn [num] (and (>= num min) (<= num max))) )
#'user/rangechecker

user=> (def in-range? (rangechecker 0 100))
#'user/in-range?

user=> (in-range? 75)
true

user=> (in-range? 101)
false
Closures II

user=> (defn adjust-range [min max]
(fn [num] (cond
(< num min) min
(> num max) max
:else num )) )
#'user/adjust-range

user=> (def adjust (adjust-range 0 100))
#'user/adjust

user=> (adjust 75)
75

user=> (adjust 101)
100
Partial functions (currying)

(partial f arg1 arg2 arg3 & more)
Takes a function f and fewer than the normal arguments to f, and
returns a fn that takes a variable number of additional args. When
called, the returned function calls f with args + additional args.

user=> (def hundred-times (partial * 100))
#'user/hundred-times
user=> (hundred-times 5)
500

Function composition




user=> (def negtimes (comp - *))
#'user/negtimes
user=> (negtimes 5 3)
-15
user=> (def third (comp first rest rest))
#'user/third
user=> (third [11 22 33 44])
33
user=> (third '(:a :b :c :d))
:c
The End