Reverse function behavior in Haskell

user_18541946 0
Viewed 87
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?

ghci reverse where-clause haskell
2 Answers

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.

user_6254030

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.

user_112824040
Related