How to read blocks of 3 elements from a list beginning at the end of the list?

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 th开发者_运维百科ere more efficient solutions?

Would really appreciate some new ideas.

Cheers

---

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"]

---

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"]

---

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)

---

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.

---

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).

---

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)