Haskell: Recursion in Functional Programming (2022)

--- tags: programming languages, haskell --- # Haskell: Recursion in Functional Programming (Part of the course *Programming Languages*) ## Prerequisites #### Installation You have Haskell installed and you can start the interactive Haskell console in a terminal. On my machine it looks like this >ghci GHCi, version 8.8.3: https://www.haskell.org/ghc/ :? for help Prelude> This is similar to the Python console. You can ask Haskell questions now, such as Prelude> 2*3 6 Prelude> n=2 Prelude> n 2 Prelude> n*3 6 Prelude> n*x <interactive>:4:3: error: Variable not in scope: x Prelude> Use `control-d` to close the console. #### Tutorial (Recommended) You have followed the tutorial at [tryhaskell.org](http://tryhaskell.org/). (If you experiment further you will notice that the Haskell-in-the-browser at`tryhaskell.org` gives you only a fragment of `ghci`.) ## First Steps in Haskell As we said before, Haskell can be interpreted and compiled. Above, we used the interpreter `ghci` to run Haskell in the console. (Recall that a Haskell programm with a `main`-function can also be compiled and run with `runhaskell`.) **Activity:** Use the Haskell console (also called REPL for read-evaluate-print-loop) to run some experiments. ("evaluate" is another word for "interprete".) Use Haskell as a calculator. Try to produce both expected results and errors. Can you use Haskell as a calculator? If you are in class ask in the chat, otherwise do a Google search if you have questions. One of the possibly surprising features of functional programming is that everything is an expression and evaluates. **Activity:** (If you dont have a local Haskell installation yet, you can run Haskell in a browser at [replit](https://replit.com/languages/haskell).) To evaluate expressions try something along the following lines. ```haskell main = print (40+2) ``` or ```haskell x=7 main = print (5*x+7) ``` or (if you have more than one thing to print) ```haskell x=7 main = do print (5*x+7) print 64 ``` If you enter the above in the Haskell console, you can run `main` by simply entering `main`. ## Lists in Haskell Lists in Haskell can be **constructed** in several ways. The basic ones are the following ```haskell [] ``` is the empty list and if `x` is some data and `xs` is a list then ```haskell x:xs ``` is the list that has `x` as its first element and continues with `xs`. We can also write ```haskell [3,6,2,1] ``` as an abbreviation of ```haskell 3:(6:(2:(1:[]))) ``` where we are allowed to drop the parentheses ```haskell 3:6:2:1:[] ``` If we want to **deconstruct** a list into its elements we can use built-in functions head and tail which are defined by the equations ```haskell head(x:xs) = x tail(x:xs) = xs ``` **Warning:** Haskell has no assignment. `=` reads more like a mathematical equality. **Example:** Save the following program ```haskell len [] = 0 len (x:xs) = 1 + len xs ``` in a file called `lists.hs` and run it in a console.[^length] [^length]: Haskell has a built in function `length` with the same functionality. But here we want to see how to write it from scratch. On my machine, I have the following dialogue ghci Prelude> :load lists.hs and test it with various lists such as in *Main> len [1,2,3] 3 **Exercise:** Implement the factorial function in Haskell. (A solution can be found in [Haskell in 5 steps](https://wiki.haskell.org/Haskell_in_5_steps).) ## Types One reason why Haskell will be a powerful tool to implement interpreters is that Haskell is *strongly typed*. We will learn later more about what that means and why this is so powerful. At the moment, this section on types is just needed for general background. If your aim is to get started quickly, types can be largely ignored. The reason for this, as we will learn later, is that Haskell has automated *type inference*. This means that even if you do do not specify the types of your Haskell programs, Haskell can (often) infer the types. This is why we choose to ignore types in the remainder of this lecture. But types may become visible to you anyway, for example in error messages or because your editor is configured to automatically display types. So it is good to have some rough acquaintance with types. I keep this section to a minimum, more information is available in many places, for example at [learnyouahaskell](http://learnyouahaskell.com/types-and-typeclasses). In `ghci`, we can use `:t` to ask for the type of a program. ```haskell Prelude> :t 'a' 'a' :: Char Prelude> :t "a" "a" :: [Char] ``` This tells us that `'a'` is a `Char` and that `"a"` is list of `Char`. Btw, we should be able to write a list containing `'a'` also using the `[...]`. A good way to learn Haskell is whenever you have a question like to ask the console. So let us try ```haskell Prelude> "a"==[a] <interactive> error: Variable not in scope: a :: Char ``` Oops ... sth went wrong. **Exercise:** Can you explain the error message? Can you fix the error? (So that we get the expected answer `True`.)  One more experiment about lists: ```haskell Prelude> list = 'a':'b':'c':[] ``` What is the type of `list` we expect now? (Btw, one of the important principles of the scientific method is to **always be explicit about what outcome you expect before performing an experiment.**) ```haskell Prelude> :t list list :: [Char] ``` Ok, next we should learn about function types. Let us try a few functions, we have seen before. What is the type of `head`? It is a function that takes a list and returns the first element. Let us see how this is expressed in Haskell: ```haskell Prelude> :t head head :: [a] -> a ``` Makes sense, doesn't it? `->` separates input from output. Input is a list of `a`s and output is an `a`. But what does `a` stand for? `a` is a so-called *type variable* and `head` is a *polymorphic function*. Again, type variables and polymorphism is sth we will hear more about later. For now, let us just say that the use of the type variable `a` allows us to type a function like `head` that works the same whatever the type of the elements of the list is. (This makes sense: All `head` does is to take the first element ... the same algorithm, whether you have a list of integers or a list of characters.) What types have numbers. There is a potential problem here, for example, the number `2` can be an integer or a fraction or a real number and maybe more. As we said before, Haskell has type inference which allows the programmer to ignore types in many situations. But what if the programmer does not specify the type of, say, `2`? The answer is *type classes*. A type class is an interface that can be instantiated in various ways. For example there is a type class `Num`. ```haskell Prelude> :t 2 2 :: Num p => p ``` `Num p => p` tells us that if `p` is an instance of `Num` then the type of `2` is `p`. The "if-then" in the previous sentence is rendered by Haskell as `=>`. As you can see, it has a different meaning than the `->` in, say, `head :: [a] -> a`. **Homework:** Read [Chapter 3: Types and Typeclasses](http://learnyouahaskell.com/types-and-typeclasses) of Learn You a Haskell. ` ## <font color=red>Homework (Week 2) for the Report</font> As we said before, you can ignore types for now. The aim for now is to learn how to write recursive functions. We have seen examples `fib` and `len` above. Now try your own. If you need more background I recommend Chapters 2, 3 and 5 of [Learn You a Haskell](http://learnyouahaskell.com/chapters). **Task 1:** Implement in Haskell the following functions select_evens select_odds member append revert less_equal Examples: *Main> select_evens ["a","b","c","d","e"] ["b","d"] *Main> select_odds ["a","b","c","d","e"] ["a",c","e"] *Main> member 2 [5,2,6] True *Main> member 3 [5,2,6] False *Main> append [1,2] [3,4,5] [1,2,3,4,5] *Main> revert [1,2,3] [3,2,1] *Main> less_equal [1,2,3] [2,3,4] True *Main> less_equal [1,2,3] [2,3,2] False *Main> Remember that Haskell does not have assignment or for-loops. All these exercises can be solved with pattern matching and recursion, just as we did for `fib` and `len`. (Btw, you can put all functions in the same file.)[^lists.hs] **Task 2:** Similar to Homework 1 and our example `fib 6`, show the computations taken in one selected example. ## More Haskell exercises (Optional) **Zipping two lists** The function `zipp` should merge two lists taking elements from the lists in turn, very much like a zipper. Example: *Main> zipp [1,2,3] [4,5,6,7,8] [1,4,2,5,3,6,7,8] Remark: The following should always be true zipp (select_odds xs) (select_evens xs) = xs **Merging two lists of integers** merge merge_sort For `merge_sort` implement an algorithm that does, for example, the following computation: [6,5,4,3,2,1,7,8] = [[6],[5],[4],[3],[2],[1],[7],[8]] = [[5,6],[3,4],[1,2],[7,8]] and then keeps on merging neighbouring lists as follows = [[3,4,5,6],[1,2,7,8]] = [[1,2,3,4,5,6,7,8]] until only one list remains. Explain why this list is always sorted. Benchmark your algorithm. What time complexity does it have? **Summing a list of integers** *Main> summ [1,2,3,4] 10 *Main> mean [1,2,1] 1.3333333333333333 *Main> prod [1,2,3,4] 24 *Main> summs [0,1,2] [4,5,6] [4,6,8] *Main> prods [0,1,2] [4,5,6] [0,5,12] #### Recursion over numbers The idea is not to use a closed formula (even if there is one), but to practice recursive programming. So defining a function `func` would typically follow the pattern func 0 = ... func n = ... see also the example of `fib` in the first lecture. *Main> triangle_number 4 10 *Main> sums_of_squares 3 14 The examples above can be found at the [Online Encyclopedia of Integer Sequences](https://oeis.org/) under [A000217](https://oeis.org/A000217) and [A000330](https://oeis.org/A000330). Why don't you explore and implement some more sequences such as [the number of different RNA structures for sequences of length n.](https://oeis.org/A170941) ## Further Resources [Haskell in 5 steps](https://wiki.haskell.org/Haskell_in_5_steps) [Comparing Haskell and Python Lists](https://hackmd.io/@alexhkurz/BkCGLGkXv) ... btw, there is a data structure for efficient indexing in Haskell, see [Haskell Vectors](https://hackage.haskell.org/package/vector), but we will not need this in this course. The tutorials referenced at [Haskell in 5 steps](https://wiki.haskell.org/Haskell_in_5_steps). The first two videos of the tutorial [Haskell for Imperative Programmers](https://www.youtube.com/watch?v=Vgu82wiiZ90) cover the material in greater depth ... well worth watching, even if it contains stuff we didn't do (yet). Wikibooks/Haskell: - [Truth values](https://en.wikibooks.org/wiki/Haskell/Truth_values) - [Lists and tuples](https://en.wikibooks.org/wiki/Haskell/Lists_and_tuples) Gayle Laakmann McDowell explains in [Algorithms: Recursion](https://www.youtube.com/watch?v=KEEKn7Me-ms) recursion as a problem solving technique. [Recursive image rotation](https://www.youtube.com/watch?v=OXo-uzzD4Js&feature=emb_logo) is a great visual example of recursion. [^leetcode48] [^leetcode48]: This is problem [LeetCode 48](https://leetcode.com/problems/rotate-image/) and [Fisher Coder](https://www.youtube.com/channel/UCPL5uAbYQ40HwAdOe4ikI0w) has a good [explanation](https://www.youtube.com/watch?v=gCciKhaK2v8). ## tl;dr [Fast Sorting with Haskell](https://www.reddit.com/r/haskell/comments/5wkyv4/delazification_of_algorithms/) [^lists.hs]: [Solution](https://github.com/alexhkurz/programming-languages-2020/blob/master/Answers/lists.hs).