Repeat a string: Difference between revisions

As the number of repetitions increases, however, it may become more efficient to repeat by progressive duplication (mappend to self), mappending to an accumulator only where required for binary composition of the target length. (i.e. Rhind Papyrus 'Egyptian' or 'Ethiopian' multiplication):

<lang haskell>import Data.Tuple (swap)

import Data.List (unfoldr)

import Control.Monad (join)

-- ETHIOPIAN MULTIPLICATION ---------------------------------------------------

repString :: Int -> String -> String

repString n m =

foldr

(\(d, x) a ->

if d > 0 -- Is this power of 2 needed for the binary composition ?

then mappend a x

else a)

"" $

zip

(unfoldr

(\h ->

if h > 0

then Just $ swap (quotRem h 2)

else Nothing)

n)

(iterate (join mappend) m) -- Iterative duplication ( mappend to self )

-- TEST -----------------------------------------------------------------------

main :: IO ()

main = print $ repString 50000 "ha"</lang>