List to Integer in Haskell

2025-02-14 ~/algorithms haskell functional-programming algorithms problem-solving
List to Integer in Haskell

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 3: 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:

  1. Direct explicit recursion
  2. Using foldr
  3. Tail Recursion
  4. Using foldl
  5. List comprehension

Understanding the Problem

Trust me, this is NOT a mathematical rabbit hole about the nature of numbers. I am not that guy. It's much simpler.

There are just 3 parts to this problem:

  1. How decimal numbers (base) are built
  2. An equation to abstract the idea
  3. 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 base 10 integers.

Each number's value is communicated by its 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 has 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 makes 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 exist, 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 we are peeling 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
= 5045

not good. will come back and finish this