Converting List to Integer in Haskell

aabusang December 16, 2024 Algorithms

You are given a list of integers, convert the list into an integer. With the digits in the same order as the order in the list.

{-

Example 1: listToInt [5, 7, 4, 6] === 5746
Example 2: listToInt [1, 9, 7, 8, 6, 0] === 197860
Example 2: listToInt [2, 0, 3, 6, 1] === 20361
-}

listToInt :: [Int] -> Int
listToInt = undefined -- your solution here

Possible Solutions

Here are several approaches we can take to solve this problem:

Direct explicit recursion
Using foldr
Tail Recursion
Using foldl
List comprehension

Understanding the Problem

Trust me, this is NOT a mathematical rabbit hole about the nature of numbers. I am not that smart yet. it’s much simpler.

So “baby calm down”

There are just 3 parts to this problem:

How decimal numbers (base) are built
An equations to abstract the idea
From math to code

1. Understanding Decimal Number Structure

Remember the position of numbers and their relative values
from primary school?

Here we are only dealing with decimal as in base 10 numerals not numbers with a decimal point. 10 not 10.0

So our input list is assumed to have only based 10 integers.

Each number’s value is commucated by it’s position in the numbers. Starting from the right we have ones, tens, hundreds, thousands, etc. so 2024 will be broken down as: - 4: ones - 2: tens - 0: hundreds - 2: thousands

Each place is 10 times greater than the place to the right.

Yes that is all the math we need.

2. Mathematical Abstraction

I could see the solution pattern when I worked it out by hand. it needed recursive function. But I got stuck trying to turn this insight into actual code or a mathematical formula.

So jumping ahead just a bit.
The code would look something like this in plain english:

if input list has only one element, 
    then return that element
if input list has more than one element.

        then take the first element out to the left
        add it to the next element multiplied by 10. 
        -- wait what? where is left?

        Why multiplied by 10? 
            Remember "Each place is 10X > the place to the right"?
            So the position of the 1 in [1,8,2,9] is 10 times greater  
            than the position of the 8  
            and the 8 is 10X > than the 2 and the 2, 10X > the 9 and  
            so forth if there were more digits.  
            
            Our base case will say if list have one element,
                return just that one element, don't multiply
                it by 10 or do anything, just return that one element.

  
    else if input list has > 2 numbers like: [3, 2]:
            we get 3 + (2 * 10)
                   3 + 20 = 23 -- our results is reversed why?
                   Well, the results is flipped because we start building the
                   number starting from the last digit in our list. This comes from
                   the nature of the recursion.
            
        How about 3 numbers? [3, 2, 4]
            we get 3 + (f [2, 3] * 10 ) == 3 + (2 + (f [4] *10 )* 10)
        How about 4 numbers [3, 2, 4, 1]
            we get:
            3 + (2 + (4 + (f [1] * 10) * 10) * 10)

        Do you see a pattern now? 
        It didn't take long for me to figure out the pattern  
        but it took forever, even with perplexity ai to figure  
        out a formula for the pattern.

        and this is it:

        Results = next_results * 10 

        The simplicity of the formula make me feel even dumber now,  
        but I guess that's all part of the game init?

        BUT, but what is next_results? We won't have it in the first   
        iteration. When an input has more than 1 element, then our  
        next results is   
        f [rest of the list except the first element], where f is our function.

        So like 
        input: [1, 2, 3, 4]
        results = 1 + (f [2, 3, 4] * 10)

3. Convert The Math into Code

What does each part of the equation really mean in terms of code? how would it look like in haskell?


{-

    Results = next_results * 10
    is same as 
    Rn = Rn-1 * 10 + nth digit
        where Rn is the result of the nth element in the list.

-}

recFunc :: [Int] -> Int
recFunc [n]    = n 
recFunc [x, y] = (x * 10) + y
recFunc (x:y:ns) = (recFunc ns * 10) + x


-- R1 = x
-- Rn = Rn-1 * 10 + nth elem
-- what is Rn in the recFunc function? Rn: recFunc [Int]
-- RecFunc (n:ns) = n * 10 then add this results to head (ns);  
--then call RecFunc again on tail ns;
-- but what is in the middle before RecFun?
-- how do I do that recursive part in haskell syntax?

4. Understanding the Dark Humor in Building Back the Results

listToInt :: [Int] -> Int
listToInt [n]    = n 
listToInt (n:ns) = n + ((listToInt ns) * 10)

This is how the solution should be like.
    
    2 + ( (f [3, 4, 5])        * 10)
        3 + (f [4, 5]  * 10)
            4 + (f [5] * 10)
            4 + (5 * 10)
            4 + 50
        3 + (54         * 10)
        3 + (540)
        543
    2 + ( 543                  * 10)
    2 + (5430)
    5432

But if we try to keep everything from every level of the recursion, we get this:

2 +           (listToInt [3, 4, 5] * 10)
2 + (3 +      (listToInt [4, 5] * 10) * 10)
2 + (3 + (4 + (listToInt [5] * 10) * 10) * 10)
2 + (3 + (4 + (5 * 10) * 10) * 10) -- problem starts here
        if we didn't carry the 2 + (... and the *10s) along,
        this problem would not exists, why? because now we are forced to
        multiply 5 by 10 and again by 10 before we add 4 which is 
        wrong and the function definitely doesn't do that in reality when it runs.
        In reality what the function does is, do 5 * 10
        then adds the 4, then it will multiply by the next 10
        But because are pealing the parenthesis from the right,  
        we are forced by order of operations.
2 + (3 + (4 + 50 * 10) * 10) 
2 + (3 + (4 + 500) * 10)
2 + (3 + 5040)
= 2 + 5043
= 5035