[Haskell-cafe] Suggestions for improvement

Richard O'Keefe ok at cs.otago.ac.nz
Mon Oct 4 16:21:51 EDT 2010


On 4/10/2010, at 8:52 AM, N. Raghavendra wrote:

> I am reading the book `The Haskell Road to Math, Logic, ...".  One of
> the exercises in the first chapter asks for a function that maps a
> string "abcd" to "abbcccdddd" and "bang!" to "baannngggg!!!!!".

answer s = concat $ zipWith replicate [1..] s

I looked at the examples and said, "hmm, elements are being repeated
varying numbers of times".  Looked up "repeat", found that that was
the wrong function, and saw "replicate", which is the right one:
	replicate n x = [x ..... x] with n copies of x
So zipWith [1..] "abcd" is ["a", "bb", "ccc", "dddd"]
and pasting those together is just what concat does.

Had replicate, zipWith, concat not already been provided, I might
have done one of two things.
(a) Write them.

	concat (x:xs) = x ++ concat xs
	concat []     = []

	zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys
	zipWith _   _      _    = []

	replicate (n+1) x = x : replicate n x
	replicate 0     _ = []

    This is _still_ less code than the code I'm replying to, and
    gives you some reusable components as well.

(b) I'd have generalised the function to

	f n [x1,...,xk] = [x1 n times, x2 n+1 times, ..., xk n+k-1 times]

    in order to get a clean recursion for f.

	answer s = f 1 s
	  where f _ []     = []                 -- list iteration
	        f n (x:xs) = g n (f (n+1) xs)
	          where g (n+1) s = x : g n s   -- element replication
	                g   0   s = s

    You can think of this by imagining the answer laid out in a triangle
        "abcd
          bcd
           cd
            d"



More information about the Haskell-Cafe mailing list