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