Reverse function behavior in Haskell-CodePudding

digits :: Int -> [Int]
digits n  = reverse (x)
    where x  
            | n < 10 = [n]
            | otherwise = (mod n 10) : (digits (div n 10))

*ghci> digits 1234 = [3,1,2,4]*

digits' :: Int -> [Int]
digits' n  =  (x)
    where x  
            | n < 10 = [n]
            | otherwise = (mod n 10) : (digits' (div n 10))

*ghci>digits' 1234 = [4,3,2,1]*

As per my understanding the evaluation of digits 1234 should be [1,2,3,4]. But it seems that I am missing something. Can anyone explain this?

CodePudding user response：

The problem is that digits reverses the string in each recursive call, not just once at the outer level. Try digits x = reverse (digits' x) (or, equivalently, digits = reverse . digits'), and see if you can explain the difference.

CodePudding user response：

Notwithstanding the excellent answer by amalloy, here is a way of getting the digits in the expected order without involving the reverse library function.

We use the common trick of accumulating the result in some extra argument of the recursive call, (the “accumulator”) noted here as dgs.

We also use the divMod library function, which returns a pair containing both the quotient and the remainder.

digits :: Int -> [Int]
digits n = go [] n
  where
    base      =  10
    go dgs k  =  if (k < base)  then  (k:dgs)
                                else  let  (q,r) = divMod k base
                                      in   go (r:dgs) q

The accumulator grows by successive prepending operations, in such a way that the digits end up in the appropriate order.