cs571-08-record
1
CS571: Programming Languages
2Cs571 Programming Languages
Haskell
3Cs571 Programming Languages
Functional Programming
Functional programming emphasizes the application of
functions, in contrast to imperative programming,
which emphasizes changes in state and the execution
of sequential commands.
A functional language is a language that supports and
encourages programming in a functional style.
4Cs571 Programming Languages
Encoding “factor” Using Haskell
fact x =
if x == 0 then 1 else x * fact(x-1);
5Cs571 Programming Languages
Why Functional Programming
Shorter, clearer, and more maintainable code.
Easier to understand
6
Haskell in Industry
AT & T: used in the Network Security division to
automate processing of internet abuse complaints.
Bank of America: used for backend data
transformation and loading.
Alcatel-Lucent: prototype narrowband software radio
systems.
Allston Trading: used Haskell for some of their
trading infrastructures.
……
Cs571 Programming Languages
7Cs571 Programming Languages
Haskell
Online tutorial
http://haskell.org/tutorial/
google “haskell tutorial”
Software:
✶ Hugs: a functional programming system based on
Haskell.
✶ Type hugs in remote.cs.binghamton.edu
✶ Download hugs from
✶ https://www.haskell.org/hugs/pages/downloading.htm
✶ To exit hugs, type :q
8Cs571 Programming Languages
Software: Hugs
bingsun2% hugs
__ __ __ __ ____ ___
_________________________________________
|| || || || || || ||__ Hugs 98: Based on the Haskell 98 standard
||__|| ||__|| ||__|| __|| Copyright (c) 1994-2005
||—|| ___ || World Wide Web: http://haskell.org/hugs
|| || Report bugs to: hugs-
|| || Version: March 2005
_________________________________________
Haskell 98 mode: Restart with command line option -98 to enable
extensions
Type 😕 for help
Hugs.Base>
9Cs571 Programming Languages
Hugs
:load
:edit
:type
:cd dir change directory
:gc force garbage collection
:version print Hugs version
:quit exit Hugs
10Cs571 Programming Languages
Type System
Type checking happens at compile time.
Every value has a type
Values can be passed as arguments to functions
Functions are values
11Cs571 Programming Languages
Case Sensitivity
Haskell is case-sensitive
✶ Function names and constants start with a lower
case letter
✶ Specific types start with a capital letter.
12Cs571 Programming Languages
Basic Types and definitions: Bool
The Booleans: Bool
✶ Values: True, False
✶ Operators
&& and
|| or
not not
Simple computation can be executed interactively
Hugs> True && False
False
Hugs> True || False
True
Hugs> not True
False
13Cs571 Programming Languages
Basic Types and definitions: Int
The integers: Int
✶ Values: e.g. 0, 45, -5, 273873
✶ Operators: +, -, *, ^ (raise to the power), div (whole
number division), mod (the remainder from whole
number division), abs (absolute value), negate
(change the sign).
✶ The greatest value in Int is 2147483647.
✶ For larger number, we need use Integer.
14Cs571 Programming Languages
Basic Types and definitions: Int
Hugs> 2*3
6
Hugs> div 13 5
2
Hugs> mod 13 5
3
Hugs> 2^3
8
Hugs> abs (-2.3)
2.3
Hugs> negate (-2.3)
2.3
15Cs571 Programming Languages
Infix and Prefix
“div” and “mod” need backquotes (`) when used as
“infix” operators
✶ 12 `mod` 5 is the same as mod 12 5
Infix operators can be written before their
arguments, by enclosing the operator in
parenthesis.
(+) 2 3 = 2 + 3
Hugs> (+) 2 3
5
16Cs571 Programming Languages
Basic Types and Definitions: Relational Operators
Relational operators: take two integers as input
and return a Bool (True or False)
>, >=, ==, /=, <=, <
Hugs> 3 >= 2
True
Hugs> 3 /= 2
True
Hugs> 3 <= 2
False
17Cs571 Programming Languages
Basic Types and Definitions: Char, String
The characters: Char
‘a’, ‘3’, ‘\t’ (tab), ‘\n’ (new line), ‘\\’ (backslash)
‘\’ ’ (single quote ’ ), ‘\” ‘ (double quote ” )
String is a list of Chars.
✶ type String = [Char]
✶ “abc” is shorthand for [‘a’,’b’,’c’]
18Cs571 Programming Languages
Basic Types and Definitions: Float
Floating-point numbers: Float
✶ Value: 0.132, -23.3
✶ Operators: e.g., +, -, *, / (fractional division), ^,
abs, ceiling/floor (convert a fraction to an
integer), pi (the constant), sqrt (positive square
root).
✶ Haskell also allows literal floating-point numbers in
scientific notation.
231.61e7 231.61 * 10^7 = 2,316,100,000
231.6e-2 231.61 * 10^(-2) = 2.3161
19Cs571 Programming Languages
Basic Types and Definitions: Float
Hugs > 3/2
1.5
Hugs > ceiling 1.23
2
Hugs > floor 1.23
1
Hugs > pi
3.14159265358979
Hugs > sqrt 4
2.0
20Cs571 Programming Languages
Script
Script: filename.hs
✶ ‘- -’ specifies the beginning of a comment. Comments
can also be enclosed by symbols ‘{-’ and `-}’ (multiple
lines).
square.hs:
—- The function to square an integer
square :: Int -> Int
square n = n*n
To load square.hs, type :1oad square.hs or :l square.hs
To edit square.hs, type :e square.hs. Use ctrl-X to exit.
Has type
21Cs571 Programming Languages
Type
Haskell can infer the type
square n = n*n
> :t square
> square :: Num a => a ! a
Num (numeric type): integers and floating points
22Cs571 Programming Languages
Functions
Functional programming: writing a program as a
set of functions.
cube x = x * (square x)
square x = x * x
> sqare 5
25
> cube 5
125
23Cs571 Programming Languages
Example: inc
Increase an integer n by 1
inc :: Integer -> Integer
inc n = n+1
Main> inc (inc 3)
f(g(a))
24Cs571 Programming Languages
Example: inc
Increase an integer n by 1
inc :: Integer -> Integer
inc n = n+1
Main> inc (inc 3)
5
f(g(a))
25Cs571 Programming Languages
Currying a Function
Functions of two or more arguments
✶ Uncurried form
addUC :: (Int, Int) ! Int
addUC (x,y) = x+y
Hugs> :load adduc.hs
Main> addUC(1,2)
3
26Cs571 Programming Languages
Currying a Function
Functions of two or more arguments
✶ Curried form — the name curry derives from the person
who popularized the idea: Haskell Curry
❖ Take a single argument at a time
add :: Int -> Int -> Int
!is right associative, a ! b ! c means a ! (b ! c)
add x y = x+y
add x y is equivalent to (add x) y – applying add to
yields a new function which is then applied to the
second argument y
We can define inc using add:
27Cs571 Programming Languages
Currying a Function
Functions of two or more arguments
✶ Curried form — the name curry derives from the person
who popularized the idea: Haskell Curry
❖ Take a single argument at a time
add :: Int -> Int -> Int
!is right associative, a ! b ! c means a ! (b ! c)
add x y = x+y
add x y is equivalent to (add x) y – applying add to
yields a new function which is then applied to the
second argument y
We can define inc using add:
inc = add 1
28Cs571 Programming Languages
Example (f.hs)
Given the following haskell program
f x y = x + 2*y
What is the result of f (f 1 2) (f 3 4)?
What is the result of f (f 1 2) f 3 4?
29Cs571 Programming Languages
Example (f.hs)
Given the following haskell program
f x y = x + 2*y
What is the result of f (f 1 2) (f 3 4)?
27
What is the result of f (f 1 2) f 3 4?
30Cs571 Programming Languages
Example (f.hs)
Given the following haskell program
f x y = x + 2*y
What is the result of f (f 1 2) (f 3 4)?
27
What is the result of f (f 1 2) f 3 4?
ERROR – Cannot infer instance
*** Instance : Num (a -> a -> a)
*** Expression : f (f 1 2) f 3 4
Reason: f (f 1 2) f 3 4 = (f (f 1 2) f) 3 4
31CS571 Programming Languages
Excercise
sumsquares(n,m) = n2 + m2
32CS571 Programming Languages
Example
sumsquares(n,m) = n2 + m2
sq x = x*x
sumsquares n m = sq n + sq m
33Cs571 Programming Languages
Example
Write a haskell fuction isEven n that checks if n
is an even number.
34Cs571 Programming Languages
Example
Write a haskell fuction isEven n that checks if n
is an even number.
isEven :: Int ! Bool
isEven n = (n `mod` 2 ==0)
35Cs571 Programming Languages
Conditional Expressions
We can write conditional expressions by means of
the if…then…else constructor of Haskell.
max:: Int ! Int ! Int
max x y
= if x >= y then x else y
36
Guards/Conditions
Used to give alternatives in the definitions of
functions.
A guard is a Boolean expression and these
expressions are used to express various cases in
the definition of a function.
f
| condition1 = statement1
| condition2 = statement2
……
| otherwise = statement
37Cs571 Programming Languages
Guards/Conditions
Used to give alternatives in the definitions of
functions.
A guard is a Boolean expression and these
expressions are used to express various cases in
the definition of a function.
max:: Int ! Int ! Int
max x y
| x >= y = x
| otherwise = y
38Cs571 Programming Languages
Example: maxThree
Given three inputs, compute the maximum
number.
39Cs571 Programming Languages
Example: maxThree
Given three inputs, compute the maximum
number.
maxThree:: Int ! Int ! Int ! Int
maxThree x y z
| x >= y && x >= z = x
| y >= z = y
| otherwise = z
40Cs571 Programming Languages
Examples
Write a haskell function threeEqual that checks
if three Integers are equal.
threeEqual :: Int ! Int ! Int ! Bool
threeEqual x y z
| x == y && x == z = True
| otherwise = False
Or
threeEqual x y z = (x==y) && (y==z)
41Cs571 Programming Languages
Examples
Write a haskell function addall such that
addall(n) = 1 + 2 + … + n (assume that n >= 1). Use
recursion.
42Cs571 Programming Languages
Examples
Write a haskell function addall such that
addall(n) = 1 + 2 + … + n (assume that n >= 1)
if n = 1 ➔ addall(n) = 1
if n > 1 ➔ addall(n) = n + addall(n-1)
addall n
| n == 1 = 1
| otherwise = n + addall (n-1)