Summary

These lecture notes cover functional programming, including definitions, historical context, and practical applications, using examples in Haskell. The document details course objectives, evaluation criteria, including specific lab assignments. The document emphasizes recursion, type inference, and higher-order functions.

Full Transcript

PF Functional Programming Radu Răzvan Slăvescu Technical University of Cluj-Napoca Department of Computer Science Outline Functional Programming Definition of Functional Programming Where is FP used? Brief history Administrativia Course overview Bibli...

PF Functional Programming Radu Răzvan Slăvescu Technical University of Cluj-Napoca Department of Computer Science Outline Functional Programming Definition of Functional Programming Where is FP used? Brief history Administrativia Course overview Bibliography Evaluation Defining functions if-then-else and Pattern Matching Recursion Looping via recursion Tail recursion Administrativia Lectures Assoc. prof. dr. eng. Radu Răzvan Slăvescu Course Materials 1. Lecture slides (in English) + lab documents posted on moodle every week 2. Enrollment key provided by the TA You MUST use the key of your group! Definition Functional Programming (FP) = a style of programming which employs functions applied to arguments as basic blocks for building programs. The arguments themselves can be function calls, so complex programs are built via function composition. Observation The functional paradigm belongs to declarative programming: you specify what the program does, not how it does it. Definition Program = Function Principles of (pure) Functional Paradigm I Functions are ”first class citizens” (can be passed as arguments, returned by other functions, stored in lists etc.) I Functions have no side effects (or they’re highly controlled) I Functions do not depend on global variables I Expressions (= get evaluated to some value), not statements (= perform some action) I No sequential execution of code, just combining functions I Immutable variables: their value does not change over time I There is no ”state of the program” I There are no loops, just recursive calls What is FP? Features of the FP languages we will study I strongly typed: every entity has a type attached I statically typed: type detected at compile time I perform type inference: each entity’s type is automatically deduced Language vs. implementation Language: Haskell. Implementation: ghc (software toolkit) Why FP? Modern software challenges... 1. complexity increases 2. time of development should decrease 3. number of errors should decrease...and solutions offered by Functional Programming 1. supports writing highly abstracted, clear and concise code 2. allows software reuse and rapid prototyping 3. permits reasoning about the program’s corectness 4. permits easy parallelization of the code Where if FP used? Functional Programming - some application domains 1. Erlang: WhatsApp (50 engineers, 900M users) 2. Haskell: IOG (Cardano - third-gen blockchain platform) 3. Haskell: Facebook (the Sigma anti-spam system) 4. Artificial Intelligence tools and languages: I Google JAX, a Python library for high-performance numerical computing, used in Machine Learning research I Isabelle and Agda: proof assistants I CLIPS, a rule based expert system shell A little bit of history Lambda calculus: 1930s I Lambda calculus - a theory by Alonzo Church about what functions are able to compute I could be seen as a minimalist programming language I virtually every functional language is based on this theory I useful in many fields, e.g. expressing semantics of text A little bit of history LISP (LISt Processing): 1950s, John McCarthy I functional language with ideas from lambda calculus I basic blocks: atoms, lists, forms I allows variable change (unfortunately!) I nowadays dialects: 1. Common LISP 2. Scheme 3. Racket 4. Clojure (integrated with Java platform) 5. Hy (integrated with Python) I implementations 1. gcl (GNU Common LISP) 2. CLISP 3. Steel Bank Common LISP 4. Allegro CL A little bit of history ML (Meta Language): 1970s, Robin Milner I featuring polymorphic types and type inference I implementations: 1. sml (Standard ML) 2. polyML 3. Caml 4. Objective Caml A little bit of history Miranda family Miranda means ”Admirable” A little bit of history Miranda family: Haskell (after Haskell Curry): 1987 I purely functional, with lazy evaluation I standard: Haskell 2010 report (succeeding Haskell 98) I implementation (de facto standard): ghc (Glasgow Haskell Compiler) Multiparadigm programming languages featuring FP Multiparadigm laguages Scala immutability, lazyness. Compiles to bytecode Rust expressions, types, concurrency F# (for.NET) OO + FP (Caml-like) C# immutability, function composition Python lambdas, higher-order functions, lazy objects Objectives After completing this course you should be able to: I write idiomatic, efficient functional code I understand and be able to use the basic concepts of FP I develop a basic understanding of Lambda calculus Lectures overview Basics of programming in Haskell I primitive data types I functions and recursion I evaluation (call-by-value, call-by-name, call-by-need) I type inference I lists and list comprehensions Lectures overview FP specific elements I higher-order functions HOFs (incl. anonymous functions, partial application) I infinite data and lazy evaluation I transformation and reasoning on programs I elements of Lambda calculus Lab overview Lab materials (+ related lectures) must be read in advance Elm lab: weeks 1 - 6 I basics of Elm I defining Elm functions by recursion I write a demo application Haskell: weeks 8 - 13 I practice writing Haskell code Bibliography R. R. Slăvescu Functional Programming - lecture notes. Technical University of Cluj-Napoca, 2024. G. Hutton Programming in Haskell, 2nd edition. Cambridge University Press, 2016 slides available from the course web page M. Lipovača. Learn you a Haskell for Great Good. http://learnyouahaskell.com Bibliography Haskell wiki page www.haskell.org I. A. Leţia, L. A. Negrescu, L. Negrescu Programare funcţională, vol. I. Ed. Albastră, Cluj-Napoca, Romania, 2006 Evaluation How is your mark computed? Weighted average: I Final examination: 50% (written/moodle) I Lab activity 50% I week 4 (Elm): Lab test 1: 10% I week 6 (Elm): Assignment 1: 30% + Lab test 2: 10% I week 11 (Haskell): Lab test 3: 10% I week 14 (Haskell): Lab test 4: 40% I lab code evaluation: 60% tests known in advance; 20% new tests; 20% code style Evaluation Bonuses: I Challenges I Kahoot Yellow Jersey competition (1 point per competition winner + 1.5, 1.4,... , 0.6 for the global standings) If Kahoot is available I outstanding activity during lectures/labs Condition for passing Lab: average(tests) 20% AND average(assignments) 30% AND average(testsAndAssignments) 50% Exam: average(exam) 5.00 AND average incl bonuses 5.00 Final Exam Exam I 50 % of the final mark I quick questions + problem I If failed: repeated during the next session of exams A couple of small Haskell examples Computing reciprocal (! partial application) (1/) Sorting lists (! list comprehension + HOF) q [] = [] q (h:t) = q [s | s Double area r = 3.14 * r * r Example (Haskell, REPL) Prelude> area r = 3.14 * r * r Prelude> area 3 28.259999999999998 How do we know the type of a function? Example (square of an integer: sq) Prelude> sq :: Int -> Int; sq x = x * x Prelude> :type sq Prelude se refera la sq :: Int -> Int varianilele funtiei ce se scrie in terminal Example (Most general solution for sq type) Prelude> sq x = x*x Prelude> :type sq sq :: Num a => a -> a How do we call a function? Calling functions Math: f(x, y*z, g(t)) FP: f x (y*z) (g t) Note 1. as a rule, no parentheses separate the function name and its arguments; 2. pay attention to the precedence: fact n - 1 versus fact (n-1); if not sure, use parentheses if expression (not statement) if-then-else if E then ET else EF: 1. E gets evaluated, then... 2. either ET or EF is evaluated, but never both of them 3. else is mandatory (Why?) Pattern matching mechanism Example (Product of elements in a list) prodl [] = 1 --equation 1 prodl (n:ns) = n * prodl ns --equation 2 Observations 1. each equation defines a pattern, telling what the function returns when its argument looks in a specific way (it matches that pattern) (! declarative style) 2. pattern order does matter 3. pattern matching leads to variable binding: I n:ns matched on [1,2,3] binds n to 1 and ns to [2,3] I 1:ns matched on [1,2,3] binds ns to [2,3] I 1:ns fails when trying to match [2,3] (different list heads) I n:_:ns matched on [1,2,3] binds n to 1 and ns to Pattern matching mechanism Example (Product of elements in a list using case) prodl xs = case xs of [] -> 1 (n:ns) -> n * prodl ns Example (Product of elements in a list: no patterns) prodl ns = if null ns then 1 else (head ns) * prodl (tail ns) Observations 1. using patterns increases code clarity... 2.... and allows a better analysis of cases, thus leading to a better performance of the generated code Recursion: a function calls itself in its body Ouroboros snake (with permission from Wikimedia Commons) Recursion: main mechanism to implement loops Definition Linear recursive function It has only one recursive call to itself each time it runs. Example (Greatest common divisor: Euclid’s Algorithm) euclidgcd m n = if (m == 0) then n else euclidgcd (n ‘mod‘ m) m Example (Power, linear) power m n = if (m==0) then 0 -- what if n==0 else if n==0 then 1 else m * (power m (n-1)) Recursive functions Example (Fibonacci F0 = 0, F1 = 1, Fn = Fn 1 + Fn 2 ) fib n = if n==0 then 0 else if n==1 then 1 else fib (n-1) + fib (n-2) Example (Ackermann-Péter function) ack m n = if m==0 then (n+1) else if n==0 then ack (m-1) 1 else ack (m-1) (ack m (n-1)) Remark The number of recursive calls of this function increases extremely rapidly with its arguments. Recursive functions Definition A function is tail recursive if it returns either something computed directly or something returned by its recursive call (the last thing it does is to call itself) Example (A tail recursive function) iseven n = if (n==0) then True else if (n==1) then False else iseven (n-2) Recursive functions Example (factorial - a not tail recursive version) fact n = if (n == 0) then 1 else n * fact (n-1) Example (factorial - a tail recursive version) factacc n a = if (n==0) then a else factacc (n-1) (n*a) fact: successive calls waste stack space and time Example fact 3 = 3 * fact 2 = 3 * (2 * fact 1) = 3 * (2 * (1 * fact 0)) = 3 * (2 * (1 * 1)) = 3 * (2 * 1) fact 0 #1 = 3 * 2 fact 1 #1 = 6 fact 2 #2 factacc: no space and time wasted Example factacc 3 1 = factacc (3-1) (3*1) = factacc (2-1) (2*3) = factacc 0 6 6 factacc (1-1) (1*6) = factacc 1 6 6 factacc 2 3 Remark Each call can overwrite the stack frame of the previous one, hence no need for extra space or stack processing time factacc: no space and time wasted Example factacc 3 1 = 6 factacc (3-1) (3*1) = factacc (2-1) (2*3) = factacc (1-1) (1*6) = 6 Remarks 1. a tail recursive function is equivalent to an iteration and can automatically be re-written this way by the compiler 2. writing recursive functions in this manner helps saving stack space (constant!) and time (stack manipulation) Don’t Repeat Yourself: Local declarations in Haskell Example (Top-down approach: where) f x y = (sq x + sq y) < 1.0 where sq z = z * z -- square Prelude> f 0.4 0.0 True Indentation matters! Don’t Repeat Yourself: Local declarations in Haskell Example (Bottom-up approach: let... in...) f x y = let sq z = z * z -- square in (sq x + sq y) < 1.0 Mutually Recursive Functions Haskell: define either before or after use Example (Order not important) isevn n = if (n==0) then True else isodd (n-1) isodd n = if (n==0) then False else isevn (n-1) or Example (Order not important) isodd n = if (n==0) then False else isevn (n-1) isevn n = if (n==0) then True else isodd (n-1) Summary I FP is a style of programming which employs functions applied to arguments as basic blocks for building programs I We use functions and functions alone I No side effects. No variable change. No program state. No sequences of instructions. No statements. No loops. I Many functional languages/implementations available; among them, Haskell/ghc and Elm I Pattern Matching is used to express alternatives. I Recursion and function composition are employed for writing complex functional programs I Tail recursion improves performance Further reading Learn more LYHFGG: Chapter 1, Chapter 2 up to ”Texas Ranges” Programming in Haskell: Chapter 1 and Chapter 2 Why haskell in Cardano? https://www.youtube.com/watch?v=1HGUu-EIb5g Functional Programming Applications - further info 1. galois.com (critical systems) 2. commercial users of FP: http://cufp.org 3. https://www.lightbend.com/case-studies Functional Programming Radu Răzvan Slăvescu Technical University of Cluj-Napoca Department of Computer Science Outline Operators Primitive types in Haskell Basic operations on lists Tuples and Records Polymorphic types and Overloading Identifiers and constants in Haskell Definition A letter followed by any number of letters, digits, _, ’ Example supercalifragilisticexpialidocious america’ catch_22 Nothing Example (Haskell, batch style) pi = 3.14 Observation No function can change the value assigned to it. Operators Definition An infix operator is a function written between its arguments. This is done for syntactic sugaring. Example (|!&) :: Bool -> Bool -> Bool infixl 6 |!& x |!& y = (x || y) && not (x && y) *Main> True |!& True False Operator precedence Example (number just after infix) infixl 6 |+| x |+| y = "(" ++ x ++ "+" ++ y ++ ")" infixl 5 |*| x |*| y = "(" ++ x ++ "*" ++ y ++ ")" *Main> "2" |+| "3" |*| "4" "((2+3)*4)" Operators Example (infixl: left associativity) infixl 6 ## x ## y = "(" ++ x ++ "+" ++ y ++ ")" Prelude> "1" ## "2" ## "3" "((1+2)+3)" Example (infixr: right associativity) infixr 6 ## x ## y = "(" ++ x ++ "+" ++ y ++ ")" Prelude> "1" ## "2" ## "3" "(1+(2+3))" Operators Note An infix operator could be used as prefix function. Example (Haskell addition) 1 + 2 same as (+) 1 2 Example (Haskell custom operator) "1" ## "2" (##) "1" "2" Example (Haskell division) 3 ‘div‘ 2 div 3 2 Types and type checking Definition (Type) Type = collection of related values + functions over them Remark Strongly typed languages require each entity to have a type assigned and enforce strict typing rules for operations. Definition (Type inference) Type inference = find out the type of an expression Definition (Static v. Dynamic type checking) I Static type checking = verify type safety at compile time I Dynamic type checking = verify type safety at runtime Primitive types: Integers Integers in Haskell I Int / Integer: fixed / arbitrary precision integers I binary operations: + - * ‘div‘ ‘mod‘ I relational operators: < > = == / = I Integral is sort of ”supertype” for both Int and Integer Example (Haskell Int operators) Prelude> 1 + 2 3 Prelude> 1 < 2 True Prelude> 3 ‘div‘ 2 1 Primitive types: Real Real type in Haskell I Float / Double: simple, respective double precision I operations: + - * / I relational operators: < > = == / = I 1.4142135 (Float) 1.41421356237 (Double) -10.0 1.0E-2 I Fractional is sort of ”supertype” for both Float and Double I Num is sort of ”supertype” for both Integral and Fractional Primitive types: Boolean Boolean type in Haskell I type: Bool; values: True, False I logical operations: not, &&, || I conditional expression: if E then ET else EF Character and string Example (Char: between quotes (´)) ’a’,’b’,...,’z’,’3’ ’\n’,’\\’ Example (String: between double quotes (")) "abc","a1b2","" String Operators 1. relational: , =, ==, /= 2. concatenation: ++ A little bit of lists and primitive functions on lists Definition (List) A list is a sequence of values of a specific type. Example (Haskell) Prelude> :set +t --ask ghci to tell the type Prelude> [1,2,3] :: [Integer] [1,2,3] :: [Integer] Observations 1. the length of the list is not limited 2. the types of list elements are not restricted 3. however, the elements must have the same type A little bit of lists and primitive functions on lists Example (Haskell) 1. Prelude> head [1,2,3] 1 2. Prelude> tail [1,2,3] [2,3] 3. Prelude> null [1,2,3] False 4. Prelude> 1:[2,3] [1,2,3] 5. Prelude> [1,2] ++ [3,4] [1,2,3,4] 6. Prelude> length [11,12,13] 3 7. Prelude> [11,12,13] !! 1 Index 12 8. Prelude> elem 12 [11,12,13] True Tuples Definition (Tuple) A finite sequence of components of possibly different types. E.g.: (1,’2’,"four") Remarks I tuples: enclosed in parentheses I components: comma-separated I component order matters (semantics connected to component position) I use case: a function which needs to return several values (e.g., a complex number) Building and accessing tuples in Haskell Example (A person has name, age, gender, address) --a tuple which stores these components type Person = (String, Int, Char, String) --Person is just an alias for the tuple --let me introduce Brad: tuple constructor a1 :: Person a1 = ("Brad", 60, ’M’, "L. A.") Main> :t a1 --the system "knows" the new type a1 :: Person --deconstruct a1 to find out info on him (thename, theage, thegender, theaddress) = a1 --constructors do the deconstruct job as well Building and accessing tuples in Haskell Example (A person has name, age, gender, address) --deconstruct a1 to find out info on him (thename, theage, thegender, theaddress) = a1 Main> theage 60 Union/sum/enumerate type Example (Introduce a brand new type: Gender (male/female)) data Gender = -- the new type’s name M | F -- alternative constructors deriving (Show) -- values can be displayed --a tuple stores personal info pieces type Person = (String, Int, Gender, String) Building and accessing tuples in Haskell Example (Add and extract personal info) --let me introduce Brad a1 :: Person a1 = ("Brad", 60, M, "L.A.") --let’s learn something about a1 (thename, theage, thegender, thelocation) = a1 Printing components of a tuple Example (The system can print a String...) Main> thelocation "L.A." Example (The system struggles to print a Gender...) Main> thegender M Printing components of a tuple Example (...so we should teach him how to improve) printGender :: Gender -> String -- the function type may use the new type --define function by cases printGender s = case s of M -> "Male" F -> "Female" Main> printGender thegender "Male" Building and accessing records in Haskell Example (A person has name, age, sex) --a record stores info in a set of NAMED fields --semantics connected to field names data Prs = Prs { name :: String , age :: Int , sex :: Char } --let me introduce Brad: record constructor a1 = Prs { name = "Brad", age = 60, sex = ’M’} Building and accessing records in Haskell Example (A person has name, age, sex) --let me introduce Brad: record constructor a1 = Prs { name = "Brad", age = 60, sex = ’M’} Main> :t age --field names work as getters age :: Prs -> Int Main> age a1 60 Polymorphism Strong typing versus Weak typing Strong typing provides safety; weak typing provides flexibility. Polymorphism aims to reconcile these. Definition Polymorphic entity = can have more than one type Definition Polymorphic function = a function based on type variables (which can be further instantiated to create specific types). Polymorphism Example head :: [a] -> a Example (Type variable a gets instantiated to Char) Prelude> head [’a’, ’b’, ’c’] ’a’ Example (Type variable a gets instantiated to [Char]) Prelude> head ["CFR", "FCSB", "U"] "CFR" Remark One behavior for the function, different argument types Type inference Definition An expression is well typed if the type checker is able to assign values to each of its type variables in a non-contradictory way. Inference rule for type inference f :: A >B e :: A (f e) :: B Explanation Let’s assume function f maps entities of type A into entities of type B and e is an entity of type A. If f is passed e as an argument, the returned entity will have type B. Type inference example Obliga un tip sa fie alt tip pentru a evalua expresia Example corect facti (n, p) = if (0 :: Int) == n then p else facti (n-1, n*p) Type inference 0 == n is Int comparison (because both the following hold: ( (0::Int)==) :: Int -> Bool and 0::Int) ! n is of type Int AND n * p is Int multiplication ! p is of type Int AND p is of type Int ! facti is of type (Int, Int) -> Int Overloaded functions Definition Overloaded function = a polymorphic function whose type contains one or more constraints. Example (constraint: t must be of type number (Num)) mysum [] = 0 mysum (x:xs) = x + mysum xs Prelude> :type mysum mysum :: Num t => [t] -> t Remark Same name for the function, different implementations. Some type classes in Haskell and their supported methods I Eq (equality types): their values can be compared using == and /= (e.g. Int, Char, lists with elements in Eq) I Ord (ordered types): those in Eq which can be ordered using =, min, max I Show (showable types): those whose values can be converted to strings (and displayed) by using show I Num (numeric types): numbers, on which we can apply +, -, *, negate, abs, signum I Integral: types which are instances of Num, on which we can apply div, mod (e.g. Int, Integer) I Fractional: types which are instances of Num, on which we can apply /, recip (e.g. Float, Double) Polymorphic equality Definition An equality type is a type endowed with an equality predicate. (which is not available for every object in FP, as we focus on semantics, not equality of memory locations). Example (Haskell: Eq a) Prelude> :type (==) (==) :: Eq a => a -> a -> Bool Polymorphic equality Example (Seek an element in a list) myelem _ [] = False myelem e (x:xs) = if (e==x) then True else myelem e xs Prelude> :t myelem myelem :: Eq t => t -> [t] -> Bool Equality types This function could be called only on lists whose elements are of equality types, e.g. Int, String, Char etc. Some more type inference examples Example (a pair of arguments, parentheses) type Vector = (Int, Int) gcd4 :: Vector -> Int gcd4 (m,n) = if m == 0 then n else gcd4 (n ‘mod‘ m, m) gcd4 :: Vector -> Int Example (a pair of arguments, parentheses) type Vector = (Int, Int) gcd3 (m,n) = if m == 0 then n else gcd3 (n ‘mod‘ m, m) gcd3 :: Integral t => (t, t) -> t Some more type inference examples Example (a pair of arguments, parentheses) gcd2 (m,n) = if m == 0 then n else gcd2 (n ‘mod‘ m, m) gcd2 :: Integral t => (t, t) -> t Example (2 arguments, no parentheses) gcd1 m n = if m == 0 then n else gcd1 (n ‘mod‘ m) m gcd1 :: Integral t => t -> t -> t Introducing new types Example (type: alias for an existing type) type Astring = [Char] Example (data: build a brand new type via enumeration) data Color | {z } = | Red | Green | Blue {z } new type type constructors names in CAPITALS! Example (Maybe: constructors might have arguments) data Maybe a = Nothing | Just a A value of this type either stores a value of type a (represented as Just a), or is just empty (represented as Nothing). Introducing new types Definition (Sum/union/enumerate types) Are defined using alternatives. Example (Sum type) data Gender = M | F data Maybe a = Nothing | Just a Definition (Product types) Are defined in a ”cartesian product”-style. Example (Product type) type Person = (String, Int, Gender, String) data Pers = Pers { name :: String, age :: Int} A 2 ⇥ 2 matrix Problem Write an operator * for 2 ⇥ 2 matrix multiplication Introducing a new data type: a 2 ⇥ 2 matrix data Matrix2x2 = Mat2 ((Integer, Integer), (Integer, Integer)) deriving (Show) A 2 ⇥ 2 matrix The new type is Num and implements * instance Num Matrix2x2 where Mat2 (ali1, ali2) * Mat2 (bli1, bli2) = let (a11, a12) = ali1 -- deconstruct lines (a21, a22) = ali2 (b11, b12) = bli1 (b21, b22) = bli2 in Mat2 ((a11*b11+a12*b21, a11*b12+a12*b22), (a21*b11+a22*b21, a21*b12+a22*b22)) A 2 ⇥ 2 matrix A new operator: matrix at number infixr 8 |ˆ| Mat2 (ali1, ali2) |ˆ| n = if (n==0) then Mat2 ((1,0), (0,1)) else Mat2 (ali1, ali2) * Mat2 (ali1, ali2) |ˆ| (n-1) Summary I Infix operators provide syntax sugaring I head, tail, null, :, ++, !!, elem provide a basic repertoire of list manipulation functions I Tuples and records increase flexibility and readability I In Haskell we have the usual basic types (Integer, Bool, Char, String) and a sophisticated type classes system I New types can be introduced as sum or product types, by deriving etc. Functional Programming Radu Răzvan Slăvescu Technical University of Cluj-Napoca Department of Computer Science Outline Function Types Recursive Types Expression evaluation Call-by-value Call-by-name / by-need List Processing with Recursion and Pattern Matching Building lists Basic functions on lists Association lists Function Types and curried functions Definition We write T1 -> T2 to denote the type of all functions which map an argument of type T1 to a result of type T2. Example not :: Bool -> Bool Remark So, functions could also be regarded as types. Function Types and curried functions Example (Argument: tuple of Int; return: Int) add :: (Int, Int) -> Int add (x, y) = x + y Example (Argument: Int; return: function from Int to Int) add’ :: Int -> (Int -> Int) add’ x y = x + y Definition A function is curried if it takes its arguments one at a time. Remark By default, every Haskell function is curried (like add’). Curried functions - why are they useful? Remark Curried functions allow to easily and concisely define some useful functions by partially applying them. Example (A function for incrementing numbers) (add’ 1) Main> (add’ 1) 2 3 Sections Definition If is an infix binary operator, then ( ), (x ) and ( y) are legal Haskell functions called sections. Example (Guess) (/2) 4.0 (2/) 4.0 :type (/) Argument order and the arrow operator Remark To avoid excess parentheses, we state, by convention, that the arrow operator in types (->) is right associative. Example Int -> Double -> Char -> Bool means Int -> (Double -> (Char -> Bool)) Remark Hence: applying curried functions is left associative. Example f i d c means ((f i) d) c Tree data type Example (Type Tree in Haskell, using 3 constructors) data Tree = Empty | Leaf Int | Node Tree Int Tree t2 :: Tree t2 = Node Empty 1 (Leaf 2) Remarks 1. constructor functions do not have any defining equations; they just build data 2. recursivity is allowed in defining new types Tree data type Example (Type Tree in Haskell, using 3 constructors) data Tree = Empty | Leaf Int | Node Tree Int Tree Example (Constructor types and arities) Empty :: Tree (arity 0) Leaf :: Int -> Tree (arity 1) Node :: Tree -> Int -> Tree -> Tree (arity 3) Remarks 1. Constructor arity: number of its arguments 2. Type arity: number of constructors in type definition Expression evaluation Question: When does an expression get evaluated? ASAP or ALAP? Question: As late as posibile ALAP When calling a function, when are the arguments evaluated: before or after they replace the parameters? Example (Square a number) Dupa ce au sq : number -> number fost inlocuiti sq n = n*n parametrii in functie call by Example (Zero) need zeroit : number -> number zeroit n = 0 Call-by-value Definition In case of ”call-by-value”, the value of the argument is sent. Using call-by-value Call-by-value is used in Elm. Elm is eager. Call-by-value Example sq (sq (sq 2)) = sq (sq (2 * 2)) = sq (sq 4) = sq (4 * 4) = sq 16 = 16 * 16 = 256 Call-by-value Example zeroit (sq (sq (sq 2))) = zeroit (sq (sq (2 * 2))) = zeroit (sq (sq 4)) = zeroit (sq (4 * 4)) = zeroit (sq 16) = zeroit (16 * 16) = zeroit 256 = 0 Call-by-name Definition The expression of the argument is sent. Example zeroit (sq (sq (sq 2))) = 0 Call-by-name Example sq (sq (sq 2)) = sq (sq 2) * sq (sq 2) = (sq 2 * sq 2) * sq (sq 2) = ((2*2) * sq 2) * sq (sq 2) = (4 * sq 2) * sq (sq 2) = (4 * (2 * 2)) * sq (sq 2) =... Call-by-need Definition Call-by-need (”lazy evaluation”) is similar to call-by-name, but evaluates an expression only if necessary and only once, then shares the result. Use of call-by-need Haskell uses call-by-need. Haskell is lazy. Mechanism [x=E] means that every occurence of x in an expression has access to E. If E is evaluated, it is replaced by its value. E is called thunk. Call-by-need Example sq (sq (sq 2)) = z*z [z=sq (sq 2)] = z*z [z=y*y] [y=sq 2] = z*z [z=y*y] [y=2*2] = z*z [z=y*y] [y=4] = z*z [z=4*4] = 16 * 16 = 256 Call-by-need: sometimes it is cool to have it Example (Avoid heavy computation) fst (x,_) = x fst (1, 2ˆ10ˆ10) = 1 -- 2ˆ10ˆ10 not needed Example (Avoid infinte loops (?)) myelem _ [] = False myelem e (x:xs) = if (e==x) then True else myelem e xs neverEndingStory n = (-1) ˆ n + neverEndingStory (n-1) Main> myelem 2 [1, 2, neverEndingStory 3, 4] True Call-by-need - a not-so-cool example Example (Sometimes, we can’t escape our fate) sumacc a [] = a sumacc a (x:xs) = sumacc (a+x) xs sumacc 0 [1,2,3] = sumacc (0+1) [2,3] = sumacc ((0+1)+2) = sumacc (((0+1)+2)+3) []= ((0+1)+2)+3 = (1+2)+3 =... Call-by-need and strict application Note In this example, the whole accumulator’s expression is built before being evaluated. This is an issue for a 10M element list. Forcing argument evaluation $! forces strict (call-by-value style) evaluation of the argument Example (Summing up numbers) sumacc a [] = a sumacc a (x:xs) = (sumacc $! (a+x)) xs Call-by-need - strict application Example (Summing up numbers) sumacc a [] = a sumacc a (x:xs) = (sumacc $! (a+x)) xs sumacc 0 [1,2,3] = (sumacc $! (0+1)) [2,3] = (sumacc $! 1) [2,3] = sumacc 1 [2,3] = (sumacc $! (1+2)) = sumacc 3 =... Call-by-need - strict application n time spent (ms.) digits of n! 5,000 31 16,327 50,000 1,575 213,238 500,000 204,696 2,632,343 1,000,000 840,458 5,565,710 2,000,000 3,500,371 11,733,841 3,000,000 7,757,876 18,128,485 5,000,000 21,295,103 31,323,383 Table: Computing n! for different values of n Machine: ASUS Notebook X551MA (Intel Celeron N2920 @1.86GHz, 4GiB RAM) Call-by-need - strict application Lazy vs. strict: 50,000! no optimization optimization (-O2) lazy 2,728 1,083 strict ($!) 1,089 1,082 Table: Time (ms.) spent to compute 50,000! Machine: ASUS Notebook X551MA (Intel Celeron N2920 @1.86GHz, 4GiB RAM) Defining lists Definition A list is either empty, or is an ordered pair made of an element (”head”) and a list (”tail”). Remark This definition shows the connection between the way we represent data and and the way we process it. Constructors Example (Haskell operator :) Prelude> 1:2:3:[] [1,2,3] Remark The cons operator is right associative. Example (Haskell operator :) Prelude> 1:2: [1,2,3] List processing: Haskell maxl Example (Partial function) Main> :set -W Main> :{ Main| maxl [x] = x Main| maxl (x:y:ys) = if (x>y) then maxl (x:ys) Main| else maxl(y:ys) Main| :} :9:1: warning: [-Wincomplete-patterns] Pattern match(es) are non-exhaustive In an equation for ’max’: Patterns not matched: [] List processing: Haskell length and append Example my_length [] = 0 my_length (_:xs) = 1 + my_length xs Example infix 4 +++ [] +++ ys = ys (x:xs) +++ ys = x:(xs +++ ys) List processing: Haskell take and drop Example my_take 0 _ = [] my_take k [] = [] my_take k (x:xs) = x:my_take (k-1) xs Example my_drop 0 xs = xs my_drop k [] = [] my_drop k (x:xs) = my_drop (k-1) xs List processing: Haskell reverse Example my_rev0 [] = [] my_rev0 (x:xs) = my_rev0 xs ++ [x] or: Example my_rev1 xs = my_rev1acc xs [] where my_rev1acc [] ys = ys my_rev1acc (x:xs) ys = my_rev1acc xs (x:ys) Haskell sum and minimum Example (Summing up a list) Prelude> sum [2,3,4] 9 Example (The lowest value in a list) Prelude> minimum [2,1,3] 1 Composed lists: flattening lists Example flatten [] = [] flatten (x:xs) = x ++ flatten xs Example Main> flatten [ ["RO"], ["CH", "IL"], ["AD"] ] ["RO","CH","IL","AD"] List membership Example (Haskell myelem, officially elem) myelem e [] = False myelem e (x:xs) | e == x = True | otherwise = myelem e xs Remark myelem is written using guarded equations: 1. the test e == x is a guard; it is followed by = and the value the function should return if the guard test is true 2. the | symbol means ”such that” and separates guards 3. the guard otherwise means True (a default guard) 4. (a matter of style): list names ought to end in s Composed lists: zip and unzip Example (zip) myzip ([], []) = [] myzip (x:xs, y:ys) = (x,y):myzip(xs,ys) Main> myzip (["RO", "CH", "IL"], [1,2,3]) [("RO",1),("CH",2),("IL",3)] Example (unzip) myunzip [] = ([], []) myunzip ((x,y):zs) = let (xs,ys) = myunzip zs in (x:xs,y:ys) Composed lists: Haskell zipWith and map Example (A higher order function: zipWith) Prelude> zipWith (*) [1,2,3] [4,5,6] [4,10,18] Remark zipWith pairs up corresponding elements, then performs the specified operation (here, *) over each pair of components Composed lists: Haskell zipWith and map Example (Another higher order function: map) Main> map (2*) [1000,2000,3000] [2000,4000,6000] Remark map applies a function given as an argument (here, (2*)) on each element of a list DIY How can I double each value in a matrix given as a list of lists? Association lists Definition Association list = a list of pairs (key, value) with key of type Eq. Example (Association lists in Haskell) capitals = [("NO","Oslo"), ("FR","Paris"), ("CH","Bern")] assoc (x, []) = [] assoc (x, (y,z):lp) = if x == y then [z] else assoc (x, lp) Example Main> assoc ("CH", capitals) ["Bern"] Summary I curried functions call one argument at a time and are a powerful mechanism in FP I function could be regarded as a type I recursive types are possible I call-by-need (arguments evaluated at most once, when needed) and call-by-value (arguments evaluated before being processed) have both advantages and disavantages I list processing is based on recursivity + pattern matching, in line with the definition of the list Functional Programming Radu Răzvan Slăvescu Technical University of Cluj-Napoca Department of Computer Science Outline Anonymous functions: Lambda expressions List comprehensions Generators Comprehensions=Generators+Guards Some basic Higher Order Functions and Combinators Combinators Anonymous functions No name Name Data 1 a=1 Functions ? inc x = x+1 Example (Lambda expressions) Expression x.x + x is called ”lambda expression” and denotes a nameless function mapping a number into its double. It consists of the symbol , its parameter(s) (here, just x), a dot and the body (computations to be performed; here, x + x). Example (Haskell lambdas: \ for , -> for the dot) Main> (\ x -> x + x) 3 6 When can we benefit from lambda expresions? Example (Avoid ”wasting” function names) squares n = map f [n, n+1, n+2] where f x = x*x could be defined in a simpler manner: squares n = map (\ x -> x*x) [n, n+1, n+2] When can we benefit from lambda expresions? Example (Functions sent as arguments) isord [] _ = True isord [x] _ = True isord (x:y:ys) ordrel = (ordrel x y) && isord (y:ys) ordrel Main> isord ["Ro","Pl","Me","Dk"] (\ x y -> x>y) True Main> isord ["Dk","Pl","Ro","Me"] (\ x y -> x b -> a const1 n _ = n const2 :: a -> b -> a const2 n = \ _ -> n Remark const2 is more natural: the call const2 n creates and returns a function \ _ -> n which does the following things: (1) waits for an argument; (2) consumes it and (3) returns n. When can we benefit from lambda expresions? Example (Formal meaning of currying-based functions) subtract x y = x - y means subtract = \ x -> (\ y -> x - y) Remark Now it should be clear that subtract 1 waits for an argument and subtracts it from 1. Ranges A range is used for enumerating list elements. Example Main> [1..6] [1,2,3,4,5,6] Example Main> [6..1] [] Ranges Example Main> [2,4..10] [2,4,6,8,10] Example Main> [6,5..1] [6,5,4,3,2,1] Remark These generators build an arithmetic progression from one initial limit up to a final limit and with a given increment. Ranges Example (A Bottomless Coin Sack) Main> take 5 [1..] [1,2,3,4,5] Example (Boolean values) Main> take 3 [False.. ] [False,True] Main> take 3 [False, False.. ] [False,False,False] List comprehensions Definition List comprehension = list generators + guards (filtering tests) Example Main> [ x | x [[t]] pr [] = [[]] pr xs = [ a:p | a b) -> [a] -> [b] mapGen f xs = [ f x | x filter odd [1..5] [1,3,5] Example (Defining filter using list comprehenions) filterGen :: (a -> Bool) -> [a] -> [a] filterGen p xs = [ x | x b -> b) -> b -> [a] -> b incorporates this pattern, with the operation and the v value as arguments/parameters, and adds it to the language. Example (New definitions for mysum and myand) mynewsum = foldr (+) 0 mynewand = foldr (&&) True Combinators Problem Write a curried function which decrements its argument by 1. Example (A wrong approach) ((-) 1) Main> ((-) 1) 9 -8 Explanation Arguments are taken from left to right. What to do? The C combinator Example (Solution: C combinator, aka flip in Haskell) combC f x y = f y x Main> combC (-) 1 9 8 Explanation combC swaps the (first two) arguments of f Definition (Combinator) Combinator = a function with no free variables. Though we’ll use this name only for a couple of such functions. The K combinator Explanation The K combinator creates a constant function. Example (Combinator K) combK n x = n Main> combK 3 "anything" 3 Combinators and the Point-Free style Point free style stil de programare in care functiile sunt scrise fara a mentiona parametrii Grade conversion Let us consider two countries, C1 and C2, with grade scales [mi1, ma1] and [mi2, ma2] respectively. (e.g., [0..4] for US GPA and [1..20] France). In country C2 my average is m. What is its corresponding value in country C1? Example (Scale conversion: to, from, mark) scaleMark mi1 ma1 mi2 ma2 m = mi1 + (m-mi2) / (ma2-mi2) * (ma1-mi1) Combinators and the Point-Free style Example (Scale conversion: to, from, mark) scaleMark mi1 ma1 mi2 ma2 m = mi1 + (m-mi2) / (ma2-mi2) * (ma1-mi1) toGPA = scaleMark 0.0 4.0 mix5 f p1 p2 p3 p4 p5 = f p3 p4 p1 p2 p5 franceToAnywhere = mix5 scaleMark 1 20 Remark Functions toGPA and franceToAnywhere are written in point-free style. Their arguments are ”hidden”. Summary I lambda expressions are nameless functions I list comprehensions (generators + guards) allow easy list manipulation I map, filter and foldr focus on lists instead of individual elements I lambda expressions, combinators, and higher-order functions help us writing code in a compact manner Functional Programming Radu Răzvan Slăvescu Technical University of Cluj-Napoca Department of Computer Science Outline Computing Cross Entropy in more than one way Application: Implementing sets as lists Applying Recursion: Polygon Triangulation Problem Four solutions for Fibonacci What is Cross Entropy? Definition (Cross Entropy) The cross entropy H(t, p) of a probability distribution p relative to the distribution t over a given set S is defined as: X H(t, p) = t(x) log2 p(x) x2S T - valorile care sunt date si P - valorile care Remark le prezicem si primim marginea de eroare It measures the difference between two probability distributions (t=true, p=predicted). It is used in Deep Learning as a loss function. Remark We assume no element of p is 0. Computing Cross Entropy: the very first attmept Example (Basic recursion using if-then-else) crossEnt :: Floating t => [t] -> [t] -> t crossEnt ts ps = if (null ts) then 0 else ((-1) * (head ts) * (logBase 2 (head ps)) + crossEnt (tail ts) (tail ps)) Computing Cross Entropy, take 1 Example (Basic recursion using guards) crossEnt :: Floating t => [t] -> [t] -> t crossEnt ts ps | null ts = 0 | otherwise = (-1) * (head ts) * (logBase 2 (head ps)) + crossEnt (tail ts) (tail ps) Computing Cross Entropy, take 2 Example (Pattern matching based equations) crossEnt [] [] = 0 crossEnt (t:ts) (p:ps) = (-1) * t * logBase 2 p + crossEnt ts ps Computing Cross Entropy, take 3 Example (Tail recursion) crossEnt ps qs = cea ps qs 0 where cea [] [] a = a cea (p:ps) (q:qs) a = cea ps qs (a + (-1) * p * logBase 2 q) Computing Cross Entropy, take 4 Example (zip, map, lambda and foldr) crossEnt ts ps = foldr (+) 0 (map (\ (t,p) -> (-1) * t * (logBase 2 p)) (zip ts ps)) Computing Cross Entropy, take 5 Example (zip, map, lambda and sum) crossEnt ts ps = sum (map (\ (t,p) -> (-1) * t * (logBase 2 p)) (zip ts ps)) Computing Cross Entropy, take 6 Example (zipWith, lambda and sum) crossEnt ts ps = sum (zipWith (\ t p -> (-1) * t * (logBase 2 p)) ts ps) Computing Cross Entropy, take 7 Example (List comprehension) crossEnt ts ps = sum [ (-1) * (ts !! i) * (logBase 2 (ps !! i)) | i t -> Set t -> Set t adElem e [] = [e] adElem e (a:x) | e < a = e:a:x | e == a = a:x | otherwise = a:adElem e x Main> adElem 2 [1,3,5] [1,2,3,5] Homework Does adElem make sure that each element is unique? Yes Building sets from lists Example listToSet :: Ord t => [t] -> Set t listToSet [] = [] listToSet (x:xs) = adElem x (listToSet xs) Main> listToSet [1,2,4,3,4,2,1] [1,2,3,4] Cardinality and set membership Example card :: Set a -> Int card s = length s inSet :: Eq t => t -> Set t -> Bool inSet e [] = False inSet e (x:xs) | e == x = True | otherwise = inSet e xs Homework Could you implement inSet in a more efficient fashion? Eliminating one element from a set Example delElem :: Ord t => t -> Set t -> Set t delElem e [] = [] delElem e (a:x) | e < a = a:x | e == a = x | otherwise = a:delElem e x Set union Example union :: Ord a => Set a -> Set a -> Set a union [] t = t union s [] = s union (a:s) (b:t) | a == b = a:union s t | a < b = a:union s (b:t) | otherwise = b:union (a:s) t Main> union [1,3,4] [2,3,5] [1,2,3,4,5] Your turn Homework Write functions for set intersection and difference. Set inclusion Example subset :: Ord a => Set a -> Set a -> Bool subset [] _ = True subset _ [] = False subset (a:s) (b:t) | a == b = subset s t | a < b = False | otherwise = subset (a:s) t Remark Main> subset [] [] True Set equality Example eqset :: Ord a => Set a -> Set a -> Bool eqset xs ys | subset xs ys = subset ys xs | otherwise = False Homework Can you implement eqset in a more efficient manner? All subsets of a set Example powerset :: Set a -> [Set a] powerset xs = pSet xs [] where pSet [] base = [base] pSet (x:xs) base = pSet xs base ++ pSet xs (x:base) Main> powerset [1,2,3] [[],,,[3,2],,[3,1],[2,1],[3,2,1]] Cartesian product Example cartprod :: Set a -> Set b -> [(a,b)] cartprod [] ys = [] cartprod (x:xs) ys = putx ys where putx [] = cartprod xs ys putx (z:zs) = (x,z):(putx zs) cartprod ["A", "F"] ["Lt", "Ro", "Ser"] [("A","Lt"),("A","Ro"),("A","Ser"), ("F","Lt"),("F","Ro"),("F","Ser")] Homework Can you implement cartprod in a different manner? Think! (courtesy of IBM & Auguste Rodin) Think! Example (Given the above, what does this function do?) ors s = foldr (++) [] (map perm (powerset s)) Main> ors [1,2,3] Think! Example (And how about this one ?) c [] = [[]] c (x:xs) = c xs ++ map (x:) (c xs) Example (A trace) c [1,2,3] = c [2,3] ++ map (1:) c [2,3] = (c ++ map (2:) c ) ++ map (1:) c [2,3] =((c [] ++ map (3:) c []) ++ map (2:) c ) ++ map (1:) c [2,3] =(([[]] ++ map (3:) [[]]) ++ map (2:) c ) ++ map (1:) c [2,3] =(([[]] ++ ) ++ map (2:) c ) ++ map (1:) c [2,3] Think! Example (And how about this one ?) c [] = [[]] c (x:xs) = c xs ++ map (x:) (c xs) Example (A trace) =([[],] ++ map (2:) [[],]) ++ map (1:) c [2,3] =([[],] ++ [,[2,3]]) ++ map (1:) c [2,3] =[[],,,[2,3]] ++ map (1:) c [2,3] =[[],,,[2,3]]++map(1:)[[],,,[2,3]] =[[],,,[2,3]]++[,[1,3],[1,2],[1,2,3]] =[[],,,[2,3],,[1,3],[1,2],[1,2,3]] A problem by Euler In how many ways can we triangulate a convex polygon by non-intersecting diagonals? Counting triangulations Tn in a systematic way F E T3 = 1, T4 = 2 G D H C A B Counting triangulations Tn in a systematic way F E T3 = 1, T4 = 2 T8 = T7 + G D H C A B Counting triangulations Tn in a systematic way F E T3 = 1, T4 = 2 T8 = T7 + T6 ⇤ T3 + G D H C A B Counting triangulations Tn in a systematic way F E T3 = 1, T4 = 2 T8 = T7 + T6 ⇤ T3 + T5 ⇤ T4 + G D H C A B Counting triangulations Tn in a systematic way F E T3 = 1, T4 = 2 T8 = T7 + T6 ⇤ T3 + T5 ⇤ T4 + T4 ⇤ T5 + G D H C A B Counting triangulations Tn in a systematic way F E T3 = 1, T4 = 2 T8 = T7 + T6 ⇤ T3 + T5 ⇤ T4 + T4 ⇤ T5 + G D T3 ⇤ T6 + H C A B Counting triangulations Tn in a systematic way F E T3 = 1, T4 = 2 T8 = T7 + T6 ⇤ T3 + T5 ⇤ T4 + T4 ⇤ T5 + G D T3 ⇤ T6 + T7 H C A B Counting triangulations Tn in a systematic way F E T2 = 1, T3 = 1, T4 = 2 T8 = T7 ⇤ T2 + T6 ⇤ T3 + T5 ⇤ T4 + T4 ⇤ T5 + G D T3 ⇤ T6 + T2 ⇤ T7 H C A B Counting triangulations Tn in a systematic way F E T2 = 1, T3 = 1, T4 = 2 T8 = T7 ⇤ T2 + T6 ⇤ T3 + T5 ⇤ T4 + T4 ⇤ T5 + G D T3 ⇤ T6 + T2 ⇤ T7 8 1 X H C T8 = Ti ⇤ T8+1 i i=2 A B Counting triangulations Tn in a systematic way F E T2 = 1, T3 = 1, T4 = 2 T8 = T7 ⇤ T2 + T6 ⇤ T3 + T5 ⇤ T4 + T4 ⇤ T5 + G D T3 ⇤ T6 + T2 ⇤ T7 8 1 X H C T8 = Ti ⇤ T8+1 i i=2 n 1 X Tn = Ti ⇤ Tn+1 i i=2 A B Computing Tn ??? Formula n 1 X Tn = Ti ⇤ Tn+1 i i=2 Haskell code v1: straightforward, but not efficient t1 n | n Int divR a b = div a b *Main> divR 10 2 5 *Main> divR 10 0 *** Exception: divide by zero Haskell errors How to introduce Haskell errors error + a string describing the error Example (Errors in Haskell) divRE a b | b == 0 = error "div by 0, dude" | otherwise = div a b *Main> divRE 1 0 *** Exception: div by 0, dude CallStack (from HasCallStack): error, called at errdivRE.lhs:2:25 in main:Main Note Expression evaluation is stopped and the program crashes. Better options are available (we’ll meet them down the road) Haskell errors Example (Dealing with errors in a lazy language) divRE a b | b == 0 = error "div by 0, dude" | otherwise = div a b Main> head [divRE 2 2, divRE 2 0] 1 Catching errors Deferred until discussing monads. Binary trees as a new type Example (Binary tree: each node has at most 2 sub-trees) data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show) root let right Example t1=Node "A" (Node "B" Empty (Node "C" (Node "D" Empty Empty) Empty)) Empty :: Tree [Char] Binary trees as a new type Example (Tree height: equation(s) to cover each case) h2 :: Tree a -> Int h2 Empty = 0 h2 (Node _ l r) = 1 + max (h2 l) (h2 r) Example (Computing height) *Main> h2 t1 4 Example (Tree height, alternative implementation) height :: Tree a -> Int height t = case t of Empty -> 0 Node _ l r -> 1 + max (height l) (height r) Binary trees as a new type Example (Reflecting a tree) reflect :: Tree a -> Tree a reflect t = case t of Empty -> Empty > pardeclarat - Node v l r -> Node v (reflect r) In jus seata (reflect l) ↳ valaile Binary trees as a new type Example (Reflecting a tree) g1 = Node 1 (Node 2 (Node 4 Empty Empty) (Node 5 Empty Empty)) (Node 3 (Node 6 Empty Empty) Empty) :: Tree Int *Main> reflect g1 Node 1 (Node 3 Empty (Node 6 Empty Empty)) (Node 2 (Node 5 Empty Empty) (Node 4 Empty Empty)) Binary trees as a new type Example (Reflecting a tree) *Main> g1 == reflect (reflect g1) No instance for (Eq (Tree Int)) arising from a use of ’==’ Tree to list Example (Preorder) preord t = case t of Empty -> [] Node v l r -> (v:preord l) ++ (preord r) *Main> preord g1 [1,2,4,5,3,6] Tree to list Remark Append (++) is expensive: O(n2 ) CONS operations Example (Preorder with a ”collecting” parameter) preordA t vs = case t of Empty -> vs Node v l r -> v:preordA l (preordA r vs) *Main> preordA g1 [] [1,2,4,5,3,6] Binary search tree Binary Search Trees v. Association Lists 1. both store info as (key,value) pairs 2. search time: O(log n) (v. O(n) for AL) 3. type of key: Ord for BST (v. Eq suffices for AL) Binary search tree Example (Searching in a binary search tree) data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show) searchB :: Ord t1 => t1 -> Tree (t1, t) -> t searchB s t = case t of Empty -> error "key missing" A Node (k,v) l r -> case (s == k) of True -> v False -> case s < k of True -> searchB s l False -> searchB s r Binary search tree Example (Searching in a binary search tree) dict1 = Node ("dos", 2) (Node ("cinque", 5) Empty Empty) (Node ("tres", 3) (Node ("quatro", 4) Empty Empty) (Node ("uno", 1) Empty Empty)) *Main> searchB "tres" dict1 3 Binary search tree Example (Inserting nodes in a binary search tree) insertB :: Ord t1 => t1 -> t -> Tree (t1, t) -> Tree (t1, t) insertB nk nv t = case t of Empty -> Node (nk, nv) Empty Empty Node (k,v) l r -> case nk == k of True -> error "Key already present" False -> case nk < k of True -> Node (k,v) (insertB nk nv l) r False -> Node (k,v) l (insertB nk nv r) *Main> insertB "seis" 6 dict1 Node ("dos",2) (Node ("cinque",5) Empty Empty)... Side effect - printing on the screen Example (Print trees: rely on what Haskell Show provides) data Mytree t = Empty | Node t (Mytree t) (Mytree t) deriving (Show) t3 = Node 3 (Node 1 Empty Empty) (Node 4 Empty (Node 5 Empty Empty)) *Main> t3 Node 3 (Node 1 Empty Empty) (Node 4 Empty (Node 5 Empty Empty)) Side effect - printing on the screen Example (Write your own show to pretty print trees) data Mytree t = Empty | Node t (Mytree t) (Mytree t) instance (Show t) => Show (Mytree t) where show = pT 0 where pInd i = [ ’ ’ | k t3 3 1.. 4. 5.. Side effect - printing on the screen Remark In solution #2, we have specified the constraint (Show t). So, when overloading show for trees, we can use (show v) and the tree printing function will work regardless the actual type of the values stored in the tree (if they are showable). Propositional logic Components 1. atoms: a,b,... 2. connectors: ¬, ^, _ (printed as ˜, &, |) Example (A type for representing propositions) data Prop = Atom String | Neg Prop | Or Prop Prop | And Prop Prop Example (Representing proposition a ^ (b _ c)) ex1 = And (Atom "a") (Or (Atom "b") (Atom "c")) Will be printed as: a & (b |c) Propositional logic Example (A type for representing propositions) data Prop = Atom String | Neg Prop | Or Prop Prop | And Prop Prop Example (Representing Implication: p ! q ⌘ ¬p _ q) imply p q = Or (Neg p) q Propositional logic Example (Pretty printing propositions) instance Show Prop where show = prtP 0 where prec oper = case oper of -- op precedence Atom _ -> 4 Neg _ -> 3 And _ _ -> 2 Or _ _ -> 1 Propositional logic Example (Pretty printing propositions) prtP cpl prop = let ppl = prec prop prnopar = case prop of --with no parentheses Atom p -> p Neg p -> "˜" ++ prtP ppl p And p q -> prtP ppl p ++ " & " ++ prtP ppl q Or p q -> prtP ppl p ++ " | " ++ prtP ppl q in if (ppl > cpl) then prnopar else "(" ++ prnopar ++ ")" Negative Normal Form (NNF): negation on atoms only Conversion to NNF: move negation inwards (1) ¬¬p replaced by p (2) ¬(p ^ q) replaced by ¬p _ ¬q (3) ¬(p _ q) replaced by ¬p ^ ¬q Example tonnf prop = case prop of Atom a -> Atom a --1 Neg (Atom a) -> Neg (Atom a) --2 Neg (Neg p) -> tonnf p --3 Neg (And p q)-> tonnf (Or (Neg p) (Neg q)) --4 Neg (Or p q) -> tonnf (And (Neg p) (Neg q)) --5 And p q -> And (tonnf p) (tonnf q) --6 Or p q -> Or (tonnf p) (tonnf q) --7 NNF and CNF (Conjunctive/Clausal Normal Form) Example (Obtaining NNF: ¬(p ! q) ⌘NNF p ^ ¬q) p = Atom "p" q = Atom "q" ni1 = Neg (imply p q) *Main> tonnf ni1 p & ˜q NNF and CNF (Conjunctive/Clausal Normal Form) Example (Obtaining NNF: ¬(p ! q) ⌘NNF p ^ ¬q) tonnf prop = case prop of Atom a -> Atom a --1 Neg (Atom a) -> Neg (Atom a) --2 Neg (Neg p) -> tonnf p --3 Neg (And p q)-> tonnf (Or (Neg p) (Neg q)) --4 Neg (Or p q) -> tonnf (And (Neg p) (Neg q)) --5 And p q -> And (tonnf p) (tonnf q) --6 Or p q -> Or (tonnf p) (tonnf q) --7 tonnf (Neg (imply (Atom "p") (Atom "q")))= --def of imply tonnf (Neg (Or (Neg (Atom "p")) (Atom "q")))= --5 tonnf (And (Neg (Neg (Atom "p"))) (Neg (Atom "q")))= --6 And (tonnf (Neg (Neg (Atom "p")))) (tonnf (Neg (Atom "q")))= --3 And (tonnf (Atom "p")) (tonnf (Neg (Atom "q")))= --2 And (Atom "p") (Neg (Atom "q")) NNF and CNF (Conjunctive/Clausal Normal Form) Definition (CNF of a sentence) p is in CNF if it is of form p1 ^... ^ pn , where pi is a disjunction of literals (atoms or negated atoms). Conversion from NNF to CNF p _ (q ^ r ) replaced by (p _ q) ^ (p _ r ) (q ^ r ) _ p replaced by (q _ p) ^ (r _ p) From NNF to CNF Conversion from NNF to CNF p _ (q ^ r ) replaced by (p _ q) ^ (p _ r ) (q ^ r ) _ p replaced by (q _ p) ^ (r _ p) Example (Distributivity) dist p (And q r) = And (dist p q) (dist p r) dist (And q r) p = And (dist q p) (dist r p) dist p q = Or p q From NNF to CNF Example (Obtaining CNF from NNF) tocnf prop = case prop of And p q -> And (tocnf p) (tocnf q) Or p q -> dist (tocnf p) (tocnf q) _ -> prop From NNF to CNF Example (¬(¬p _ q) _ ¬(p ^ q) ⌘NNF (p ^ ¬q) _ (¬p _ ¬q)) f2 = Or (Neg (Or (Neg (Atom "p")) (Atom "q"))) (Neg (And p q)) *Main> tonnf f2 p & ˜q | (˜p | ˜q) From NNF to CNF Example (Getting CNF: ¬(¬p _ q) _ ¬(p ^ q) ⌘CNF (p _ (¬p _ ¬q)) ^ (¬q _ (¬p _ ¬q))) *Main> tonnf f2 p & ˜q | (˜p | ˜q) *Main> tocnf (tonnf f2) (p | (˜p | ˜q)) & (˜q | (˜p | ˜q)) Definition (Tautology) Tautology = a sentence which is always true. Testing whether a sentence is a tautology 1. put it into CNF (p1 ^... ^ pn ) and check if pi is a tautology for every i between 1 and n 2. a disjunctive formula q1 _... _ qm is a tautology iff there is a literal which appears both as an atom and as it negate... 3.... so separately collect all positive and all negative atoms in that formula and check if the two sets are not disjoint Testing if a formula is a tautology Example (Collect positive atoms) getpos prop = case prop of Atom a -> [a] Neg (Atom _) -> [] Or p q -> (getpos p) ++ (getpos q) _ -> error "proposition not in CNF" Example (Collect negative atoms) getneg prop = case prop of Atom _ -> [] Neg (Atom a) -> [a] Or p q -> (getneg p) ++ (getneg q) _ -> error "proposition not in CNF" Testing if a formula is a tautology Example (Is it a tautology?) istaut prop = case prop of And p q -> (istaut p) && (istaut q) _ -> not (null [ a | a istaut (tocnf (tonnf tau1)) True Example Why do we need a tautology checker? Summary I error causes evaluation to stop and crash. Avoid! I Constructors can help handling heterogenous structures (e.g. trees) I Side effects help pretty printing trees I It is easy to implement a propositional reasoner in functional manner. Functional Programming Radu Răzvan Slăvescu Technical University of Cluj-Napoca Department of Computer Science Outline Functions as data (.) for function composition map and filter revisited fold family takeWhile and alike Remember: functions Remark: First class citizenship for functions In FP, functions could be regarded even as data 1. functions can be arguments or results of functions 2. functions can be elements of lists First order functions versus higher-order functions Definition (First order function) Its arguments and returned result are both data Definition (Higher-order function, aka functional) Its arguments, returned result, or both, are functions Remarks: advantages of Higher-order functions 1. One can add programming idioms as functions into the language itself hence higher abstraction and reuse 2. Their algebraic properties help in reasoning on programs Functions as data Example (A function sent as a parameter) myinser x [] _ = [x] myinser x (y:ys) orel > (x) San(4 - | orel x y = x:y:ys > sternet bita normal - | otherwise= y:myinser x ys orel (x)(4) - * Emul litei un nowl cap mysortins [] _ = [] mysortins (x:xs) orel = myinser x (mysortins xs orel) orel f a b = a mysortins [3,1,2,1,4] f [1,1,2,3,4] *Main> mysortins [3,1,2,1,4] ( mysortins [3,1,2,1,4] (\x y -> x>=y) [4,3,2,1,1] 32194 37 32411 321 41 172F = 34211 131F Remark 174F 43217 Here, orel is a function which compares two entities; it is passed to inser and tells in which order the list will be sorted Functions as data Example (A list of functions) processWage :: [t -> t] -> t -> t processWage [] w = w areful fait ene processWage lop w = processWage (tail lop) apli ↓ (head lop w) perme Extract an element from a list of functions and use it: fance *Main> processWage [\ w -> w - 25.00, \ w -> 0.65 * w, \ w -> 0.90 * w] 1025.00 585.0 When are two functions equal? Function equality: when are two functions equal? (i) same expressions v. (ii) same results for identical arguments Definition (Extensional equality of functions) f and g are extensionally equal (f = g) iff 8 x : f x = g x Example (Functions as data) *Main> i1 x = x+x -- same as i1 = \x -> x+x *Main> i2 x = 2*x -- extensionally equal to i1 *Main> i3 = i1 -- "copy" body of i1 *Main> i1 4 8 *Main> i2 4 8 Functions as data Example (Functions as data) *Main> i3 4 8 *Main> i1 x = x+x+1 *Main> i1 4 9 *Main> i3 4 8 The functional composition Definition (Function composition: (f. g) x = f (g x)) (.) :: (b -> c) -> (a -> b) -> a -> c f. g = \ x -> f (g x) Example (Functional composition) Main> map (not. odd) [1..5] [False,True,False,True,False] odd :: Integral a => a -> Bool not :: Bool -> Bool not. odd :: Integral a => a -> Bool (.) :: (b -> c) -> (a -> b) -> a -> c The functional composition Example (Functional composition) odd :: Integral a => a -> Bool not :: Bool -> Bool not. odd :: Integral a => a -> Bool (.) :: (b -> c) -> (a -> b) -> a -> c Remark Functions odd, not and not. odd are first order. On the other hand, (.) is a higher-order function (or operator). It builds a new, nameless function from its operands not and odd, which is then sent as an argument to map. The functional composition Example (Function composition exercise) Guess (1) Type; (2) example call (3) reasonable name for: ((length. ). filter) Function application Definition (Function application operator) infixr 0 $ ($) :: (a -> b) -> a -> b f $ x = f x Example sum (map (ˆ2) (filter (>0) [1,2,-2,3])) same as with this more readible one: sum $ map (ˆ2) $ filter (>0) [1,2,-2,3] Remember: The higher-order function map Definition (Map) It applies a given function on every element of a list. Example (Haskell map) Prelude> map (\ x -> x*x) [1,2,3] [1,4,9] Example (Defining map using list comprehensions) mapGen :: (a->b) -> [a] -> [b] mapGen f xs = [ f x | x filter odd [1..5] [1,3,5] Example (Defining filter using list comprehenions) filterGen :: (a -> Bool) -> [a] -> [a] filterGen p xs = [ x | x b -> b) -> b -> [a] -> b would incorporate this pattern, with the operation and the v value as parameters. Operator should be right associative. Remember: some higher-order functions on lists Example (Haskell foldr) Prelude> foldr (*) 1 [1,2,3] 6 Example (New definitions for sum and and) mynewsum = foldr (+) 0 mynewand = foldr (&&) True Understanding foldr foldr One can regard foldr as simultaneously replacing (:) in a list by and [] by v. The operator should be right associative. Example mynewsum [1,2,3] = foldr (+) 0 [1,2,3] = foldr (+) 0 (1:(2:(3:[]))) = (1+(2+(3+0))) = 6 Example (But what if we do this?) *Main> foldr (-) 0 [1,2,3] 2 (1 (2 - - (3 - b) (1 (2 +3) = - Understanding foldr (Image source: wiki.haskell.org) Replace (:) by f and [] by v Some examples on lists Example (Reverse) myrev [] = [] myrev (x:xs) = myrev xs ++ [x] myrev [1,2,3] = myrev (1:(2:(3:[]))) = (([] ++ ) ++ ) ++ = [3,2,1] mynewrev = foldr (\ x xs -> xs ++ [x]) [] Some more examples on lists Example (Member) mynewmember e xs = foldr (||) False (map ((==) e) xs) Remark Here, we map the equality-to-e-test on list xs and get a list of True and False values with the same length as xs; folding (||) on it tells us whether there is at least one True inside. Example (Append) mynewappend xs = foldr (:) xs Example mynewflatten = foldr (++) [] All and any Example (All: every element satisfies a predicate) - - mynewall p xs = foldr (&&) True (map p xs) - - True 00 Main> mynewall odd [1,3] && Main> mynewall odd [1,2,3] False Example (Any: at least one element satisfies a predicate) mynewany p xs = foldr (||) False (map p xs) The higher-order function foldl foldl Many functions are defined using the following pattern: f v [] =v f v (x : xs) = f (v x) xs In Haskell, this pattern is incorporated by the function foldl :: (a -> b -> a) -> a -> [b] -> a It has operation and the v value as first two parameters. should be left associative. Understanding foldl Haskell foldl foldl ( ) v [x0 , x1 ,... , xn ] = (((v x0 ) x1 )...) xn = (((v x0 ) x1 )...) xn =... = (((v x0 ) x1 )...) xn Understanding foldl (Image source: wiki.haskell.org) Reflect tree Reverse list Replace (:) and [] foldr v. foldl Example Example Prelude> foldr (++) "r" Prelude> foldl (++) "r" ["o", "t", "t", "e"] ["o", "t", "t", "e"] "otter" "rotte" foldr v. foldl Remember Haskell operator (ˆ) is right associative: 4ˆ3ˆ2 = 4ˆ(3ˆ2) 2 2 (i.e., 43 = 4(3 ) = 262144, as opposite to (43 )2 = 4096) Example (Your turn) Prelude> foldr (ˆ) 1 [2,2,2] 16 Prelude> foldl (ˆ) 1 [2,2,2] 1 Prelude> foldl (ˆ) 2 [2,2,2] 256 Prelude> foldr (ˆ) 2 [2,2,2] 65536 foldr v. foldl Remark 1. foldl is related to tail recursion 2. sometimes, foldr can give the answer, but foldl cannot Example *Main> foldr (&&) True [ False, False..] False *Main> foldl (&&) True [ False, False..] ˆCInterrupted. Understanding foldl Elm foldl foldl ( ) v [x0 , x1 ,... , xn ] = xn (... (x1 (x0 v )))... ) = xn (... (x1 (x0 v ))... ) =... = xn (... (x1 (x0 v ))... ) Understanding foldl Example > import List as L L.foldl (+) 0 [1,2,3] = L.foldl (+) 0 (1:(2:(3:[]))) = 3+(2+(1+0)) = 6 Example (But what if we do this?) *Main> L.foldl (-) 0 [1,2,3] 2 Understanding foldl Haskell-style v. Elm-style foldl Elm preserves the signature of foldr: > List.foldr : (a -> b -> b) -> b -> List a -> b > List.foldl : (a -> b -> b) -> b -> List a -> b Haskell swaps the parameters of the operation. Prelude> :t foldr foldr :: (a -> b -> b) -> b -> [a] -> b Prelude> :t foldl foldl :: (b -> a -> b) -> b -> [a] -> b Your turn Example (Warming up) ra = foldl (\ xs x -> x:xs) [] Main> ra [1,2,3] [3,2,1] Your turn Example (Yet another one) fl210 = foldl (\ y x -> x+2*y) 0 01 - ) 2 Main> fl210 [1,0,1,1] 12 - )+ 4 5 = 11 157 1 + 18 = 11 Example (And the last one) f :: [Integer] -> Integer f l = foldr (\ x y -> x+2*y) 0 (reverse l) Main> f [1,0,1,1] 11 foldl’ Remark A strict version of foldl. Example Prelude> import Data.List Prelude Data.List> foldl’ (+) 0 [1..100000000] 5000000050000000 (2.67 secs, 8,800,076,312 bytes) Prelude Data.List> foldr (+) 0 [1..100000000] *** Exception: stack overflow Remark Usually, you’ll have to choose between foldr and foldl’. foldl1 Definition foldl1 :: (a -> a -> a) -> [a] -> a foldl1 f (x:xs) = foldl f x xs Remark Similar to foldl, but the argument cannot be an empty list. Example (Lowest value in a list: Haskell minimum) minimum :: Ord a => [a] -> a minimum = foldl1 min min :: Ord a => a -> a -> a returns the lowest of its two arguments foldr1 Definition foldr1 :: (a -> a -> a) -> [a] -> a foldr1 _ [x] = x foldr1 f (x:xs) = f x (foldr1 f xs) Remark Similar to foldr, but the argument cannot be an empty list. Example (Haskell unwords) *Main> foldr1 (\s ss -> s ++ " " ++ ss) ["no", "trailing", "space"] "no trailing space" scanl Definition myscanl :: (b -> a -> b) -> b -> [a] -> [b] myscanl f v [] = [v] myscanl f v (x:xs) = v : myscanl f (f v x) xs Remark Similar to foldl, but returns the list of partial values from left. Example Main> scanl (+) 0 [10, 12, 15] [0,10,22,37] The power of fold Example reversef xs = foldl (\ xs x -> x:xs) [] xs lengthf xs = foldl (\ n _ -> n+1) 0 xs mapf f xs = foldr (\ y ys -> (f y):ys) [] xs filterf p xs = foldr (\ y ys -> if (p y) then y:ys else ys) [] xs Some more higher-order functions Some more higher-order functions unfold with arguments p, h, t, x unfold p h t x | p x = [] | otherwise = (h x) : unfold p h t (t x) If p x is true, then return an empty list (end of story) else put h x as the first element of the result and call t x to generate the rest of the result, which will be processed in a similar manner Example (unfold) *Main> unfold (==0) (‘mod‘ 2) (‘div‘ 2) 11 11 % 2 = 15 % 2 12% 2:0 : [1,1,0,1] - 11/2 = 5 3/2 2 2/2 : / : 1 %2 : / 1/2 : 8 Some more higher-order functions unfold with arguments p, h, t, x unfold p h t x | p x = [] | otherwise = (h x) : unfold p h t (t x) Example (Your turn) unfold (null) ((2*). head) (tail) [1,2,3] 2 , 3 , 9 Some more higher-order functions takeWhile Select elements of a list as long as they satisfy a predicate. mytakeWhile :: (a -> Bool) -> [a] -> [a] mytakeWhile _ [] = [] mytakeWhile p (x:xs) | p x = x:mytakeWhile p xs | otherwise = [] Example (takeWhile) *Main> mytakeWhile (odd) [1,3,5,6,7,8] [1,3,5] Some more higher-order functions dropWhile Remove elements of a list as long as they satisfy a predicate. Example (dropWhile) *Main> mydropWhile (odd) [1,3,5,6,7,8] [6,7,8] Some more higher-order functions span Split a list at the first element not satisfying a predicate. myspan p xs = (takeWhile p xs, dropWhile p xs) Example (span) *Main> myspan (odd) [1,3,5,6,7,8] ([1,3,5],[6,7,8]) span v. splitAt mysplitAt Split a list at a given index mysplitAt n xs = (take n xs, drop n xs) take 2 [1 , 3, 5 , 6 7, 3) Example (mysplitAt) , *Main> mysplitAt 2 [1,3,5,6,7,8] ([1,3],[5,6,7,8]) Using higher-order functions Example (Your turn) i xs ys = filter (combC elem ys) xs where combC f x y = f y x Example (Your turn) l xs = foldr (+) 0 (map (combK 1) xs) where combK k _ = k Example (Your turn) ll = (foldr (+) 0). (map (combK 1)) where combK k _ = k Using higher-order functions Example (Your turn) lll :: [Int] -> Int lll = foldr (\_ n -> 1+n) 0 Example (Your turn) m f = foldr ( (:). f ) [] Using higher-order functions Example (Your turn) li = "Now I need a drink, alcoholic sugarfree of course, after the heavy lectures involving magical functions, and pi, and formulas, when people go really mad but thriving " p = map length. hew []. filter (/=’,’) where hew a "" = reverse a hew a cs = let (f,s) = span (/=’ ’) cs in hew (f:a) (tail s) Summary I in FP, data and functions can be regarded in the same way I map and filter iterate structures and separate structure traversal from element processing I fold family members combine elements of a data structure, according to a given operator, into one value Functional Programming Radu Răzvan Slăvescu Technical University of Cluj-Napoca Department of Computer Science Outline Lazy evaluation Data streams in circular structures Memoization via circular structures Challenge: consecutive colors in a deck of cards Challenge Consider a deck of 52 cards, half of which are red (both hearts and diamonds are so) and the others black (spades and clubs). You shuffle the deck, cut the cards and start looking at them. Find out the probability (3 digits) to see at least one sequence of at least 5 cards of the same color (either red or black). Your solution should scale for the case of k decks mixed up. Lazy evaluation Example (Lazy data) Prelude> let x = 1+2 :: Int Prelude> :sprint x -- print only, no evaluation x = _ -- x is unevaluated, it is just a thunk Prelude> x -- this will force evaluation 3 Prelude> :sprint x x = 3 -- thunk has been replaced by its value Lazy evaluation Example (Lazy data) Prelude> let x = 1+2 :: Int Prelude> let y = x+1 :: Int Prelude> :sprint x x = _ Prelude> :sprint y y = _ Lazy evaluation Example (Lazy data) --seq evaluates arg #1 then returns arg #2 Prelude> seq y () () Prelude> :sprint y y = 4 Prelude> :sprint x x = 3 -- thunk evaluated because of y Lazy evaluation Example (Lazy recursive data structures and WHNF) --map builds a lazy data structure map f [] = [] map f (x:xs) = x’ : xs’ where x’ = f x -- thunk xs’ = map f xs -- also a thunk Prelude> let xs = map (*2) [1..5] :: [Int] Prelude> seq xs () () Prelude> :sprint xs xs = _ : _ --evaluate up to the first constructor --xs is now in weak head normal form (WHNF) Lazy evaluation Weak Head Normal Form (WHNF) An expression is in Weak Head Normal Form if it is either: I a constructor (eventually applied to arguments), e.g., True, Just 42 or ((:) 1) I or a lambda abstraction \ x -> expression I a built-in function applied to too few arguments, e.g., (+) 2 or sqrt Adapted from: https://wiki.haskell.org/Weak_head_normal_form Remark If the outermost part of expression E is a constructor or a lambda abstraction, then E is in WHNF. Lazy evaluation Example (Lazy data structures) Prelude> :sprint xs xs = _ : _ Prelude> length xs 5 Prelude> :sprint xs xs = [_,_,_,_,_] --structure generated Prelude> sum xs 30 Prelude> :sprint xs xs = [2,4,6,8,10] (Examples from S. Marlow. Parallel and Concurrent Programming in Haskell. O’Reilly Media, 2013, Chapter 2) Lazy evaluation Definition (Function seq) seq x y evaluates x to WHNF and returns y Example (foldl’) foldl’ o z [] = z foldl’ o z (x:xs) = let z’ = z ‘o‘ x in seq z’ $ foldl’ o z’ xs Lazy evaluation: one piece at a time Customer: ”I could use a couple of Cuba Libres” Bar tender: ”Here you are. The first one. I’m ready to prepare the next. Just let me know when you need it” Lazy evaluation: infinite lists Example (A (potentially) infinite list of 2s) Prelude> twos = [2,2..] Prelude> take 5 twos [2,2,2,2,2] Remark One can extract as many elements from this list as needed. Lazy evaluation: infinite lists Example (Turner’s Eratosthenes-like sieve revisited) sv (p:ns) = p : sv [ n | n 0] primes = sv [2..] Trace sketch sv [2..] = 2 : sv on all odd numbers (first: 3) = 2 : 3 : sv on all odd numbers not divisible by 3 (first: 5) = 2 : 3 : 5 : sv on all odd numbers not divisible by 3 or 5... Evaluation termination? primes: no; a prefix of it: yes Prelude> take 5 primes [2,3,5,7,11] Lazy evaluation: only what we need Example (Minimum of a list using insert sort) [1 5, 9 3) , sorti [] = [] , sorti (x:xs) = ins x (sorti xs) where ins ins x [] x (y:ys) = [x] | x fi !! 4 3 Prelude> :sprint fi fi = 0 : 1 : 1 : 2 : 3 : _ memoize computed results Memoization Example (Fibonacci, take 2) Prelude> fi = 0:1:zipWith (+) fi (tail fi) :: [Int] Prelude> fi !! 4 3 Prelude> :sprint fi Prelude> fi = 0 : 1 : 1 : 2 : 3 : _ Remark Lazy evaluation together with circular structures allow elegant memoization, sometimes with zero effort from the programmer. Pn 1 Polygon triangulation once again Tn = i=2 Ti ⇤ Tn+1 i Example (Haskell v2: cache in a list accumulator) t2 n = t2a 1 where t2a k cs | k == n-1 = head cs | otherwise = t2a (k+1) (cn:cs) where cn = sum (zipWith (*) cs (reverse cs)) Example (Haskell v3: memoize via circular lists) ntrsq = 1:1:map (\ n -> sum (comb n)) [4..] where comb n = let uptos = take (n-2) ntrsq in zipWith (*) uptos (reverse uptos) Pascal Triangle Example (Building the triangle) Row 0: just a 1 Row k: add the two neighbors just above (if absent, assume 0) 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 Pascal Triangle Example (Build the triangle: map on a circular structure) pascalSeq = let infix 6 &: x &: xs = xs ++ [x] in : (map (\r -> zipWith (+) (0:r) (0&:r))) pascalSeq Example (A one-liner for the triangle) ps=:map (\r->zipWith (+) (0:r) (r++)) ps - & jucepe Gela 1 se atanga e lanifinal iniquit Summary 1. Lazy evaluation allows data potentially infinite 2. Lazy evaluation allows building circular structures. Data streams produced and used in processing networks 3. Code: elegant, concise, close to problem spec 4. A tradeoff with the overhead of the interpretor, garbage collector and debugger is needed For those eager to try something new... G. Hutton A Haskell implementation of Sudoku using lazy evaluation http://www.cs.nott.ac.uk/˜pszgmh/sudoku.lhs Functional Programming Radu Răzvan Slăvescu Technical University of Cluj-Napoca Department of Computer Science Outline One more example on data streams Haskell iterate Corecursion Challenge: ”quasi-static” Tiki Taka Tiki Taka style in football Tiki Taka style consists of quick passing and movement. Challenge Two players, C and D, are training on a standard pitch (105 ⇥ 68 meters). They have to practice Tiki Taka in a ”quasi-static” manner: the game starts with one of the playes, say C, having the ball. D makes no move and waits for the ball. Now C passes the ball to D, then runs to a random point, anywhere on the pitch. When D receives the ball, C stops and D passes it to C, in the precise position C is situated at that moment. Now D starts running and stops when C passes the ball to him, and so one. Come up with an assessment of the average length of a pass. You should either come with a Haskell implelementation, or with a mathematical proof. A circular structure for generating primes Example (Successsively eliminate multiples of primes) primes = let oPrs n | isPr n primes = n:oPrs (n+2) | otherwise = oPrs (n+2) isPr n (x:xs) | n < xˆ2 = True | n ‘mod‘ x == 0 = False | otherwise = isPr n xs in 2:oPrs 3 A circular structure for generating primes Example (A trace of primesGen) = 2:oPrs 3 [isPr 3 (2:... ) = True] = 2:3:oPrs 5 [isPr 5 (2:3:... ) = isPr 5 (3:... ) = True] = 2:3:5:oPrs 7 [isPr 7 (2:3:... ) = isPr 7 (3:... ) = True] = 2:3:5:7:oPrs 9 [isPr 9 (2:3:... ) = isPr 9 (3:... ) = False] = 2:3:5:7:oPrs 11 [isPr 11 (2:3:5... ) = isPr 11 (3:5... ) = isPr 11 (5..) = True] =... Iteratively calling a function in Haskell Definition (Haskell function iterate) iterate :: (a -> a) -> a -> [a] iterate f x = x : iterate f (f x) Iterates the call of f and builds the infinite sequence [x, f(x), f(f(x)),...] Example (Haskell function iterate) iterate (*2) 1 = 1 : iterate (*2) ((*2) 1) = 1 : 2 : iterate (*2) ((*2) 2) = 1 : 2 : 4 : iterate (*2) ((*2) 4) =... Iteratively calling a function in Haskell Haskell function iterate iterate :: (a -> a) -> a -> [a] iterate f x = x : iterate f (f x) Example (Haskell function iterate) Prelude> take 5 $ iterate tail [1,2,3,4] [[1,2,3,4],[2,3,4],[3,4],,[]] Prelude> take 5 $ iterate ((ˆ2). (+1). sqrt) 1.0 [1.0,4.0,9.0,16.0,25.0] p Computing a iteratively p Example (The ”Babylonian method” for a) start with an initial approximation x0 repeat xk+1 = (a / xk + xk ) / 2 until a stopping criterion is met (e.g. a given number of iterations is reached or 2 consecutive approximations are ”very close” to each other) nextap :: Double -> Double -> Double nextap a capx = (a / capx + capx) / 2.0 p Computing a iteratively p Example (Approximating 3) nextap :: Double -> Double -> Double nextap a capx = (a / capx + capx) / 2.0 We arbitrarily set the initial approximation value (capx) to 1.0. A manual trace of the first iterations will give: *Main> nextap 3.0 1.0 2.0 *Main> nextap 3.0 2.0 1.75 *Main> nextap 3.0 1.75 1.7321428571428572 p Computing a iteratively p Example (Approximating 3) nextap :: Double -> Double -> Double nextap a capx = (a / capx + capx) / 2.0 *Main> take 5 $ iterate (nextap 3.0) 1.0 [ 1.0, 2.0, 1.75, 1.7321428571428572, 1.7320508100147274 ] p Computing a iteratively Definition (Stopping criterion: ”very close” approximations) Instead of stopping after a given number of iterations, we’ll stop when the difference between two consecutive terms is smaller, in absolute value, than a preset value ✏ (they are ”very close”). stopIt eps (ac:an:as) | veryClose eps ac an = an | otherwise = stopIt eps (an:as) where veryClose eps a1 a2 = abs (a1-a2) < eps p Computing a iteratively p Example (Approximating 3) nextap a capx = (a / capx + capx) / 2.0 stopIt eps (ac:an:as) | veryClose eps ac an = an | otherwise = absdif eps (an:as) where veryClose eps a1 a2 = abs (a1-a2) < eps aproxSqrt a eps = stopIt eps (iterate (nextap a) 1.0) *Main> aproxSqrt 3 10E-5 1.7320508100147274 PageRank algorithm Definition (PageRank score of node in a directed graph) 1 d X PR(pj ) PR(pi ) = +d N L(pj ) pj 2M(pi ) where: p1 ,... , pN are graph nodes (=pages) N is the number of nodes in the graph M(pi ) is the set of nodes that send links to pi L(pj ) is the number of outbound links of node pj d is a damping factor (usually 0.85) Remark The score of node N depends on the scores of the nodes sending links towards N. PageRank algorithm Example A B C D 1 d X PR(pj ) PR(pi ) = +d N L(pj ) pj 2M(pi ) PageRank algorithm Example type Name = String type Degree = Int type Node = (Name, [Name], Degree) type Graph = [Node] type Score = Double type Ranks = [(Name, Score)] d = 0.85 :: Double --dampening factor dimG = 4 :: Int --number of nodes in the graph prec = 10E-5 :: Double --convergence precision PageRank algorithm Example outDegree :: Name -> Graph -> Degree outDegree n ((c,_,d):nds) | n==c = d | otherwise = outDegree n nds nodesIn :: Name -> Graph -> [Name] nodesIn n ((c,ins,_):nds) | n==c = ins | otherwise = nodesIn n nds nodeRank :: Name -> Ranks -> Score nodeRank n ((c,r):ranks) | n==c = r | otherwise = nodeRank n ranks PageRank algorithm Example nodeUpdate :: Name -> Graph -> Ranks -> Score nodeUpdate n graph ranks = (1-d) / (fromIntegral dimG) + d * s where s = sum [ (nodePass i graph ranks) | i Graph -> Ranks -> Score nodePass n graph ranks = (nodeRank n ranks) / (fromIntegral (outDegree n graph)) PageRank algorithm Example veryClose :: Double -> Ranks -> Ranks -> Bool veryClose eps cranks pranks = foldr (&&) True $ zipWith (\ (_,c) (_,p) -> abs (c-p) < eps) cranks pranks stopIt :: Double -> [Ranks] -> Ranks stopIt eps (pi:ci:nis) | veryClose eps pi ci = ci | otherwise = stopIt eps (ci:nis) PageRank algorithm Example ranksUpdate :: Graph -> Ranks -> Ranks ranksUpdate graph ranks = map (\(n,r) -> (n, nodeUpdate n graph ranks)) ranks pageRank :: Double -> Graph -> Ranks -> Ranks pageRank prec graph ranks = stopIt prec $ iterate (ranksUpdate graph) ranks PageRank algorithm Example A B C D g1 = [("A", ["C"], 2), ("B", ["A"], 1), ("C", ["A", "B", "D"], 1), ("D", [], 1) ] :: Graph r100 = [("A", 0), ("B", 1), ("C", 1), ("D", 2) ] :: Ranks PageRank algorithm Example A B C D *Main> pageRank prec g1 r100 [("A",0.3730180867176842), ("B",0.1960695295812611), ("C",0.3946404722701038), ("D",3.7500000000000006e-2)] Corecursion: dual of recursion Definition (Corecursion) Start from a base case and iteratively produce data, based on a recursive relation, in a potentially infinite sequence. Example (Build a factorials sequence using corecursion) fseq = iterate (\(n,f) -> (n+1, f*(n+1))) (0,1) Trace [(0,1), (0+1,1*(0+1)) = (1,1), (2,2), (3,6)... Example (Factorial with corecursion) factorial n = snd (fseq !! n) where fseq = iterate (\(n,f) -> (n+1, f*(n+1))) (0,1) Corecursion: dual of recursion Example (Fibonacci, once again) fibo n = trd (fiboseq !! n) where fiboseq = iterate (\(n,f1,f2) -> (n+1, f2, f1+f2)) (0,1,0) trd (_,_,c3) = c3 Remark: recursion v corecursion Recursion progresses towards ”smaller” structures; corecursion progresses towards ”larger” structures. Pascal Triangle Example (Build the triangle via iterate) pascalSeq = let infix 6 &: x &: xs = xs ++ [x] in iterate (\l -> zipWith (+) (0:l) (0&:l)) Summary 1. A program can be seen as a network of circular structures which produce and consume data streams 2. iterate can be used to implement iterative algorithms. To this end, you have to specify: I a function to ”connect” two consecutive iterations I a criterion for stopping the process 3. corecursion: start from a base case and iteratively produce data, according to a recursive relation, in a potentially infinite structure Functional Programming Radu Răzvan Slăvescu Technical University of Cluj-Napoca Department of Computer Science Outline Functors Applicatives Functions generic over a range of parameterized types Abstracting out common patterns I mapping: Functor I function application: Applicative I effectful programming: Monads Maybe: a new type for dealing with context data Maybe a = Nothing | Just a deriving (Show) Observations I Just can be regarded as a ”wrapper” or as a context I A value of type Maybe a either ”wraps” a value of type a (in case of Just a) or is empty (in case of Nothing) I This way, we can convey the idea of success or failure I Applying functions on ”wrapped” values could lead to different results, depending on the ”wrapper“ (i.e., context) I deriving (Show) makes Maybe showable: a value of this type can be converted into a string and displayed I Haskell can use its type system to build stateful programs (we’ll see soon how this is done via Monads) class: introducing a new typeclass Definition (Typeclass) A set of types that support some methods (i.e., behavior) Example (Introducing the class Eq of equality types) --this is how we specify a typeclass class Eq a where -- declare its methods + their types (==), (/=) :: a -> a -> Bool (x /= y) = not (x == y) Remark If type a wants to be an instance of class Eq, then it must provide an operator of the specified type for testing equality (one for inequality testing is provided by default). class: introducing a new typeclass Example (Make Bool into an equality type) instance Eq Bool where False == False = True True == True = True False == True = False True == False = False Remarks I we have simply provided an implementation for (==) I actually, Bool uses deriving to be made into an Eq type: data Bool = F

Use Quizgecko on...
Browser
Browser