Haskell Lecture 1

Haskell_lecture_1.adoc

Haskell

Functions

Is a mapping that takes one or more arguments and produces a single result.

• Is defined using an equation with a name for the function

• Each argument has a name

• The body specifies how would be calculated in terms of the arguments

Ex.

double x = x + x

• The result is obtained by sustituiting these args into the body, in place of the arguments names

• The result will be an expression containing other function application

• which must then be processed in the same way

double 3
= { applying double }
  3 + 3
= { applying + }
  6

double (double 2)
= { applying the inner double }
  double ( 2 + 2 )
= { applying + }
  double 4
= { applying double }
  4 + 4
= { applying + }
  8

Functional programming

• Style of programming

• The basic method of computation is the application of functions to arguments

Functional programming language

Is one that supports and encourages the functional style

Imperative style(for demo purposes)

count := 0
total := 0
repeat
  count := count + 1
  total := total + count
until
  count = n

Functional style(with Haskell)

sum[1..n], where [..] is a function, sum is a function

sum[1..5]
= { applying [..] }
  sum[1,2,3,4,5]
= { applying sum }
  1+2+3+4+5
= 15

Notes: - Most imperatives languages support some form of functions, for that reason, the last implementation could be translated. - However, most of those languages don’t encourage the functional style.

Features of Haskell

• Concise programs

• Powerful type system

• List comprenhension

• Recursive functions

• Higher-order functions(DSL)

• Monadic effects

• Lazy evaluation

• Reasoning about programs(induction)

Historical background

• 1930 Alonzo Church developed the lambda calculus(theory of functions).

• 1950 John McCarthy developed LISP(LISt Processor)

• 1960 Peter Landin developed ISWIM(If you See What I Mean), the first purely functional language

• 1970 John Backus developed FP(Functional Programming)

• 1970 Robin Milner developed ML(Meta-Language), polymorphic types and type inference

• 1970-1980 David Turner developed Miranda, lazy FPL

• 1987 an intnl committee starts the development of Haskell, a standard lazy functional programming language

• 2003, such committee published th Haskell Report, which defines a stable version, 50 years of work culminated

Taste of Haskell

sum[] = 0
sum(x:xs) = x + sum xs

sum[1,2,3]
= { applying sum }
1 + sum[2,3]
= { applying sum }
1 + (2 + sum[3])
= { applying sum }
1 + (2 + (3 + sum[]))
= { applying sum }
1 + 2 + 3 + 0
= { applying + }
6

Note: In Haskell, every function has a type that specifies the nature of its arguments and results, which is inferred from the definition.

Num a ⇒ [a] → a

Ex.:

qsort [] = []
qsort(x:xs) = qsort smaller ++ [x] ++ qsort larger
              where
                smaller = [ a | a <- xs, a <= x]
                larger = [ b | b <- xs, b > x]

qsort :: Ord a => [a] -> [a]

First steps

Hugs is the default environment for Haskell Hugs load Prelude.hs Glasgow Haskell Compiler, ghci

Basic operations

2+3
2-3
2*3
7 / 2
7 `div` 2
2^3

Lists

head[1,2,3,4]
tail[1,2,3,4]
[1,2,3,4,5,6]!!2
take 3 [1,2,3,4,5,6,7]
drop 3 [1,2,3,4,5,6,7]
length [1,2,3,4,5,6,7]
sum[1,2,3,4,5,6,7]
product[1,2,3,4,5,6,7]
[1,2,3] ++ [4,5]
reverse [1,2,3,4,5,6,7]

1 `div` 0
head []

## Function application

Math: ƒ(a,b) + c d

Haskell: f a b + c * d

In math the multiplication is denoted silently by writing two values next to one another. Function application in Haskell is denoted silently using spacing, and has higher order priority.

f(x) => f x
f(x,y) => f x y
f(g(x)) => f(g x)
f(x,g(y)) => f x (g y)
f(x)g(y) => f x * g y

Haskell scripts

double x = x + x
quadruple x = double(double x)

factorial n = product[1..n]
average ns = sum ns `div` length ns

Calling scripts

:load script.hs
:reload
:edit name
:edit
:type
:?

Naming

myFun fun1 arg_2 x'

The names of th function and its arguments must begin with a lower-case, but can then be follewd by zero or moere letters(uppercase included), digits, underscores and single quotes.

Keywords

case class data default deriving do else if import in infix infixl infixr instance let module newtype of then type where

Note: By convention, list arguments have the suffix 's' on their name to indicate multiple values.

Layout Rule

In a script, each fefinition must begin in precisely the same column. This layout rule makes it posiible to determine the grouping of definitions from their indentation.

Implicit

a = b + c
  where
    b = 1
    c = 2
d = a * 2

Explicit

a = b + c
  where
    {b = 1;
    c = 2}
d = a * 2

Comments

Ordinary

-- This is a comment
-- This comment is single line
Nested
{-
This is a comment
Could be multiline
-}

Exercise: Make the correction of:

N = a `div` length xs
  where
    a = 10
    xs = [1,2,3,4,5]