Recursive Thinking in Haskell: Practical Examples

1. Problem runLengthEncode

Implement a function called runLengthEncode that performs run-length encoding on a list of elements. Run-length encoding is a simple form of data compression that replaces consecutive data elements with a single data value and count.

For example:

• Input: "AABBBCCCC"
• Output: [(2,'A'), (3,'B'), (4,'C')]

Coming from javascript background my thought process is:

1. convert the string to a list
2. create a set, to count the occurance of a char
3. iterate over the string list
4. if the currentChar is already in the set, set[currentChar] ++
5. else set it to 1
6. Convert the set which has {char: count} i.e {A:2, B: 3, C:4} into a desired output

Now, we also know that in Haskell, we can do following:

1. Function pattern matching
2. count & char can be passed down as parameter
3. since our problem can be broken down into subproblem, we know we can use recursion to solve while problem

defining function type

runLengthEncode :: String -> [(Int, Char)]

base case:

runLengthEncode "" = []

function body:

1. Convert a string input into a list, leveraging pattern matching.
2. given "AABBBCCCC"
3. x = A, xs = "ABBBCCCC"
4. count of x i,e A. = 1, while starting

runLengthEncode (x:xs) = encode 1 x xs

1. Next we will write out helper encode function:
2. since we are leveraging recursion, we will define a base case.
3. Base case: When we are done processing the last element in the string list i.e C and the remaining list is empty:
4. we will just return (count, char) if the remaining list is empty
5. Recursive case: when the we have elements in the list
6. We will account for if two char matches update count
7. else we will move forward adding the current char & count to the list.

runLengthEncode (x:xs) = encode 1 x xs
  where
    encode count char [] = [(count:char)]
    encode count char (y:ys) 
        | char == y = encode (count + 1) char ys
        | otherwise = (count :char): encode 1 y ys

when we run this code:

main :: IO()
main = print(runLengthEncode "AABBBCCCC")

-- result -- [(2,'A'),(3,'B'),(4,'C')]

visually this is what happening:

2. Problem runLengthDecode

Implement a function called runLengthDecode that decodes a run-length encoded list back into its original string.

For example:

• Input: [(2,'A'), (3,'B'), (4,'C')]
• Output: "AABBBCCCC"

We need to learn a replicate

replicate Int -> a -> [a]
replicate 3 'A' -- AAA
replicate 5 0 -- 00000

let's now work on this problem 2.

runLengthDecode :: [(Int, Char)] -> String
runLengthDecode [] = ""

runLengthDecode ((count, char): xs)
 = replicate count char ++ runLenthDecode xs

3. Palindrome Checker

Palindrome Checker: Implement a function that checks if a given string is a palindrome. This will help you practice string manipulation and recursion. 

{--
radar
level
madam
--}

isPalindrome :: string -> Bool
isPalindrome str = str == reverse str

import Data.Char (toLower, isAlphaNum)
isPalindromeCaseIn :: String -> Bool
isPalindromeCaseIn str = lower == reverse lower
  where lower = map toLower str

isPalindromeIgnoreNonAlphaNum :: String -> Bool
isPalindromeIgnoreNonAlphaNum str = cleaned == reverse cleaned
  where cleaned = filter isAlphaNum (map toLower str)

4. List Compression:

List Compression: Implement a function that compresses a list by replacing consecutive duplicates with a single copy. This is similar to run-length encoding but without counting. 

dropWhile:

dropWhile (<3) [1,2,3, 4, 1, 2] return [3, 4, 1, 2]

• It drops elements while they are less than 3.
• It stops as soon as it encounters 3, which is not less than 3.
• The rest of the list (including 1 and 2 later) is kept

dropWhile even [2, 4, 6, 7, 8, 9] returns [7,8,9]

• it drops elements while they are even
• it stops as soon as it encounter 7, which is not event
• The rest of the list (including 8, which is even) is kept

dropWhile isUpper "ABcdeFG" return "cdeFG"

• It drops AB while they are uppercase
• It stops as soon as it encounter 'c'
• The rest Of the string Uppercase is kept

The key point to understand is that dropWhile only operates on the beginning of the list or string. It stops as soon as it encounters an element that doesn't satisfy the condition, and then it returns the rest of the list or string from that point on, regardless of whether later elements would satisfy the condition.

Example usage:

compress [1,1,2,3,3,3,1,1] -- Returns [1,2,3,1]

compress "AABBBCCCC" -- Returns "ABC"

compress :: [Int] -> [Int]
compress [] = []
compress (x: xs) = x: compress (dropWhile ( ==x) xs)

5. Fibonacci Sequence:

Implement a function to generate the fibonacci sequence up n terms.

fibonachi :: Int -> [Int]
fibonachi n = map fib [0..n-1]
  where 
    fib 0 = 0
    fib 1 = 1
    fib n = fib(n-1) + fib(n-2)

-- fibonacci 5 [0,1,1,2,3]

#Haskell #computerScience #practiceSyntax