CODEWITHSUNDEEP
listhaskellrecursion
Cara
Cara

Reputation: 165

How does recursion work in Haskell? - Example merge function

if we look at the funtion definition of merge

merge (x:xs) (y:ys) | x <= y    = x:merge xs (y:ys)
                    | otherwise = y:merge (x:xs) ys

With the input [2,3] [4,1]

the first step looks like this

2<=4 => 2:merge [3] (1:[4])

Here my question lies: The first head element of the second list was 4 but since 2<=4 nothing was done with 4 so the 4 has to be still in the second list but the 4 needs to be the last element in the list now so 3 can be compared to the 1. I wonder how the compiler changes the second list: At first 4 was the head element but since it makes none sense to compare the 3 to the 4 again the indices has to be switched.

So the compiler just put the head element to the end of the list after the first comparison? Or what does the compiler do here?

Upvotes: 1

Views: 112

Answers (2)

chepner
chepner

Reputation: 531055

3 isn't compared to 1 until it has been compared to 4 as well; merge preserves the relative order of each value within a single list.

The recursion proceeds as follows:

merge [2,3] [4,1] == 2 : merge [3] [4,1]  -- 2 < 4
                  == 2 : 3 : merge [] [4, 1] -- 3 < 4
                  == 2 : 3 : [4, 1] -- assuming merge [] ys == ys

Don't confuse merge with mergeSort, which uses merge as a subroutine.

mergeSort [] = []
mergeSort xs = merge (mergeSort first) (mergeSort second)
   where (first, second) = split xs
         split xs = ... -- some function to split a list roughly in half

The order-preserving behavior of merge is what makes mergeSort a stable sorting algorithm.

Upvotes: 3

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476574

I wonder how the compiler changes the second list.

It does not. If we call merge [2,3] [4,1] then the clause you describe will fire, with: x = 2, y = 4, xs = [3] and ys = [1]. It will indeed check that 2 <= 4, which holds, and then call merge with:

x : merge xs (y:ys)

so that means that if we use the variables we just assigned, we get:

2 : merge [3] (4:[1])

or less verbose:

2 : merge [3] [4,1]

I wonder how the compiler changes the second list: At first 4 was the head element but since it makes none sense to compare the 3 to the 4 again the indices has to be switched.

Such merge function often has a precondition that the two lists it aims to merge, are sorted individually already. So normally merge [2,3] [4,1] will not be called with an algorithm like MergeSort, the two lists are first sorted, and then it is thus called with merge [2,3] [1,4].

Upvotes: 4

Related Questions