[Haskell-cafe] recursion problem part 2
Jeffrey Brown
jeffbrown.the at gmail.com
Sat Feb 7 01:01:34 UTC 2015
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 <david.feuer at gmail.com> wrote:
>
> 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/1871090d/attachment.html>
More information about the Haskell-Cafe
mailing list