CODEWITHSUNDEEP
listhaskelllogichaskell-stackhaskell-platform
Gabriel Monteiro Silva
Gabriel Monteiro Silva

Reputation: 55

understand haskell logic behind odd's and even's index lists

I had a question in haskell that asks a function to divide a list in two different lists so the even indexs filled a list and the odd ones another. Example:

func :: [Int] -> ([Int], [Int])

Then, if we enter with [44,8,11,23], we expected receive [44,11] and [8,23]. Looking in the internet I found a great and geniaus solution but can't understand the logic behind it:

func :: [Int] -> ([Int], [Int])
func [] = ([], [])
func [x] = ([x], [])
func (x:y:xs) = (x:odds, y:evens)
    where
    (odds, evens) = func xs

I know that there are "odd" and "even" functions in haskell, but what would mean "odds" and "evens". How tha values go righty to the certain list? I am drowning in doubt because of this.

I am looking in severals foruns and tutorials to try understand the logic of this code but I am in the zero level until now.

Upvotes: 1

Views: 99

Answers (2)

Jon Purdy
Jon Purdy

Reputation: 55069

I know that there are "odd" and "even" functions in haskell, but what would mean "odds" and "evens".

odds & evens are just variable names. They’re not directly related to the odd & even functions. They’re plural (ending in s) because that’s the Haskell naming convention for lists.

Let’s work step-by-step through your example input, starting with func [44, 8, 11, 23].

Since this is a recursive function, there will be multiple calls to func, with their own local variables. To avoid confusion, I will add numbers to the local variables for each call, e.g. x1 and x2 instead of just x.

First, func [44, 8, 11, 23] matches the third clause of func, func (x : y : xs).

let
  x1 = 44
  y1 = 8
  xs1 = [11, 23]
  (odds1, evens1) = func xs1
in (x1 : odds1, y1 : evens1)

This can be simplified a bit.

let
  (odds1, evens1) = func [11, 23]
in (44 : odds1, 8 : evens1)

Now we need to know the value of func [11, 23]. This also matches the third clause.

let
  (odds1, evens1) = let
    x2 = 11
    y2 = 23
    xs2 = []
    (odds2, evens2) = func xs2
    in (x2 : odds2, y2 : evens2)
in (44 : odds1, 8 : evens1)

And again we can simplify.

let
  (odds1, evens1) = let
    (odds2, evens2) = func []
    in (11 : odds2, 23 : evens2)
in (44 : odds1, 8 : evens1)

Finally, func [] matches the first clause, func [] = ([], []).

let
  (odds1, evens1) = let
    (odds2, evens2) = ([], [])
    in (11 : odds2, 23 : evens2)
in (44 : odds1, 8 : evens1)

So we can continue simplifying until we get a solution.

let
  (odds1, evens1) = let
    odds2 = []
    evens2 = []
    in (11 : odds2, 23 : evens2)
in (44 : odds1, 8 : evens1)

let
  (odds1, evens1) = (11 : [], 23 : [])
in (44 : odds1, 8 : evens1)

let
  odds1 = 11 : []
  evens1 = 23 : []
in (44 : odds1, 8 : evens1)

(44 : 11 : [], 8 : 23 : [])

([44, 11], [8, 23])

Upvotes: 3

chi
chi

Reputation: 116174

Piece by piece:

func (x:y:xs) = ...

When the input has length >=2, starting with x and y and then continuing with the list xs ...

          ... = (x:odds, y:evens)

... the result is a pair, whose first component is x : odds and the second component is y : evens. The variables odds and evens are defined as ...

    where
    (odds, evens) = func xs

... those (list) values which result from the recursive call func xs.

Let's make an example:

func [1,2,3,4] =
func (1:2:xs) =   -- with xs = [3,4]
(1:odds, 2:evens) 
where (odds, evens) = func xs = func [3,4]

To complete the computation, we then compute the recursive call:

func [3,4] =
func (3:4:xs2) =  -- with xs2 = []
(3:odds2, 4:odds2)
where (odds2, evens2) = func xs2 = func []

One more recursive call to compute, but that's immediate: func [] = ([], []).

So, we have

(odds2, evens2) = func [] = ([],[])
-- hence
odds2 = evens2 = []

Having discovered that, we obtain from the previous equation:

func [3,4] = (3:[], 4:[]) = ([3], [4])

So, we have

(odds, even) = ([3], [4])
-- hence
odds = [3]
evens = [4]

so we obtain from the even older equation:

func [1,2,3,4] = (1:odds, 2:evens) = (1:[3], 2:[4]) = ([1,3], [2,4])

Upvotes: 3

Related Questions