Functional Programming - 11. Haskell Intro

Functional Programming

11. Haskell Intro

11.1 The Haskell functional programming language

Haskell is a pure functional, statically strongly-typed, non-strict evaluation language.
Pure functional - no unrestricted mutation
Non-strict - values lazy computed, i.e. only if and when needed
Statically typed - types are checked at compile time
Strongly typed - things can be combined only if they are exactly compatible.

But there is more:
Type-checked at compile time
Polymorphic, parameterized by types
Type hierarchy (class and subclass) and multiple inheritance
Sophisticated type inference engine
Function Currying and partial application is for free.

11.2 Haskell References

For a gentle and amusing introduction to Haskell visit http://learnyouahaskell.com/starting-out.

The book Real World Haskell is here http://book.realworldhaskell.org

And a very good wiki-book is here http://en.wikibooks.org/wiki/Haskell

A tour of the basic syntax can be found at https://www.fpcomplete.com/blog/2012/09/ten-things-you-should-know-about-haskell-syntax

A tour of the basic operations provided in prelude: http://cs.fit.edu/~ryan/cse4250/tourofprelude.html

And an excellent Haskell cheatsheat http://cheatsheet.codeslower.com/

11.3 Obtaining the Haskell environment

You will need a Haskell environment. Get started by obtaining the Glasgow Haskell Compiler, ghc from http://www.haskell.org/ghc/ for your favorite platform. The recommended way to start is with the Haskell platform, http://hackage.haskell.org/platform/

When you install, there will be documentation (put somehere like /usr/share/doc/ghc), /usr/share/doc/ghc/html/users_guide/index.html

You want to start by looking at how to run it interactively by reading this section: /usr/share/doc/ghc/html/users_guide/interactive-evaluation.html The online version is at http://haskell.org/haskellwiki/GHC

11.4 Preliminaries

Name spaces:

variables named with lower case first. _ is lower (but not _ by itself), the ' quote character after the initial character is valud in a name. So x' is a proper variable name.
types and everything else are named with upper case first.

Run interactively with ghci. Try these basic scalar operations
3 + 4
it * 2

Operators can be in infix (above) or prefix form:
(+) 4 5

Everthing in Haskell is typed. To get the type of something, use :t as in
:t (+)

Haskell uses an equational style of definition, with progressively more general pattern matches.
let g n = n + n
let { g 0 = 42 ; g n = n + n } pattern match
let { g n = n + n; g 0 = 42 } first pattern overlaps second, not so good.
let { fib 0 = 1 ; fib 1 = 1; fib n = fib(n-1) + fib(n-2) }

To see the type of g:
:t g
To see the bindings of all the variables currently in scope:
:show bindings

Basic list operations - lists are homogeneous, that is all items must have the same type.
[ 1, 2, 4 ]
[ 3 .. 10000000 ] texas range
[1, 2 ] ++ [3, 4] concatenation

Other operations like: head, tail, etc...

List comprehension
[ x | x <- [1 .. 20] ]
[ x | x <- [1 .. 20], mod x 2 == 1 ]

Tuples are heterogeneous and can have difference types in each position
[ (x, y, z) | x <- [1 .. 5], y <- [1, 7], z <- [1, 3] ]

11.5 Operators

Define an operator, derive its type

Let us define the operator m. The :{ and :} brackets are just for when you are typing input directly into the interpreter. (See 2.4. Interactive evaluation at the prompt in http://www.haskell.org/ghc/docs/latest/html/users_guide/interactive-evaluation.html. The { amd } brackets, along with ; are the "traditional" delimiter way of defining cases that is insensitive to white space. You normally use white space to indicate nesting, as for Python.

code/Haskell/Intro/op.hs

-- Define the m function, where op is in prefix position

:{

let { m op n [ ] = n

; m op n (h:hs) = (op h (m op n hs))

}

:}

{- this is a long comment

that covers three lines

Of course, why not have yet another comment convention! -}

-- The same form but in infix form

:{

let { m op n [ ] = n

; m op n (h:hs) = h `op` m op n hs

}

:}

-- The same again, but using whitespace nesting and cases

:{

let

m op n [ ] = n

m op n (h:hs) = (op h (m op n hs))

:}

The first name being mentioned is m, the operator being defined. How did Haskell figure out the type of m? Let's look step by step.

Prelude> let m op n [ ] = n
Prelude> :t m
m :: t -> t1 -> [t2] -> t1

Haskell gives op the type t, and n the type t1, and the elements of [ ] type t2. The only thing it knows is that it returns n so its return type must be t1.

Adding the additional equation

m op n (h:hs) = (op h (m op n hs))

gives additional type information.

Prelude> :t m
m :: (t1 -> t -> t) -> t -> [t1] -> t

It gives n the type t, and so knows the return type of m is t. It gives elements of [ ] the type t1, and then knows that the type of h must be t1. But h appears as the first argument of op, and the result type of m is the second argument of op, and the entire right hand side is of type t, so op must have type t1 -> t -> t

Now try m (*) 1 [1..3]

Lists

Lists are similar to racket, the : is cons.
code/Haskell/Intro/lists.hs

let flip (x:y:z) = y : x : z

flip [1, 2, 3, 4]

flip [1, 2]

flip [1]

flip [2]

flip "Hello"

:{

let { flip [] = []

; flip (x:[]) = [x]

; flip (x:y:z) = y:x:z

}

:}

-- let shuffle (h1:hs1) (h2:hs2) = h1 : h2 : (shuffle hs1 hs2)

let shuffle (h1:hs1) h2 = h1 : (shuffle h2 hs1)

let ones = 1 : ones

take 10 (shuffle ones [2..])

-- the safer version of shuffle

:{

let { shuffle [ ] h = h

; shuffle h [ ] = h

; shuffle (h1:hs1) h2 = h1 : (shuffle h2 hs1)

}

:}

11.6 More ...

Load this by doing ghci HaskellIntro-2.hs, then in interactive mode you can try :help, :reload, :load, etc.

code/Haskell/Intro/HaskellIntro-2.hs

-- lequal :: a => [a] -> [a] -> Boolean

lequal [] [] = True

lequal (x:xs) [] = False

lequal [] (y:ys) = False

lequal (x:xs) (y:ys) = (x == y) && (lequal xs ys)

-- examples of using wildcard _

lhead (x:_) = x

ltail (_:xs) = xs

llast [x] = x

llast (_:xs) = llast xs

linit [x] = []

linit (x:xs) = x : linit xs

lnull [] = True

lnull (_:_) = False

-- remove duplicates

nub [] = []

nub (x:xs) = x : nub (remove x xs)

where

remove y [] = []

remove y (z:zs) | y == z = remove y zs

| otherwise = z : remove y zs

-- lambda abstraction

-- map (\x -> x + x) [1, 2, 3]

-- map and filter

lmap f [] = []

lmap f (x:xs) = (f x) : lmap f xs

lfilter p [] = []

lfilter p (x:xs) | p x = x : filter p xs

| otherwise = filter p xs

-- shuffle two lists

shuffle [] y = y

shuffle x [] = x

shuffle (x:xs) y = x : (shuffle y xs)

-- infinite list of ones

ones = 1 : ones

-- induction over naturals

-- f(0) = c

-- f(n+1) = h(f(n))

-- natural recursive definition

foldn h c 0 = c

foldn h c n = h (foldn h c (n-1))

-- :t foldn (\x -> 1 + x) 2

-- induction and recursion over lists

lfoldr f z [] = z

lfoldr f z (x:xs) = (f x (lfoldr f z xs))

lfoldl f z [] = z

lfoldl f z (x:xs) = (lfoldl f (f z x) xs)

-- reverse a list efficiently

-- note: in (f z x) of foldl, z is the reversed list being constructed

-- in rev, the function f tacks a new element onto the list being constructed

rev = foldl (\ ys y -> y:ys) []

-- data types are defined by constructor patterns

-- Eq equality can be derived from structural equality

data BinTree = L | N BinTree BinTree deriving (Eq, Show)

makeBinTree 0 = L

makeBinTree n = N (makeBinTree (n-1)) (makeBinTree (n-1))

size L = 1

size (N t1 t2) = 1 + size t1 + size t2

-- exercise: given n construct a binary tree of size n

-- exercise: trees over strings

Try this:
:t T
:t N
let x = makeBinTree 5
size x
Note how N is a function that builds a BinTree from two BinTrees.

11.7 Terminology and Notions

Haskell uses a calculation or reduction model of computation. The things we calculate on are called expressions. The things that result from a calculation are called values. Expressions are values. Every value and expression has a type. All programs must be well-typed before being run. The opposite of well-types is ill-typed.

An atomic value is indivisible. No further calculation on it is possible, or put another way, all calculations on atomic values reaturn the original value.

A structured value is composed of other values, say by putting them into a list, a tuple, or part of a new type.

The = symbol is NOT the operational assignment of a procedural language. It should be thought of as a name-binding equation that assigns a name to an expression. For example, you can read x = 1 as x is assigned to 1, or bound to 1.

In Haskell you declare the type of something using the has-type operator ::, and then define its value. For example this declares x to be an Integer (arbitrary precision) and binds it to 1 + y.

x :: Integer x = 1 + y

It is possible to have a definition like:

x :: Integer x = 1 + x

which has non-terminating reductions. When the value is non-termination we express this with the bottom symbol ⏊.

11. Haskell Intro
Notes on Functional Programming / Version 2.10 2014-02-24