An Introduction To Programming In Haskell

2y ago
41 Views
2 Downloads
1.88 MB
58 Pages
Last View : 2m ago
Last Download : 2m ago
Upload by : Rafael Ruffin
Transcription

An Introduction toProgramming in HaskellMark P JonesPortland State University1

Haskell Resources:2

Haskell Resources:The focal point for information aboutHaskell programming, implementations,libraries, etc is www.haskell.orgI’ll be using: the Hugs interpreter (haskell.org/hugs)the Glasgow Haskell compiler, GHC, andinterpreter, GHCi (haskell.org/ghc)Online tutorials/references: learnyouahaskell.combook.realworldhaskell.org3

The Language Report:The definition of the Haskell 98standardLots of technical details not agreat read!Available in hard copy fromCambridge University PressOr in pdf/html/etc fromwww.haskell.org/definition4

Textbooks:Introduction to Functional Programming usingHaskell (2nd edition), Richard BirdThe Haskell School of Expression, Paul HudakHaskell: The Craft of Functional Programming(2nd edition), Simon ThompsonProgramming in Haskell, Graham Hutton5

What is FunctionalProgramming?6

What is Functional Programming?Functional programming is a style ofprogramming that emphasizes theevaluation of expressions, rather thanexecution of commandsExpressions are formed by using functionsto combine basic valuesA functional language is a language thatsupports and encourages programming in afunctional style7

Functions:In a pure functional language:The result of a function depends only onthe values of its inputs: Like functions in mathematicsNo global variables / side-effectsFunctions are first-class values: They can be stored in data structuresThey can be passed as arguments or returnedas results of other functions8

Example:Write a program to add up thenumbers from 1 to 109

In C, C , Java, C#, :initializationinitializationint tot 0;for (int i 1; i 10; i )tot tot i;iterationupdateupdateimplicit result returned in the variable tot10

In ML:accumulating parameterlet fun sum i tot if i 10then totelse sum (i 1) (tot i)in sum 1 0endinitialization(tail) recursionresult is the value of this expression11

In Haskell:sum [1.10]combiningfunctionthe list of numbers to addresult is the value of this expression12

Raising the Level of Abstraction:"If you want to reduce [design time], youhave to stop thinking about something youused to have to think about.” (Joe Stoy,recently quoted on the Haskell mailing list)Example:Example:Example:Example:memory allocationdata representationorder of evaluation(restrictive) type annotations13

Computing by Calculating:Calculators are a great toolfor manipulating numbersButtons for: entering digitscombining valuesusing stored values42.0!Not so good for manipulatinglarge quantities of dataNot good for manipulatingother types of data14

Computing by Calculating:What if we could “calculate”with other types of value?Buttons for: entering pixelscombining picturesusing stored picturesI wouldn’t want to calculate awhole picture this way!I probably want to deal withseveral different types of data atthe same time15

Computing by Calculating:Spreadsheets arebetter suited fordealing with largerquantities of dataValues can benamed (but not operations)Calculations (i.e., programs) are recorded so thatthey can be repeated, inspected, modifiedGood if data fits an “array”Not so good for multiple types of data16

Functional Languages:Multiple types of data Primitive types, lists, functions, Flexible user defined types Operations for combining values to build newvalues (combinators)Ability to name values and operations(abstraction)Scale to arbitrary size and shape data“Algebra of programming” supports reasoning17

Getting Started withHaskell18

Starting Hugs:user hugs --- Version: September 2006Hugs 98: Based on the Haskell 98 standardCopyright (c) 1994-2005World Wide Web: http://haskell.org/hugsBugs: http://hackage.haskell.org/trac/hugsHaskell 98 mode: Restart with command line option -98 to enable extensionsType :? for helpHugs The most important commands: :qquit :l fileload file :e fileedit file Exprevaluate expression19

The read-eval-print loop:1. Enter expression at the prompt2. Hit return3. The expression is read, checked, andevaluated4. Result is displayed5. Repeat at Step 120

Simple Expressions:Expressions can be constructed using:The usual arithmetic operations:1 2*3Comparisons:1 2'a' 'z'Boolean operators:True && Falsenot FalseBuilt-in primitives:odd 2sin 0.5Parentheses:odd (2 1)(1 2) * 3Etc 21

Expressions Have Types:The type of an expression tells you whatkind of value you will get when youevaluate that expression:In Haskell, read “::” as “has type”Examples: 1 :: Int, 'a' :: Char, True :: Bool, 1.2 :: Float, You can even ask Hugs for the type of anexpression: :t expr22

Type Errors:Hugs 'a' && TrueERROR - Type error*** Expression*** Term*** Type*** Does not matchin application: 'a' && True: 'a': Char: BoolHugs odd 1 2ERROR - Cannot infer instance*** Instance: Num Bool*** Expression : odd 1 2Hugs 23

Pairs:A pair packages two values into one(1, 2)('a', 'z')(True, False)Components can have different types(1, 'z')('a', False)(True, 2)The type of a pair whose first component isof type A and second component is of typeB is written (A,B)What are the types of the pairs above?24

Operating on Pairs:There are built-in functions forextracting the first and secondcomponent of a pair:fst (True, 2) Truesnd (0, 7) 725

Lists:Lists can be used to store zero or moreelements, in sequence, in a single value:[][1, 2, 3]['a', 'z'][True, True, False]All of the elements in a list must have thesame typeThe type of a list whose elements are oftype A is written as [A]What are the types of the lists above?26

Operating on Lists:There are built-in functions for extractingthe head and the tail components of a list: head [1,2,3,4] 1 tail [1,2,3,4] [2,3,4]Conversely, we can build a list from a givenhead and tail using the “cons” operator: 1 : [2, 3, 4] [1, 2, 3, 4]27

More Operations on Lists:Finding the length of a list:length [1,2,3,4,5] 5Finding the sum of a list:sum [1,2,3,4,5] 15Finding the product of a list:product [1,2,3,4,5] 120Applying a function to the elements of alist:map odd [1,2,3,4] [True, False, True, False]28

Continued Selecting an element (by position):[1,2,3,4,5] !! 3 4Taking an initial prefix (by number):take 3 [1,2,3,4,5] [1,2,3]Taking an initial prefix (by property):takeWhile odd [1,2,3,4,5] [1]Checking for an empty list:null [1,2,3,4,5] False29

More ways to Construct Lists:Concatenation:[1,2,3] [4,5] [1,2,3,4,5]Arithmetic sequences:[1.10] [1, 2, 3, 4, 5, 6, 7, 8, 9, 10][1,3.10] [1, 3, 5, 7, 9]Comprehensions:[ 2 * x x - [1,2,3,4,5] ] [2, 4, 6, 8, 10][ y y - [1,2,3,4], odd y ] [ 1, 3 ]30

Strings are Lists:A String is just a list of Characters['w', 'o', 'w', '!'] "wow!"['a'.'j'] "abcdefghij""hello, world" !! 7 'w'length "abcdef" 6"hello, " "world" "hello, world"take 3 "functional" "fun"31

Functions:The type of a function that mapsvalues of type A to values of type B iswritten A - BExamples: odd :: Int - Boolfst :: (a, b) - a(a,b are type variables)length :: [a] - Int32

Operations on Functions:Function Application. If f :: A - B and x ::A, then f x :: BNotice that function application associatesmore tightly than any infix operator:f x y (f x) yIn types, arrows associate to the right:A - B - C A - (B - C)Example: take :: Int - [a] - [a]take 2 [1,2,3,4] (take 2) [1,2,3,4]33

Sections:If is a binary op of type A - B - C,then we can use “sections”: ( ):: A - B - C(expr ) :: B - C (assuming expr::A)( expr) :: A - C (assuming expr::B)Examples: (1 ), (2*), (1/), ( 10), 34

Higher-order Functions:map :: (a - b) - [a] - [b] map (1 ) [1.5] [2,3,4,5,6]takeWhile :: (a - Bool) - [a] - [a] takeWhile ( 5) [1.10] [1,2,3,4](.) :: (a - b) - (c - a) - c - b (odd . (1 )) 2 True“composition”35

Definitions:So far, we’ve been focusing on expressionsthat we might want to evaluate.What if we wanted to: Define a new constant (i.e., Give a name to theresult of an expression)?Define a new function?Define a new type?Definitions are placed in files with a .hssuffix that can be loaded into the interpreter36

Simple Definitions:Put the following text in a file “defs.hs”:greet name "hello " namesquare x x * xfact n product [1.n]37

Loading Defined Values:Pass the filename as a command line argument toHugs, or use the :l command from inside Hugs:Main :l defsMain greet "everybody""hello everybody"Main square 12144Main fact 32263130836933693530167218012160000000Main 38

Using Libraries:Many useful functions are provided as partof the “Prelude”Many more are provided by libraries thatmust be imported before they can be usedExample:import CharnextChar c chr (1 ord c)(The Char library also provides functions forconverting to upper/lower case, testing foralphabetic or numeric chars, etc )39

Typeful Programming:Types are an inescapable feature ofprogramming in Haskell Programs, definitions, and expressions that donot type check are not valid Haskell programsCompilation of Haskell code depends oninformation that is obtained by type checkingHaskell provides several predefined types: Some built-in (functions, numeric types, )Some defined in the Prelude (Bool, lists, )What if you need a type that isn’t built-in?40

Type Synonyms:41

Type Synonym:A type synonym (or type abbreviation) givesa new name for an existing AngleRadiusPointSet a [Char] Float Float Length (Float, Float) a - Bool42

Algebraic Datatypes:43

In Haskell Notation:data Bool False Trueintroduces: A type, BoolA constructor function, False :: BoolA constructor function, True :: Booldata List a Nil Cons a (List a)introduces A type, List t, for each type tA constructor function, Nil :: List aA constructor function, Cons :: a - List a - List a44

More Enumerations:data Rainbow Red Orange Yellow Green Blue Indigo Violetintroduces: A type, Rainbow A constructor function, Red :: Rainbow A constructor function, Violet :: Rainbow45

More Recursive Types:data Shape Circle Radius Rect Length Length Transform Transform Shapedata Transform Translate Point Rotate Angle Compose Transform Transformintroduces: Two types, Shape and Transform Circle :: Radius - Shape Rect :: Length - Length - Shape Transform :: Transform - Shape - Shape 46

Using New Data Types:Building values of these new types iseasy:Nil:: List RainbowCons Red Nil:: List RainbowCons Blue (Cons Red Nil) :: List RainbowBut how do we inspect them or takethem apart?47

Pattern Matching:In addition to introducing a new type and acollection of constructor functions, each datadefinition also adds the ability to pattern matchover values of the new typeExample:firstfirst (x, y):: (a, b) - a xwavelengths:: Rainbow - (Length,Length)wavelengths Red (620*nm, 750*nm)wavelengths Orange (590*nm, 620*nm) nm 1e-9 :: Float48

More Examples:headhead []head (x:xs):: [a] - a error “head of []” xlengthlength []length (x:xs):: [a] - Int 0 1 length xsareaarea (Circle r)area (Rect w h)area (Transform t s):: Shape - Float pi * r * r w*h area s49

Pattern Matching & Substitution:The result of a pattern match is either: A failureA success, accompanied by a substitutionthat provides a value for each of thevalues in the patternExamples: [] does not match the pattern (x:xs)[1,2,3] matches the pattern (x:xs) withx 1 and xs [2,3]50

Patterns:More formally, a pattern is either:An identifier Matches any value, binds result to the identifierAn underscore (a “wildcard”) Matches any value, discards the resultA constructed pattern of the form C p1 pn,where C is a constructor of arity n and p1, ,pnare patterns of the appropriate type Matches any value of the form C e1 en, provided thateach of the ei values matches the corresponding pipattern.51

Other Pattern Forms:For completeness:“Sugared” constructor patterns: Tuple patterns (p1,p2)Cons patterns (ph : pt)List patterns [p1, p2, p3]Strings, for example: "hi" (‘h’ : ‘i’ : [])Character and numeric Literals: Can be considered as constructor patterns, but theimplementation uses equality ( ) to test for matches52

Function Definitions:In general, a function definition is written asa list of adjacent equations of the form:f p1 pn rhswhere: f is the name of the function that is being definedp1, , pn are patterns, and rhs is an expressionAll equations in the definition of f must havethe same number of arguments (the “arity”of f)53

continued:Given a function definition with mequations:f p1,1 pn,1 rhs1f p1,2 pn,2 rhs2 f p1,m pn,m rhsmThe value of f e1 en is S rhsi, where i isthe smallest integer such that theexpressions ej match the patterns pj,i and S54is the corresponding substitution.

Example: filterfilter:: (a - Bool) - [a] - [a]filter p [] []filter p (x:xs) px x : rest otherwise restwhere rest filter p xsguards“where” clause55

Example: Binary Search Treesdata Tree Leaf Fork Tree Int Treeinsertinsert n Leafinsert n (Fork l m r) n m otherwise:: Int - Tree - Tree Fork Leaf n Leaf Fork (insert n l) m r Fork l m (insert n r)lookup:: Int - Tree - Boollookup n Leaf Falselookup n (Fork l m r) n m lookup n l n m lookup n r otherwise True56

Summary:An appealing, high-level approach toprogram construction in whichindependent aspects of programbehavior are neatly separatedIt is possible to program in a similarcompositional / calculational manner inother languages but it seems particularly natural in afunctional language like Haskell 57

Assignment #1Your goal is to write a function: toInt :: String - IntTo accomplish this, consider the following functions: explode :: String - [Char]digitValue :: [Char] - [Int]reverse :: [Int] - [Int]pairedWithPowersOf10 :: [Int] - [(Int,Int)]pairwiseProduct :: [(Int,Int)] - [Int]sum :: [Int] - IntWrite definitions for four of these functions (reverse and sum are builtin), using pattern matching and recursion where necessaryTurn in an elegant program that communicates your solution well,including appropriate tests for each part.58

What is Functional Programming? Functional programming is a style of programming that emphasizes the evaluation of expressions, rather than execution of commands Expressions are formed by using functions to combine basic values A functional language is a language that supports and encourages programming in a functional style

Related Documents:

work/products (Beading, Candles, Carving, Food Products, Soap, Weaving, etc.) ⃝I understand that if my work contains Indigenous visual representation that it is a reflection of the Indigenous culture of my native region. ⃝To the best of my knowledge, my work/products fall within Craft Council standards and expectations with respect to

Object Oriented Programming 7 Purpose of the CoursePurpose of the Course To introduce several programming paradigms including Object-Oriented Programming, Generic Programming, Design Patterns To show how to use these programming schemes with the C programming language to build “good” programs.

Functional programming paradigm History Features and concepts Examples: Lisp ML 3 UMBC Functional Programming The Functional Programming Paradigm is one of the major programming paradigms. FP is a type of declarative programming paradigm Also known as applicative programming and value-oriented

1 1 Programming Paradigms ØImperative Programming – Fortran, C, Pascal ØFunctional Programming – Lisp ØObject Oriented Programming – Simula, C , Smalltalk ØLogic Programming - Prolog 2 Parallel Programming A misconception occurs that parallel

About this Programming Manual The PT Programming Manual is designed to serve as a reference to programming the Panasonic Hybrid IP-PBX using a Panasonic proprietary telephone (PT) with display. The PT Programming Manual is divided into the following sections: Section 1, Overview Provides an overview of programming the PBX. Section 2, PT Programming

Programming paradigms Structured programming: all programs are seen as composed of control structures Object-oriented programming (OOP): Java, C , C#, Python Functional programming: Clojure, Haskell Logic programming based on formal logic: Prolog, Answer set programming (ASP), Datalog

Programming is the key word here because you make the computer do what you want by programming it. Programming is like putting the soul inside a body. This book intends to teach you the basics of programming using GNU Smalltalk programming language. GNU Smalltalk is an implementation of the Smalltalk-80 programming language and

It stands for Object Oriented Programming. Object‐Oriented Programming ﴾223﴿ uses a different set of programming languages than old procedural programming languages ﴾& 3DVFDO, etc.﴿. Everything in 223 is grouped as self sustainable "REMHFWV". Hence, you gain reusability by means of four main object‐oriented programming concepts.