Re: [Haskell-cafe] recursion problem part 2

6 Feb 2015

      Jeff,
An expression of the form xs ++ [x] appends the element to the end of the
list. In order to evaluate the result, the ++ function iterates through the
elements of the first list to find the end of the list then sets the tail
of the last element of the first list to the second list. This means that
on each recursive call (once per digit), your algorithm must traverse the
list of digits already produced to attach the newest element. You can avoid
this problem by instead consing the new digit onto the front of the list,
and then reverse the list at the end to produce the digits in the correct
order. Alternatively, you could try and compute the digits in the reverse
order.

Here's another solution, though it also will only work on positive integers
and will fail on negative inputs:

    import Data.Char (digitToInt)

    lastDigit :: Int -> [Int]
    lastDigit x = map digitToInt (show x)

You can fix the issues with this implementation by replacing digitToInt
with a wrapper that checks if the character being analyzed is in fact a
digit and then providing something if it is not. What you should provide in
the failure case is up to the requirements of the problem.

Thanks,
Arjun

On Fri, Feb 6, 2015 at 8:01 PM, Jeffrey Brown 
wrote:
...
Is it successively appending? My intention was to prepend. If it's
appending, Is that because the ++ operator always evaluates its left
argument first, then its right one?
On Fri, Feb 6, 2015 at 2:42 PM, David Feuer  wrote:
...
On Feb 6, 2015 3:41 PM, "Jeffrey Brown"  wrote:
...
Here's a solution:
lastDigit x = mod x 10
remainingDigits x = (x - lastDigit x) `div` 10
listDigits x
  | x < 10 = [x]
  | otherwise = (listDigits $ remainingDigits x) ++ [lastDigit x]
Here's a faster one:
listDigits2 x
  | x < 10 = [x]
  | otherwise = (listDigits $ remainingDigits) ++ [lastDigit]
  where lastDigit = mod x 10
        remainingDigits = (x - lastDigit) `div` 10
These give somewhat peculiar results when the argument is negative. That
can be rectified, of course. Unfortunately, all of these proposed solutions
have a serious performance problem: successively appending single elements
to build a list of length n is O(n^2). There's an easy fix, which I'll let
you come up with.
David
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] recursion problem part 2

Arjun Comar