If You Must Learn Haskall ( Introduction )

The Pure Functional Programming Language.

• Its pure, thus has no side-effects.

  • No Mutations

  • No Changing the environment like removing stuff and adding stuff to the streams.

• Haskall doesn't tell the program what to do, instead it tells the program what is.

  • Perks of no side-effects?

    • Referential Transparency,

      • If a function is called twice, it is guaranteed to return the same result.

    • BETTER/EASIER REASONING with program's behaviour

      • Allows to easily deduce if a function is correct.

        • Then build more complex functions by gluing simple ones together !

• Haskall is Lazy

  • Won't Calculate results/execute functions until asked to produce result.

• USES:

  • Very Powerful in Pattern Matching, which makes stuff later in CS146, very accessible.

• 

+ expects the left and right side of the operator to be NUMBERS.

== can compare anything of the same type, exclusive.

5 + 4.0 because 5 is sneaky and can act like an integer or a floating-point number. 4.0 can’t act like an integer, so 5 is the one that has to adapt.

Note: GHC errors are all assigned unique identifiers such as GHC-39999 above. Whenever you are stuck with a stubborn error, you can look it up at https://errors.haskell.org/ to learn typical causes and solutions.

We actually been using functions all along, *, takes two numbers and multiplies them.

A function that is sandwiched between two terms is called an infix function.

Most functions that aren't used with numbers are prefix functions.

In Haskell, functions are called by writing the function name, a space and then the parameters, separated by spaces. For a start, we’ll try calling one of the most boring functions in Haskell

ghci >succ 8
> 9 

returns immediate successor.

Other functions

ghci> min 9 10  
9  
ghci> max 100 101  
101  

Function Application, which is basically calling the function by typing the function name, delimited by a space, followed by the parameters, has the highest precedence in the Order of Operations Thus.

ghci> succ 9 + max 5 4 + 1 

is equivalent to:

ghci> (succ 9) + (max 5 4) + 1 

Converting prefix functions to infix functions.

>ghci div 92 10 

is equivalent to:

>ghci 92 `div` 10

• Notice the backticks

To define a function, it's basically the same as how you would apply the function but you have to add an equal sign at the end.

doubleMe x = x + x  

Saving this in a file as a baby.hs, navigating to where it's saved, run ghci. After that we can load the function, using

:l baby

+ works on integer, as well on floating-point numbers ( anything can be considered a number, really )

Note how this works for any number !

doubleMe x = x + x
doubleUs x y = x*2 + y*2
doubleTest x y = doubleMe 6 + doubleUs 6 7 + 6

This is a very simple example of a common pattern you will see throughout Haskell. Making basic functions that are obviously correct and then combining them into more complex functions. This way you also avoid repetition. What if some mathematicians figured out that 2 is actually 3 and you had to change your program? You could just redefine doubleMe to be x + x + x and since doubleUs calls doubleMe, it would automatically work in this strange new world where 2 is 3.

Functions in Haskell don’t have to be in any particular order, so it doesn’t matter if you define doubleMe first and then doubleUs or if you do it the other way around.

If Statements

• If statements are pretty similar in the Haskall language except that the else is mandatory !

• Every block must return something, for the if statement to be valid !

• If statements are expressions ( Any piece of code that returns something ), this reinforces the second AND first point.

doubleSmallNumber' x = (if x > 100 then x else x*2) + 1  

Had we omitted the parentheses, it would have added one only if x wasn’t greater than 100. Note the ' at the end of the function name. That apostrophe doesn’t have any special meaning in Haskell’s syntax. It’s a valid character to use in a function name. We usually use ' to either denote a strict version of a function (one that isn’t lazy) or a slightly modified version of a function or a variable. Because ' is a valid character in functions, we can make a function like this.

conanO'Brien = "It's a-me, Conan O'Brien!"  

In Haskall, functions can't begin with Upper Case Letters.

If a function doesn't contain any parameters, its called a Definition ( or a name ).

Because of referiental transparency,

conanO'Brien

can be used interchangably with

"It's a-me, Conan O'Brien!"  

An Introduction to Lists

• Homogeneous Data Structure

  • May only store elements of the same type.

ghci> lostNumbers = [4,8,15,16,23,42]
ghci> lostNumbers
[4,8,15,16,23,42]

Strings, in Haskall, are just lists of characters. Thus, we may use list operations/functions on strings!

Use the ++ operator to append two lists together ( basically the append in HASKALL )

ghci> [1,2,3,4] ++ [9,10,11,12]
[1,2,3,4,9,10,11,12]

The order of ++ MATTERS!!

[1,2,3] ++ [4], means traversing through the whole list on the left, where as the other way to represent this, one must only go through 1 elt.

The "cons" in Haskall, is ":".

e.g.

ghci> 'A':" Small Cat"
"A Small Cat"
ghci> 5:[1,2,3,4,5]
[5,1,2,3,4,5]

Note that [1,2,3] is just syntax sugar for 1:2:3:[] , where [] is the empty list.

Get an element out by index using !!:

ghci> "Steve Bob" !! 6
'B'
ghci> [9.4,33.2,96.2,11.2,23.25] !! 1
33.2

• Index must exist in the list, other else error.

• Lists can be compared if and only if the elements in the list can be compared.

  • Compared in Lexicographical Order.

    • If first few elements are equal, then the next pair of elts are done so.

    • Commands:

      • Head

      • Tail

      • Last

      • Init

Trying to use these operations on an empty list cannot be caught at run-time.

• length [lst]: returns length of list.

• null [lst]: checks if lst is empty.

• reverse [lst]: reverses lst.

• take int [lst]: takes the int amount of numbers from start of list.

take won't error if you try to take more elements than in the list. It just returns the original untouched list.

• drop int [lst]: takes int amount of numbers from end of list.

• maximum [lst]: returns maximum elt of a list

• minimum [lst]: returns minimum elt of a list

• product [lst]: returns product of all elts in list

• elem elt [lst]: checks if elt is in lst, usually used as infix expression tho.

  • elt`elem`[lst]

Ranges

• Motivation: getting the list of elts from 1-20.

  • Use a range.

    • Perfect for lists that can be represented by an aritimetic sequence or sequences that can be enumerated ( in some order ).

[1..20]

is equivalent to

[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]

ghci> [1..20]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]  
ghci> ['a'..'z']
"abcdefghijklmnopqrstuvwxyz"
ghci> ['K'..'Z']
"KLMNOPQRSTUVWXYZ"  

Introducing Steps:

ghci> [2,4,..,20]
[2,4,6,8,10,12,14,16,18,20]  
ghci> [3,6,..,20]
[3,6,9,12,15,18]  

To introduce steps, simply denote the first two elements of the sequence, then specifying the upper limit.

It's not as smart as you think though.

[1,2,4,8,16,..100]

does not return the powers of 2.

You can only specify one step, because some sequences that aren't arithmetic are ambiguous !

e.g.

to make numbers from 20-1, [20,..,1] is not enough, you have to do [20,19,..,1].

Watch out when using floating point numbers in ranges. They are, by definition, not precise.

Its recommanded to not use them in list ranges.

e.g.

ghci> [0.1,0.3 ..1]
[0.1,0.3,0.5,0.7,0.8999999999999999,1.0999999999999999]  

• We can specify infinite lists here because of Haskall's lazy nature.

e.g.

take 24 [13,26..]

Getting 24 elements out of the infinite list.

Ways to create infinite lists.

cycle

Takes a list and cycles it into an infinite list.

repeat

Takes an element and produces an infinite list of just that element. Essentially, cycle, but with a one element list.

Consider a standard set definition ( called set comprehensions )

This is made up of three components:

1. The Output Function ( 2 * x )

2. $\mathbb{N}$, is the input set.

3. $x\leq 10$ is the predicate.

This set can be created by take 10 [2,4,..] for more complicated functions we use list comprehensions ( similar structure to set comprehensions ).

• E.g.

ghci> [x*2 | x <- [1,..,10]]
[2,4,6,8,10,12,14,16,18,20]

• Gets every element from [1,..,10], then doubles it.

ghci> [x*2 | x <- [1..10], x*2 >= 12]  
[12,14,16,18,20]  

• The double of every number whose double is greater than or equal to 12.

ghci> [x | x <- [50,..,100], x `mod` 7==3]  
[52,59,66,73,80,87,94]  

• Takes every number from 50-100, whose remainder when divided by 7 is 3.

• This weeding out process is called filtering.

ghci> myFun lst =  [ if x < 10 then "BOOM!" else "BANG!" | x <- lst, x `mod` 2 == 1]
or
ghci> myFun lst =  [ if x < 10 then "BOOM!" else "BANG!" | x <- lst, odd x]

• Removes all even elements, if the element is less than 10, its replaced by the string, "BOOM!"

• Greater than or equal to its "BANG!"

ghci> [ x|x <- [10..20], x/=13, x/=15, x/=19]
[10,11,12,14,16,17,18,20]  

• We can stack predicates ( elements must satisfy all predicates ! )

We can "draw" from multiple functions.

• Produces all combinations between the elements of the functions

ghci> [ x*y | x <- [2,5,10], y <- [8,10,11]]  
[16,20,22,40,50,55,80,100,110]  

e.g.

If the length of two lists were 9, drawing from both will result in a list of length 81.

Every combination for funny names.

ghci> nouns = ["hobo","frog","pope"]  
ghci> adjectives = ["lazy","grouchy","scheming"]  
ghci> [adjective ++ " " ++ noun | adjective <- adjectives, noun <- nouns]  
["lazy hobo","lazy frog","lazy pope","grouchy hobo","grouchy frog",  
"grouchy pope","scheming hobo","scheming frog","scheming pope"]  

Implementing our own version of length.

ghci> length' xs = sum [1 | _ <-xs]

• _ indicates we don't care about the drawn element from the set.

Strings, as lists, can also be made from list comprehensions.

ghci> removeNonUppercase st = [c | c <-st, c `elem` ['A'..'Z']]

ghci> let xxs = [[1,3,5,2,3,1,2,4,5],[1,2,3,4,5,6,7,8,9],[1,2,4,2,1,6,3,1,3,2,3,6]]  
ghci> [ [ x | x <- xs, even x ] | xs <- xxs]  
[[2,2,4],[2,4,6,8],[2,4,2,6,2,6]]  

• Removing all the odd numbers without flattening list.

Tuples

• Storing several values as one value.

• Unlike lists where the length is arbitrary, the length of tuples and the type of elements inside are clear.

• No homogeneous.

(1,2)

• the above is a tuple of size 2, which is a pair.

• Each different-sized tuple is its own type. So you can't write a general function to append an element to a tuple of size n, thus a separate function needs to be made for every tuple size.

There does not exist size-1 tuples ( why? )

Unlike lists, we can't compare tuples of different sizes.

• fst

ghci> fst (8,11)
8
ghci> fst ("Wow", False)
"Wow"

• snd

ghci> snd (8,11)
11
ghci> ("Wow", False)
False

These functions only work on pairs.

• Zip

  • Produces a list of pairs.

  • Taking two lists, pairs the corresponding elements of the two lists and puts them in a list.

  • Useful for combining lists in an useful way and traversing two lists simultaneously.

ghci> zip [1,2,3,4,5] [5,5,5,5,5]
[(1,5),(2,5),(3,5),(4,5),(5,5)]
ghci> zip [1..5] ["one","two", "three", "four", "five"]
[(1,"one"), (2,"two"), (3, "three"), (4, "four"), (5, "five")]

For lists of different lengths, the longer list is cut off to match with the shorter one. This allows for the utility of infinite lists !

e.g.

ghci> zip [1..] ["apple", "orange", "cherry", "mango"]  
[(1,"apple"),(2,"orange"),(3,"cherry"),(4,"mango")] 

Common Theme in Haskall Problem-Solving

• Start with a huge solution set of possible solutions, then filter and trim it down with predicates until the desired set is reached.

  • This is exactly the Branch and Cut method from the TSP lol !