tags:

views:

157

answers:

7

This is my function signature:

foo :: Integer -> [String]

How this function should work:

  1. foo 1234567 should return ["567", "234", "001"]
  2. foo 12345678 should return ["678", "345", "012"]
  3. foo 123456789 should return ["789", "456", "123"]

My current solution:

zeichenreihenBlock :: Integer -> [String]
zeichenreihenBlock x = reverse (partition (show x))

partition :: String -> [String]
partition [] = []
partition x
    | length x `mod` 3 == 2 = take 3 ("0" ++ x) : partition (drop 3 ("0" ++ x))   
    | length x `mod` 3 == 1 = take 3 ("00" ++ x) : partition (drop 3 ("00" ++ x))   
    | length x `mod` 3 == 0 = take 3 x : partition (drop 3 x)

Replace 'zeichenreihenBlock' with 'foo'. How would you implement this? Are there more efficient solutions?

Would really appreciate some new ideas.

Cheers

+2  A: 

You check the length way too often (an O(n) operation) when you could just fix up each case afterwards, so at a cost a a couple reverses:

import Data.List.Grouping(splitEvery)

foo :: Integer -> [String]
foo = map (reverse . fixIt) . splitEvery 3 . reverse . show
  where
  fixIt [a] = a:'0':'0':[]
  fixIt [a,b] = a:b:'0':[]
  fixIt lst = lst

Another way is to check the length of the list ONCE and add padding in the first function. This avoids the extra reverse for the cost of a single list traversal (note that isn't much savings). In go I just assume the list is length mod 3 (because it is) and always take 3.

import Data.List.Grouping

foo :: Integer -> [String]
foo   x | r == 2 = go ('0':s)
        | r == 1 = go ('0':'0':s)
        | otherwise = go s
  where
  r = l `rem` 3
  l = length s
  s = show x
  go = reverse . splitEvery 3

And not that it matters one bit what the performance is here (other code will dominate) but I like to hit things with Criterion for fun:

benchmarking doubleRev -- my first one
mean: 14.98601 us, lb 14.97309 us, ub 15.00181 us, ci 0.950

benchmarking singleRev -- my second one
mean: 13.64535 us, lb 13.62470 us, ub 13.69482 us, ci 0.950

benchmarking simpleNumeric -- this is sepp2k
mean: 23.03267 us, lb 23.01467 us, ub 23.05799 us, ci 0.950

benchmarking jetxee  -- jetxee beats all
mean: 10.55556 us, lb 10.54605 us, ub 10.56657 us, ci 0.950

benchmarking original
mean: 21.96451 us, lb 21.94825 us, ub 21.98329 us, ci 0.950

benchmarking luqui
mean: 17.21585 us, lb 17.19863 us, ub 17.25251 us, ci 0.950

-- benchmarked heinrich at a later time
-- His was ~ 20us

Also, this is a good opportunity to point out how your best guess about what is fastest often doesn't pan out (least, not for me). If you are wanting to optimize then profile and benchmark, don't guess.

TomMD
good point about padding first
jetxee
+1  A: 

Well, I think it would look nicer if you used more pattern-matching instead of those guards. You can match against specific list lengths like this:

partition :: String -> [String]
partition [] = ...
partition [x] = ...
partition [x,y] = ...
partition (x:y:z:rest) = ...

It might also work better if you reversed the string before splitting it up, checking the length like that isn't very elegant. That way you can take three digits at a time, put them back in proper order, then repeat. Worrying about length then only happens at the end, and can be done with pattern matching (as above).

camccann
He can't pattern match for the length of a list. Notice how he wants to chunk from the back of the list forward, so he must either reverse the list or find out if the list is of non-mod3 length and add some padding.
TomMD
@TomMD: That's why I suggested reversing the list, which makes more sense anyway. Since the final list of groupings is in reverse order and the grouping is independent of length if started from the back. Should have put that part first, maybe.
camccann
Right, sorry for the knee-jerk comment before reading carefully enough.
TomMD
@TomMD: No worries, even if it is [hard to imagine me making a silly mistake in an answer](http://stackoverflow.com/questions/3926681/counting-the-number-of-recursions/3926828#3926828).
camccann
+3  A: 

Pad first, split, reverse:

foo :: Integer -> [String]
foo = reverse . split3 . pad0

split3 [] = []
split3 xs = take 3 xs : split3 (drop 3 xs)

pad0 x = let s = show x in replicate ((- length s) `mod` 3) '0' ++ s

Test:

ghci> foo 1234567
["567","234","001"]
ghci> foo 12345678
["678","345","012"]
ghci> foo 123456789
["789","456","123"]
jetxee
+2  A: 

A simple solution using integer arithmetic:

padWithZeros n | n < 10 = "00" ++ show n 
               | n < 100 = '0' : show n
               | otherwise = show n

foo 0 = []
foo n = padWithZeros (n `mod` 1000) : foo (n `div` 1000)
sepp2k
+1 for the simplest solution so far, and probably most efficient as well.
identity
@identity I would agree, the code is simple but it doesn't clearly and immediately communicate to me that I'll end up with a list of strings of length 3 (which seems to be the important characteristic). Other solutions (jetxees) using simple recursion and/or function composition are clearer. Also, my benchmarks show this is the slowest solution even with -O2 and using `rem` instead of `mod` (totally to my surprise too).
TomMD
@TomMD: Fair enough, though I must say that I am totally surprised by how slow it is.
identity
+5  A: 

It's easier just to work with numbers to get the groups, not using strings at all.

digitGroups group 0 = []
digitGroups group n = r : digitGroups group q
    where (q,r) = n `divMod` (10^group)

-- > digitGroups 3 1234567
-- [567,234,1]

And then showing with padding becomes a separate problem:

pad char len str = replicate (len - length str) char ++ str

-- > pad '0' 3 "12"
-- "012"

They come together for the final solution:

foo = map (pad '0' 3 . show) . digitGroups 3

-- > foo 1234567
-- ["567","234","001"]
luqui
A: 

The other solutions are very nice, but the real solution is to use an infinite list for padding. ;-)

foo n = take count . map reverse . group 3 . (++ repeat '0') . reverse $ digits
    where
    digits = show n
    count  = (length digits - 1) `div` 3 + 1
    group k xs = take k xs : group k (drop k xs)
Heinrich Apfelmus
But that is basically no faster than the original (I'm assuming computation time is what the poster ment by "more efficient") and it gives incorrect results.
TomMD
Oops, fixed the incorrect results. Concerning performance, I think it's unlikely that this function will be a bottleneck, so I'm fine with a slow variant.
Heinrich Apfelmus
A: 

Thank you everybody for your help. Because I'm a Haskell newbie your solutions really help me to improve my Haskell skills.

Claus Polanka