Haskell: Loops, Recursion

Unlike imperative, object oriented languages Haskell don’t provide loops like while, for. You have to do everything using recursion.

Let me briefly explain about recursion.

In recursion, part of the function calls itself again and again, until it meets the base (terminate) condition.

For example,

Factorial of a number n is denoted by factorial(n) = n * (n-1) * (n-2) * ..... 1.

Base condition for factorial of a number is 0!, we can use 0! As a base condition and proceed execution. We can write function like below.

factorial(n) = 1 If n = 0

                  = n * factorial(n-1) otherwise

Haskell provide number ways to define Recursion.

Method 1: Using if-else block

-- Calculate factorial of a number using if-else if-else ladder
factorialMethod_1 num = 
    if(num < 0)
        then
            -1
    else if(num == 0)
        then
            1
    else
        num * factorialMethod_1(num-1)

Method 2: Using guards

-- Calculate factorial of a number using guards
factorialMethod_guards num
    | (num < 0)  = -1
    | (num == 0) = 1
    | otherwise = (factorialMethod_guards (num-1)) * num

Method 3: Using piece wise definition

-- Calculate factorial of a number using piece-wise definition
factorialMethod_pieceWise 0 = 1
factorialMethod_pieceWise num
    | (num < 0) = -1
    | otherwise = num * factorialMethod_pieceWise (num-1)

Method 4: Using where clause

-- Calculate factorial of a number using where clause
factorialMethod_where num = factorialMethod_where num 1
    where
        factorialMethod_where num base
            | ((num == 0) || (num == 1)) = 1
            | (num > 1) = num * (factorialMethod_where (num-1) 1)
            | otherwise = -1

Following is the complete working application.

recursion.hs

{-Calculate factorial of a number -}

-- Calculate factorial of a number using if-else if-else ladder
factorialMethod_if num = 
    if(num < 0)
        then
            -1
    else if(num == 0)
        then
            1
    else
        num * factorialMethod_if(num-1)

-- Calculate factorial of a number using guards
factorialMethod_guards num
    | (num < 0)  = -1
    | (num == 0) = 1
    | otherwise = (factorialMethod_guards (num-1)) * num

-- Calculate factorial of a number using piece-wise definition
factorialMethod_pieceWise 0 = 1
factorialMethod_pieceWise num
    | (num < 0) = -1
    | otherwise = num * factorialMethod_pieceWise (num-1)

-- Calculate factorial of a number using where clause
factorialMethod_where num = factorialMethod_where num 1
    where
        factorialMethod_where num base
            | ((num == 0) || (num == 1)) = 1
            | (num > 1) = num * (factorialMethod_where (num-1) 1)
            | otherwise = -1

*Main> :load recursion.hs
[1 of 1] Compiling Main             ( recursion.hs, interpreted )
Ok, modules loaded: Main.
*Main> 
*Main> factorialMethod_if 0
1
*Main> factorialMethod_if 10
3628800
*Main> factorialMethod_if (-1)
-1
*Main> 
*Main> factorialMethod_guards 0
1
*Main> factorialMethod_guards 10
3628800
*Main> factorialMethod_guards (-1)
-1
*Main> 
*Main> factorialMethod_pieceWise 0
1
*Main> factorialMethod_pieceWise 10
3628800
*Main> factorialMethod_pieceWise (-1)
-1
*Main> 
*Main> factorialMethod_where 0
1
*Main> factorialMethod_where 10
3628800
*Main> factorialMethod_where (-1)
-1
*Main>

Just practice some programs using recursion, you can get the beauty of Haskell. For your understanding, I am going to write another application, which calculate Fibonacci series.

The Fibonacci Sequence is the series of numbers:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

The next number is found by adding up the two numbers before it. First identify the base condition.

fibonacci(0) = 0, fibonacci(1) = 1 is the base condition,

fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)

Lets rewrite above formula like below.

fibonacci(n) = 0 If (n == 0)

                   = 1 if (n == 1)

                   = fibonacci(n-1) + fibonacci(n-2) otherwise

fibonacci.hs

fib 0 = 0
fib 1 = 1
fib n
    | (n < 0) = -1
    | otherwise = fib(n-1) + fib(n-2)

Prelude> :load fibonacci.hs
[1 of 1] Compiling Main             ( fibonacci.hs, interpreted )
Ok, modules loaded: Main.
*Main> 
*Main> fib 0
0
*Main> fib 1
1
*Main> fib 5
5
*Main> fib 10
55
*Main> fib 9
34
*Main>

Find multiplication of two numbers

Lets try to identify the base conditions.

num1 * 0 = 0

num1 * 1 = num1

num1 * num2 = (num1+ num1 + .....num2 times)

multiplication.hs

-- Calculate multiplication of two positive numbers
mul _ 0 = 0
mul num1 1 = num1
mul num1 num2 =  num1 + (mul num1 (num2-1))

*Main> :load multiplication.hs
[1 of 1] Compiling Main             ( multiplication.hs, interpreted )
Ok, modules loaded: Main.
*Main> 
*Main> mul 10 0
0
*Main> mul 10 1
10
*Main> mul 10 2
20
*Main> mul 10 10
100
*Main> 

Write program to calculate x power y

power(x, 0) = 1
power(x, 1) = x
power(x, y) = x * x *…..y times

power.calc.hs

--Calculate power of x, y
power num1 0 = 1
power num1 1 = num1

power num1 num2
    | (num2 < 0) = (1/(power num1 (-1*num2)))
    | otherwise = num1 * (power num1 (num2-1))

*Main> :load power_calc.hs
[1 of 1] Compiling Main             ( power_calc.hs, interpreted )
Ok, modules loaded: Main.
*Main> 
*Main> power 10 0
1.0
*Main> power 10 1
10.0
*Main> 
*Main> power 10 2
100.0
*Main> 
*Main> power 10 (-2)
1.0e-2

  Write a program, that double every element in the list

Lets try to find the base case for this problem. You can't double the empty list, so base condition is the empty list. For a non-empty list, read element one by one, double it and add to new list.

double_list.hs

doubleList [] = []
doubleList list = (2 * (head list)) : (doubleList (tail list))

*Main> :load double_list.hs
[1 of 1] Compiling Main             ( double_list.hs, interpreted )
Ok, modules loaded: Main.
*Main> 
*Main> doubleList [1, 2, 3, 4]
[2,4,6,8]
*Main> 
*Main> doubleList []
[]

Multiply every element in the list by some constant k

list_util.hs

multiply_list :: Integer -> [Integer] -> [Integer]
multiply_list _ [] = []
multiply_list k list = (k * (head list)) : (multiply_list k (tail list))

*Main> :load list_util.hs
[1 of 1] Compiling Main             ( list_util.hs, interpreted )
Ok, modules loaded: Main.
*Main> 
*Main> multiply_list 5 [1, 2, 3, 4, 5]
[5,10,15,20,25]
*Main> 
*Main> multiply_list (-5) [1, 2, 3, 4, 5]
[-5,-10,-15,-20,-25]
*Main> 

Get all the first elements in list of lists

first_elements.hs

getFirst [] = []
getFirst list = head((head list)) : getFirst(tail list)

[1 of 1] Compiling Main             ( first_elements.hs, interpreted )
Ok, modules loaded: Main.
*Main> 
*Main> getFirst [[1, 2, 3], [4, 5, 6, 7], [8, 9, 10, 11]]
[1,4,8]
*Main> getFirst []
[]
*Main> 

 

Previous                                                 Next                                                 Home