[Haskell-cafe] recursion problem part 2

[David Feuer]

On Feb 6, 2015 3:41 PM, "Jeffrey Brown" <jeffbrown.the at gmail.com> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20150206/dd98547c/attachment.html>