### Improvements

Chaddaï Fouché kindly responded to a query I put out on the haskell-beginners mailing list, suggesting:

Give it a function

So, for example, rather than

we can write

and instead of

we can write

Not shabby, eh?

About those

So I added

and changed a little bit of code:

and indeed it helped. I hope it will help more soon; I can't have an unboxed vector of

A bigger payoff, for now, had to do with sorting, or the minimizing thereof. It's easy to make oneTwos come out in order; noTwos is the gotcha. We did the folliowing:

and poof! The profiler output shows total time as 174 ticks, 0.17 seconds. The best

No reduction in the percentage of time used for garbage collection, though.

You know... now it may be worth keeping palindromes rather than combinations, because we would only have to sort them once instead of twice--and that might cut the memory usage as well.

- using
**iterate** - using
**Data.Vector**or**MemoTrie**instead of lists where possible

**iterate**, you ask?**iterate :: (a -> a) -> a -> [a]**Give it a function

**f**and a starting value**s**and it will hand you back**[s, f s, f . f s, f . f . f s, ...]**So, for example, rather than

**powersOfTen = map (10 ^) [0..]**we can write

**powersOfTen = iterate (10 *) 1**and instead of

**bigTwos = map (2 ^) powersOfTwo**we can write

**square n = n * n**

bigTwos = iterate square 2bigTwos = iterate square 2

Not shabby, eh?

About those

**Vector**s: they're a data structure that makes for O(1) (i.e. constant time) indexing, as opposed to the O(n) time for lists. There are two flavors:**Data.Vector**and**Data.Vector.Unboxed**. The unboxed version has lower overhead, but can't be used on all types.So I added

**import qualified Data.Vector as V**and changed a little bit of code:

**memoPair = V.generate halfN (\i -> tenToThe i + tenToThe (n - 1 - i))**

pair i = memoPair V.! i

pairSum v = V.foldl' (+) shell (V.map pair v)pair i = memoPair V.! i

pairSum v = V.foldl' (+) shell (V.map pair v)

**choices :: Int -> Int-> [V.Vector Int]**

m `choices` n

| n == 0 = [V.empty]

| m == n = [V.enumFromStepN m (-1) m]

| otherwise = [m `V.cons` c | c <- (m - 1) `choices` (n - 1)]

++ ((m - 1) `choices` n)m `choices` n

| n == 0 = [V.empty]

| m == n = [V.enumFromStepN m (-1) m]

| otherwise = [m `V.cons` c | c <- (m - 1) `choices` (n - 1)]

++ ((m - 1) `choices` n)

and indeed it helped. I hope it will help more soon; I can't have an unboxed vector of

**Integer**s (or is that a vector of unboxed**Integer**s?), so if I want the**choices****Int**s unboxed, I can't use the unboxed vector**map**; I'll have to roll my own function for that.A bigger payoff, for now, had to do with sorting, or the minimizing thereof. It's easy to make oneTwos come out in order; noTwos is the gotcha. We did the folliowing:

**nDigitYs n = (merge (oneTwos n) (noTwos n)) ++ twoTwos n**

where twoTwos n

| even n = [twoShell]

| otherwise = [twoShell, twoShell + tenToThe halfN]

where twoShell = 2 * shell

oneTwos n

| even n = []

| otherwise = map (+ (shell + 2 * tenToThe halfN))

(0 : map pair [halfN - 1,halfN - 2..1])

noTwos n

| even n = base

| otherwise = merge base [p + tenToThe halfN | p <- base]

where base = sort $ map pairSum (noTwosChoices !! (halfN - 1))where twoTwos n

| even n = [twoShell]

| otherwise = [twoShell, twoShell + tenToThe halfN]

where twoShell = 2 * shell

oneTwos n

| even n = []

| otherwise = map (+ (shell + 2 * tenToThe halfN))

(0 : map pair [halfN - 1,halfN - 2..1])

noTwos n

| even n = base

| otherwise = merge base [p + tenToThe halfN | p <- base]

where base = sort $ map pairSum (noTwosChoices !! (halfN - 1))

and poof! The profiler output shows total time as 174 ticks, 0.17 seconds. The best

**time**output is now**real 0m0.214s****user 0m0.176s****sys 0m0.028s**No reduction in the percentage of time used for garbage collection, though.

You know... now it may be worth keeping palindromes rather than combinations, because we would only have to sort them once instead of twice--and that might cut the memory usage as well.

## Comments