DOC PREVIEW
Princeton COS 320 - ML intro

This preview shows page 1-2-3-4-25-26-27-51-52-53-54 out of 54 pages.

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

Unformatted text preview:

More ML Compiling Techniques David Walker Today More data structures lists More functions More modules Lists Lists are created with nil makes empty list head tail makes a longer list 5 nil int list element list of elements Lists Lists are created with nil makes empty list head tail makes a longer list 4 5 nil int list element list of elements Lists Lists are created with nil makes empty list head tail makes a longer list 3 4 5 nil int list element list of elements Lists Lists are created with 3 4 5 nil int list 3 4 5 nil int list true 1 false 2 nil bool int list 3 nil 2 nil nil int list list Lists Lists 3 int list 3 4 5 int list a different way of writing nil true bool list a different way of writing a list Lists Bad List 4 3 Lists Bad List 4 3 stdIn 1 1 2 2 Error operator and operand don t agree literal operator domain int list int list list operand int list int in expression 4 nil 3 Lists Bad List true 5 Lists Bad List true 5 stdIn 17 1 17 9 Error operator and operand don t agree literal operator domain bool bool list operand bool int list in expression true 3 nil List Processing Functions over lists are usually defined by pattern matching on the structure of a list fun length l case l of nil 0 l l 1 length l Hint often the structure of a function is guided by the type of the argument recall eval List Processing Two arguments f and l fun map f l case l of nil l x l f x map f l What does it do List Processing fun map f l case l of nil l x l f x map f l applies the function f to every element in the list fun add1 x x 1 map add1 1 2 3 val it 2 3 4 int list List Processing fun fold f a l case l of nil a l x l f fold f a l x another incredibly useful function what does it do use it to write map ML is all about functions There are many different ways to define functions I almost always use fun f x When I am only going to use a function once and it is not recursive I write an anonymous function fn x Anonymous functions val n 3 binds a variable n to a value 3 binds a variable isValue val isValue fn t case t of Bool true to the anonymous fn keyword function value t false introduces anonymous fun Anonymous functions fun map f l case l of nil l x l f x map f l fun addlist x l map fn y y x l anonymous functions Anonymous functions a type definition very convenient type ifun int int val intCompose ifun ifun ifun a pair of anonymous functions fun add3 x intCompose fn x x 2 fn y y 1 x Anonymous functions type ifun int int val intCompose ifun ifun ifun fn f g argument is pair of functions fn x f g x pattern match against arg result is a function fun add3 x intCompose fn x x 2 fn y y 1 x Another way to write a function fun f x can be written as val f fn x provided the function is not recursive f does not appear in Another way to write a function fun f x can always be written as val rec f fn x f can be used here keyword rec declares a recursive function value Yet another way to write a function fun isValue Num n true isValue Bool b true isValue false This is just an abbreviation for fun isValue t case t of Num n true Bool b true false Yet another way to create a type error fun isValue 0 true isValue Bool b true isValue false ex sml 9 1 11 29 Error parameter or result constraints of clauses don t agree literal this clause term Z previous clauses int Z in declaration isValue fn 0 true Bool b true false Parametric Polymorphism Functions like compose work on objects of many different types val compose fn f fn g fn x f g x compose fn x x 1 fn x x 2 compose not fn x x 17 Parametric Polymorphism Functions like compose work on objects of many different types val compose fn f fn g fn x f g x compose not fn x x 17 compose fn x x 17 not BAD Parametric Polymorphism Functions like compose work on objects of many different types val compose fn f fn g fn x f g x a type variable stands for any type compose a b c a c b Note type variables are written with Parametric Polymorphism Functions like compose work on objects of many different types compose a b c a c b can be used as if it had the type compose int b c int c b Parametric Polymorphism Functions like compose work on objects of many different types compose a b c a c b can be used as if it had the type compose int int b c int int c b Parametric Polymorphism Functions like compose work on objects of many different types compose a b c a c b can be used as if it had the type compose unit int int unit int int Parametric Polymorphism compose a b c a c b not bool bool compose not Parametric Polymorphism compose a b c a c b not bool bool compose not type of compose s argument must equal the type of not bool bool a b Parametric Polymorphism compose a b c a c b not bool bool compose not therefore a must be bool b must be bool as well in this use of compose Parametric Polymorphism compose a b c a c b not bool bool a bool b bool compose not c bool c bool Parametric Polymorphism compose a b c a c b not bool bool compose not c bool c bool compose not not bool bool Parametric Polymorphism compose a b c a c b not bool bool compose not c bool c bool compose not not Parametric Polymorphism compose a b c a c b compose fn x x Parametric Polymorphism compose a b c a c b compose fn x x d d Parametric Polymorphism compose a b c a c b compose fn x x d d must be the same ie a d b d Parametric Polymorphism compose d d c d c d compose fn x x d d must be the same ie a d b d Parametric Polymorphism compose d d c d c d compose fn x x d d c d c d What is the type of map fun map f l case l of nil l x l f x map f l What is the type of map fun …


View Full Document

Princeton COS 320 - ML intro

Download ML intro
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 ML intro 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 ML intro 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?