DOC PREVIEW
UMD CMSC 330 - Functional Programming with OCaml

This preview shows page 1-2-3 out of 9 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1CMSC 330: Organization of Programming LanguagesFunctional Programming with OCamlCMSC 330 2Reminders / Announcements• Project 3 was posted2CMSC 330 3More Basics…# let l1 = [1;2;3];;val l1 : int list = [1; 2; 3]# let l2 = [1;2;3];;val l2 : int list = [1; 2; 3]# l1 == l2;;- : bool = false (shallow equality)# l1 = l2;;- : bool = true (deep equality)- <> is negation of =- != is negation of ==CMSC 330 4More Examples of Recursion• sum l (* sum of elts in l *)let rec sum l = match l with[] -> 0| (x::xs) -> x + (sum xs)• negate l (* negate elements in list *)let rec negate l = match l with[] -> []| (x::xs) -> (-x) :: (negate xs)• last l (* last element of l *)let rec last l = match l with[x] -> x| (x::xs) -> last xs3CMSC 330 5More Examples (cont’d)(* return a list containing all the elements in thelist l followed by all the elements in list m *)• append (l, m)let rec append (l, m) = match l with[] -> m| (x::xs) -> x::(append (xs, m))• rev l (* reverse list; hint: use append *)let rec rev l = match l with[] -> []| (x::xs) -> append ((rev xs), [x])• rev takes O(n2) time. Can you do better?CMSC 330 6A Clever Version of Reverselet rec rev_helper (l, a) = match l with[] -> a| (x::xs) -> rev_helper (xs, (x::a))let rev l = rev_helper (l, [])• Let’s give it a tryrev [1; 2; 3] rev_helper ([1;2;3], []) rev_helper ([2;3], [1]) rev_helper ([3], [2;1]) rev_helper ([], [3;2;1]) [3;2;1]4CMSC 330 7More Examples• flattenPairs l (* ('a * 'a) list -> 'a list *)let rec flattenPairs l = match l with[] -> []| ((a, b)::t) -> a :: b :: (flattenPairs t)• take (n, l) (* return first n elts of l *)let rec take (n, l) =ifn=0then []else match l with[] -> []| (x::xs) -> x :: (take (n-1, xs))CMSC 330 8Working with Lists• Several of these examples have the same flavor– Walk through the list and do something to every element– Walk through the list and keep track of something• Recall the following example code from Ruby:– Here we passed a code block into the collect method– Wouldn’t it be nice to do the same in OCaml?a = [1,2,3,4,5]b = a.collect { |x| -x }5CMSC 330 9Higher-Order Functions• In OCaml you can pass functions as arguments, and return functions as resultslet plus_threex=x+3let twice (f, z)=f(fz)twice (plus_three, 5)twice : ('a->'a) * 'a -> 'alet plus_fourx=x+4let pick_fn n =ifn>0then plus_three else plus_four(pick_fn 5) 0pick_fn : int -> (int->int)CMSC 330 10The map Function• Let’s write the map function (just like Ruby's collect)– Takes a function and a list, applies the function to each element of the list, and returns a list of the resultslet add_onex=x+1let negatex=-xmap (add_one, [1; 2; 3])map (negate, [9; -5; 0])• Type of map?let rec map (f, l) = match l with[] -> []| (h::t) -> (f h)::(map (f, t))map : ('a -> 'b) * 'a list -> 'b list6CMSC 330 11Anonymous Functions• Passing functions around is very common– So often we don’t want to bother to give them names•Use fun to make a function with no namemap ((fun x -> x + 13), [1; 2; 3])twice ((fun x -> x + 2), 4)funx->x+3Parameter BodyCMSC 330 12Pattern Matching with fun•matchcan be used within funmap ((fun l -> match l with (h::_) -> h),[ [1; 2; 3]; [4; 5; 6; 7]; [8; 9] ])(* [1; 4; 8] *)– For complicated matches, though, use named functions• Standard pattern matching abbreviation can be usedmap ((fun (x, y) -> x + y), [(1, 2); (3, 4)])(* [3; 7] *)7CMSC 330 13All Functions Are Anonymous• Functions are first-class, so you can bind them to other names as you like– letfx=x+3– letg=f– g 5 (* returns 8 *)•letfor functions is just a shorthand– letfx=body stands for– let f = fun x -> bodyCMSC 330 14Examples• letnextx=x+1– Short for letnext=funx->x+1• let plus (x, y)=x+y– Short for letplus=fun(x,y)->x+y– Which is short for• let plus = fun z ->(match z with (x, y) ->x+y)• let rec fact n =ifn=0then 1 else n * fact (n-1)– Short for let rec fact = fun n ->(ifn=0then 1 else n * fact (n-1))8CMSC 330 15let rec fold (f, a, l) = match l with[] -> a| (h::t) -> fold (f, f (a, h), t)The fold Function• Common pattern: iterate through a list and apply a function to each element, keeping track of the partial results computed so far–a= “accumulator”– this is usually called “fold left” to remind us that ftakes the accumulator as its first argument• What's the type of fold?fold : ('a * 'b -> 'a) * 'a * 'b list -> 'aCMSC 330 16Exampleletadd(a,x)=a+xfold (add, 0, [1; 2; 3; 4]) fold (add, 1, [2; 3; 4]) fold (add, 3, [3; 4]) fold (add, 6, [4]) fold (add, 10, []) 10We just built the sum function!let rec fold (f, a, l) = match l with[] -> a| (h::t) -> fold (f, f (a, h), t)9CMSC 330 17Another Examplelet next (a, _)=a+1fold (next, 0, [2; 3; 4; 5]) fold (next, 1, [3; 4; 5]) fold (next, 2, [4; 5]) fold (next, 3, [5]) fold (next, 4, []) 4We just built the length function!let rec fold (f, a, l) = match l with[] -> a| (h::t) -> fold (f, f (a, h), t)CMSC 330 18Using fold to Build rev• Can you build the reverse function with fold?let prepend (a, x) = x::afold (prepend, [], [1; 2; 3; 4]) fold (prepend, [1], [2; 3; 4]) fold (prepend, [2; 1], [3; 4]) fold (prepend, [3; 2; 1], [4]) fold (prepend, [4; 3; 2; 1], []) [4; 3; 2; 1]let rec fold (f, a, l) = match l with[] -> a| (h::t) -> fold (f, f (a, h),


View Full Document

UMD CMSC 330 - Functional Programming with OCaml

Documents in this Course
Exam #1

Exam #1

6 pages

Quiz #1

Quiz #1

2 pages

Midterm 2

Midterm 2

12 pages

Exam #2

Exam #2

7 pages

Ocaml

Ocaml

7 pages

Parsing

Parsing

38 pages

Threads

Threads

12 pages

Ruby

Ruby

7 pages

Quiz #3

Quiz #3

2 pages

Threads

Threads

7 pages

Quiz #4

Quiz #4

2 pages

Exam #2

Exam #2

6 pages

Exam #1

Exam #1

6 pages

Threads

Threads

34 pages

Quiz #4

Quiz #4

2 pages

Threads

Threads

26 pages

Exam #2

Exam #2

9 pages

Exam #2

Exam #2

6 pages

Load more
Download Functional Programming with OCaml
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Functional Programming with OCaml and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Functional Programming with OCaml 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?