Transcript CST223 Week 5 Monday

CST223 WEEK 5 MONDAY

Test on Wednesday, May 2nd
Review Questions for Chapters 1&2
 Homework for Chapter 3
 Lab1 & Lab4

Homework#2 (Chapter 5) due next Wednesday,
May 9th.
 In-Class Exercise #5
 Topic:

Functional Programming Overview
 Introduction to F#

IN-CLASS EXERCISE #5

Write a non-recursive function to reverse a string
(either std::string or char *)

Write a recursive function to reverse a string

Can you reuse the logic to reverse a linked list?
F# BASICS

F# is a multi-paradigm programming language
It supports Functional Programming
 It supports Object-oriented programming
 It supports concurrent programming


Functional Programming
Supports recursive functions
 Built-in data structure – list
 Less type restricted – has some type limitations
(Microsoft .NET)

You don’t have to declare the type of anything.
 F# tries to figure out what the type is. It may need some
help at time.
 It won’t let you mix types

F# BASIC DATA STRUCTURE

List





[] - empty list
[1;2;3;4;5] – list with 5 ints
[‘a’; ‘b’; ‘c’] – list with 3 chars
[“Sherry”; “Sam”; “Jody”] – list with 3 strings
[ [1;2;3];[4;5;6];[7;8;9]] – nested lists of 3
lists each with 3 elements.
 F#
lists must be the same type. Nesting levels
must be consistent.
[1;’a’;”Sherry”] – Error
 [1; [2]; 4] - Error

LIST OPERATORS

Some built-in list operations






Length
Head
Tail
IsEmpty
@ - Append
:: - Cons –
Additional operations available through List
class
 Adding a [ ] to anything makes a list

Let x = 3
 [x] => [3]

LIST APPEND OPERATOR: @
@ requires two lists
 It merges two lists together and return one new
list

[‘a’; ‘b’; ‘c’] @ [‘d’;’e’;’f’] =>
[‘a’;’b’;’c’;’d’;’e’;’f’]
[1;2] @ [3;4;5] =>
[1;2;3;4;5]
LIST CONS OPERATOR:

::
The format is: element::list
This operator simply prepends the element to the
list
‘z’::[‘a’; ‘b’; ‘c’] => [‘z’;’a’;’b’;’c’]
“Michelle” ::“Sherry”; “Sam”; “Jody”]=>
[“Michelle”;”Sherry”;”Sam”;”Jody”]
[12;14]::[ [1;2;3];[4;5;6];[7;8;9]] =>
[[12;14];[1;2;3];[4;5;6];[7;8;9]]
HOW TO APPLY LIST OPERATORS

If F# knows that it’s a list:
Let myList=[1;2;3;4;5]
myList.Head => returns 1
myList.Tail => returns [2;3;4;5]
myList.Length => returns 5
myList.IsEmpty => returns false

If F# doesn’t know that it’s a list or if you want to
use additional List operations:
If myList above is a parameter passed into a function:
List.head myList => returns 1
List.tail myList => returns [2;3;4;5]
List.length myList => returns 5
List.nth myList 3 => returns 4
STATEMENTS

Assignment & definition keyword
let x = 3
Let fn x x*x*x
let rec factorial n =
if n=0 then 1 else n * factorial (n-1)
//rec for recursive functions

Conditional
Have to use then
 Can have elif
 No ( ) around conditional expression

if n=0 then 1 else n * factorial (n-1)
DEFINE FUNCTIONS

Imperative/Functional style

Use if/then/else
let rec factorial n =
if n=0 then 1 else n * factorial (n-1)
let rec hcf a b =
if a=0 then b
elif a<b then hcf a (b-a)
else (hcf (a-b) b)
//extra () optional

Pure functional style

Use pattern matching for lists
EXAMPLE: COMPUTE LENGTH FUNCTION
let rec computeLength myList =
match myList with
| [] -> 0
| head::tail -> 1 +
(computeLength myList.Tail)
EXAMPLE: SUM ELEMENT FUNCTION
let rec sumList myList =
match myList with
| [] -> 0
| head::tail -> head+
(sumList myList.Tail)
EXAMPLE: DUPLICATE ELEMENTS FUNCTION
let rec duplicateList myList =
match myList with
| [] -> []
| head::tail -> head::head::
duplicateList myList.Tail
EXAMPLE: FIND ELEMENT IN LIST FUNCITON
let rec find x ls =
match ls with
| [] -> false
| head::tail -> if x=head then true
else (find x ls.Tail)
HOW TO RUN F# IN VS2010

Build and run (non-interactive)


Create a F# application project
Interactive

Highlight the code to run interactively and hit
<Alt><Enter>