**Course Title:** Functional Programming with Haskell: From Fundamentals to Advanced Concepts **Section Title:** Recursion and Higher-Order Functions **Topic:** Implement recursive functions and higher-order functions to solve problems.(Lab topic) **Objective:** In this lab, you will apply your knowledge of recursive functions and higher-order functions to solve problems in Haskell. You will write and test several functions, exploring how these concepts can be used to tackle various challenges. **Background** Recursion and higher-order functions are fundamental building blocks of functional programming. By using recursion, you can break down complex problems into smaller sub-problems, making your code more elegant and efficient. Higher-order functions, on the other hand, enable you to create more abstract code by passing functions as arguments to other functions or returning functions as output. **Problem 1: Summing a List of Numbers** Write a recursive function `sumList` that takes a list of integers and returns their sum. ```haskell sumList :: [Int] -> Int sumList [] = 0 sumList (x:xs) = x + sumList xs ``` This function uses a base case (an empty list) and a recursive case (a non-empty list). The recursive case breaks the list into the first element `x` and the rest of the list `xs`, then adds `x` to the sum of the rest of the list. **Problem 2: Filtering a List** Implement a higher-order function `filterList` that takes a predicate `p` and a list `xs` as input, returning a new list that only contains elements for which `p` holds. ```haskell filterList :: (a -> Bool) -> [a] -> [a] filterList p [] = [] filterList p (x:xs) | p x = x : filterList p xs | otherwise = filterList p xs ``` In this function, the predicate `p` is applied to each element in the list. If the element satisfies the predicate, it is included in the new list; otherwise, it is excluded. **Problem 3: Computing the Fibonacci Sequence** Write a recursive function `fibonacci` that generates the Fibonacci sequence up to the given integer `n`. ```haskell fibonacci :: Int -> [Int] fibonacci 0 = [] fibonacci 1 = [1] fibonacci n = [1, 1] ++ map (uncurry (+)) (zip [1,1..] (0 : [1,1..])) where takeUntil x n = takeWhile (< x) [n..] ``` This function first defines the base cases (0 and 1), then uses a recursive approach to generate the sequence. **Problem 4: Using the Fold Function** Implement a function `factorial` using the foldl function. ```haskell factorial :: Int -> Int factorial 0 = 1 factorial n = foldl1 (*) [1..n] ``` The foldl1 function applies a binary function to the first elements of a list, and uses the result as the first element of the new list. **Conclusion** In this lab, you have applied your knowledge of recursive functions and higher-order functions to solve problems in Haskell. You have seen how these concepts can be used to break down complex problems into smaller sub-problems and how to create abstract code by passing functions as arguments to other functions or returning functions as output. **Activity** After completing these problems, you can try to implement some additional functions: * Implement a function that reverse a list without using the reversed function. * Create a higher-order function that makes possible to change case of text. You have now covered one of the core concepts of Haskell, recursion and higher-order functions. Keep practicing with different problems and you'll develop a strong foundation in functional programming. **What's next?** In the next topic, we'll explore **"Understanding Haskell's strong, static type system"**, where we'll see how Haskell's type inference can assist you in creating correct and well-typed code. **Additional Links** If you'd like to learn more about these topics, here are some useful resources: * [Haskell and Functional Programming](https://learnyouahaskell.com/) * [Real World Haskell](https://book.realworldhaskell.org/) * [Recursion and Higher-Order Functions in Haskell](https://pursuitoflazyevaluationbyabysstractia.tumblr.com/post/141330186773/recursion-and-higher-order-functions-in-haskell) Please, write a comment if you need further help or want to share any of your thoughts about Haskell, keep practicing!