Haskell is a functional programming language.
Why do you need to know about it? Because you should.
The utilities you should have once Haskell is setup on your PC.
ghc, ghci and cabal
Load a script with functions with :l <fileName>
Pure functions, Immutable Data
So no side effects
Declarative
Easier to verify correctness
Definition of complex enough algorithms can be done elegantly in Haskell.
Note that I have learnt that examples help in understanding a lot more than definitions by themselves. So including a tonne of them.
Function Definition
name arg1 arg2 arg3 = < exp >
There is no return statement. The last statement evaluated is returned
Types
var :: Type
e.g. x :: Integer
func :: Type
e.g. inRange :: Integer -> Integer -> Integer -> Bool
Let
Imperative isn’t allowed, i.e. you can’t return a value.
So instead, we use let
func params =
let params = < exp >
in params
That is, we define a name, and bind it to an expression, i.e. some name and expression, another name and it’s expression…and finally in
and all “bind-ed” expression containing all names
Things are evaluated only when needed, Lazy Haskell
Where
func params = paramsToBeReturned --technically not "returned"
where
params = < exp >
if-then-else
if < exp > then < exp > else < exp >
Infix Functions
:t (+) --for checking type of any function
> (+) :: Num a=>a->a->a
Any function can be written in Infix style by ` ` around them
Recursion
No loops in Haskell. So we need recursion
fac n =
if n <= 1 then
1
else
n * fac (n-1)
Guards
otherwise
always evaluates to True
Guards can replace if-then-else, as that guard is executed, and returned as THE expression of the function which evaluates to True
fac n
| n <= 1 = 1
| otherwise = n*fac(n-1)
| < exp to be evaluated for True or False > = < exp returned >
_
is a wild card
Pattern Matching
Multiple definitions of the same functions can occur in Haskell, each with different set of inputs
ghci> is_zero 0 = True
...
ghci> is_zero _ = False
This means that for 0, is_zero will return True, and for a wild card “Excluding the already defined input set”, the function returns False
Accumulators
fac n = aux n 1 --aux is an auxiliary function, which takes an accumulator
where
aux n acc --definition of aux
| n <= 1 = acc
| otherwise = aux (n - 1) (n * acc)
In short, accumulators are applying Tail Recursion.
This is much more efficient than usual recursion, cause it takes a lot less memory and same complexity.
The main thing to remember about tail recursion is that the recursive step is always the last step at a particular depth.
Another example on Fibonacci
fib n = go n (a, b)
where
go 0 (a, b) = a
go 1 (a, b) = b
go n (a, b) = go (n-1) (b, a + b)
Lists
Lists only have one internal type. They can be constructed via constructors []
(empty) and :
(pre-pend)
example:
asc :: Int -> Int -> [Int]
asc n m --list from n to m
| m < n = []
| m == n = [m]
| m > n = n : asc (n+1) m
Many functions of Lists are predefined, quite a lot of them in Data.List
module.
For Polymorphic Lists
elem :: a -> [a] -> Bool --returns if given element belongs to the list
head :: [a] -> a --returns the first element of the list
tail :: [a] -> a --returns all of list except the head
length :: [a] -> Int --returns length of list
init :: [a] -> [a] --returns a last-element-removed list
last :: [a] -> a --returns the last element of list
null :: [a] -> Bool --check if a list is empty
Every data structure in Haskell is immutable, so we always get a copy with modifications to current structure, which we may reassign to the same variable name, that effectively changes the data structure.
For Boolean Lists
and :: [Bool] -> Bool --and operation over all elements of list
or :: [Bool] -> Bool --or operation over all elements of list
When can such a thing be useful, a list of booleans?
The case of List Comprehensions.
List Comprehension
[<gen> | <elem> <- <list>, ... , <guard>, ... ]
Patterns in Lists
Pattern matching with Lists is quite useful. It is used mostly in recursion tbh
sum [] = 0
sum (x:xs) = x + sum xs
-- is equivalent to
sum xs = foldr (+) 0 xs
-- another example
evens :: [Int] -> [Int]
evens [] = []
evens (x:xs) --colon constructor
| mod x 2 == 0 = x : evens xs
| otherwise = evens xs
Tuples
Tuples can have any number of elements, but a fixed number
fst :: (a,b) -> a
fst (x,_) = x
snd :: (a,b) -> b
snd (_,y) = y
Tuple “unpacking”
let (x, y) = (1, 2) in x
Higher Order Functions
app :: (a -> b) -> a -> b
app f x = f x
add1 :: Int -> Int
add1 x = x + 1
app add1 1
Anonymous Functions
(\<args> -> <expr>)
example (\x -> x+1)
Functions are just values in Haskell, just like Js, can be assigned to variables
increment = (\x -> x+1)
addAll = (\x y z -> x+y+z)
app f x = f x
incrementOne = app (\x -> x + 1) 1
Some common Higher order functions
-- Map is useful to map each element of a list to another list via a function
map :: (a->b) -> [a] -> [b]
map (\(x,y) -> x+y) [(1,2),(2,3),(4,6)]
-- Filter is used to filter out a list on the basis of a provided function
-- this is a predicate function
-- the predicate when returns True, then the element will be in the new list
filter :: (a->Bool) -> [a] -> [a]
filter (\x -> x>2) [1,2,3,4,5,6]
filter (\(x,y) -> x/=y) [(1,2),(2,2)]
Currying
Essentially, functions having multiple arguments don’t exist.
f :: a -> b -> c -> d
is equivalent to f :: a -> (b -> (c -> d))
So, example:
add :: Int -> Int -> Int
add x y = x + y
-- or equivalent to
add x = (\y -> x+y)
-- or equivalent to
add = (\x -> (\y -> x + y))
-- so clearly, anonymous functions are fundamental, while any function itself is just a variable which has an anonymous function assigned to it.
add 1 -- returns a function
add 1 :: Int -> Int
The last statement is generating a new function from an old function. This is called the partial function application.
This is done everywhere in Haskell. Example, you might use a map or filter (higher order functions), but have to rewrite it’s filtering function every time. Partial function application is a way out.
doubleList = map (\x -> 2*x)
-- now we don't need any function argument to do this operation. Just pass a list, and doubleList will double it element wise ofc
Function Composition
Haskell is great for implementing mathematical functions, and its exactly that.
(.) :: (b -> c) -> (a -> b) -> a -> c
f :: a -> b
g :: a -> b
composite f g = f.g
composite f g = (\x -> f (g x))
Application? If you have a sorting function sort
and reverting function reverse
, define
descSort = reverse.sort
descSort = (\x -> reverse (sort x))
descSort x = reverse (sort x)
-- All are equivalent
Another example, mapping of mappings
map2D :: (a->b) -> [[a]] -> [[b]]
map2D = map.map
$ function
Used to write cleaner code while using composition or higher order functions
($) :: (a -> b) -> (a -> b)
f $ x = f x
-- or
($) f x = f x
-- or
($) = id
Applications:
f xs = map (\x -> x+1) (filter (\x -> x>1) xs)
-- or
f xs = map (\x -> x+1) $ filter (\x -> x>1) xs
Folding
One of the most important concept in Lists. Folding up a list’s element into a value, on the basis of a binary function and an initiator (accumulator)
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr (\elem acc -> <term>) <start_acc> <list>
foldr (%) a [x1, x2, x3, x4] = x1 % x2 % x3 % x4 % a
-- a is accumulator, % is a binary function
Applications:
-- some partial functions
sum = foldr (+) 0
and = foldr (&&) True
or = foldr (||) False
length = foldr (\x -> (+) 1) 0
length' = foldr (const $ (+) 1) 0 -- as x isn't used, replace it by const
map f = foldr ((:) . f) []
count x = foldr (\y acc -> if x==y then acc+1 else acc) 0 -- a partial function that counts how many times an element occurs in a list
isAll e = foldr (\x acc -> e==x && acc) True -- note that this isn't efficient, but that's not the point
isAll' e = foldr (\x -> (&&) $ e == x) True
Now, folding has direction. We have seen foldr
, and there exists a foldl
foldr (\elem acc -> <term>) <start_acc> <list> --from last element of list with the acc, we build upto the first
foldl (\acc elem -> <term>) <start_acc> <list> --from the first element with the acc, we build upto the last
Tree folding
In a Lazy based language, the order of folding of trees actually shouldn’t matter.
But while printing, we need to take order into account.
Data Types
data Name =
Constructor1 <args> | Constructor2 <args> | ..
-- args shouldn't contain literals, but the type itself
data Color =
Red | Green | Blue
data PeaNum =
Succ PeaNum | Zero
data Calculation =
Add Int Int | Mul Int Int | Sub Int Int | Div Int Int
data Tree a =
Leaf | Node (Tree a) a (Tree a)
-- specifying a is necessary cause a tree should have a particular datatype stored
Using the above defined data-types
-- using the custom datatype Calculation
calc :: Calculation -> Int
calc (Add x y) = x+y
calc (Sub x y) = x-y
calc (Mul x y) = x*y
calc (Div x y) = x/y
tree :: Tree Int
tree = Node (Node Leaf 1 Leaf) 2 (Node (Node Leaf 3 Leaf) 4 Leaf)
-- recursive data-type
add :: PeaNum -> PeaNum -> PeaNum
add Zero n = n
add (Succ m) n = Succ (add m n)
sum :: [PeaNum] -> PeaNum
sum [] = Zero
sum (x:xs) = add x (sum xs)
References
All mighty reference link, an interactive guide:
http://learnyouahaskell.com/
This is a summary/writeup of Lessons by Philipp Hagenlocher
basics
functional
haskell