First take on Haskell

December 23, 2021

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

---