<div dir="ltr">And really, I should have used concat instead of join there.</div><br><div class="gmail_quote"><div dir="ltr">On Mon, Jan 11, 2016 at 4:10 PM Rein Henrichs <<a href="mailto:rein.henrichs@gmail.com">rein.henrichs@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"> (blowup' n+1 xs) should be  (blowup' (n+1) xs) but otherwise this is spot on.<br></div><br><div class="gmail_quote"><div dir="ltr">On Mon, Jan 11, 2016 at 3:18 PM Peter McIlroy <<a href="mailto:pmcilroy@gmail.com" target="_blank">pmcilroy@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><br></div><div>Fabian,<br><br>For your problem of bang ->  baanngggg<br>You can derive Rein's hairy idiom from a more straightforward technique for getting a recursive definition:<br><br>First get a basic implementation using ++ and recursion:<br><br>* add a helper function with any "state variables" as arguments.<br>* Ignore concatenation while thinking about a problem.<br>* Use pattern matching for recursion step.<br><br>This gives the basic (naïve) implementation:<br><br>blowup :: [a] -> [a]<br>blowup x = concat (blowup' 1 x)<br><br>-- returns (e.g.) ["b", "aa", "nnn", "gggg" ]<br>blowup' a b :: Integer a => a -> [b] -> [[b]]<br>blowup' n (x:xs)  = (replicate n x : blowup' n+1 xs)<br>blowup' _ _ = [] -- base case<br><br>You can distribute concatenation into blowup', to get recursion over concatenation, but this really is going the wrong direction:</div><div><br>blowup' n (x:xs)  = (replicate n x) ++ (blowup' n+1 xs)<br>blowup' _ _ = []<br></div><div><br></div><div>Instead, derive Rein's hairy-looking version by (as always) ignoring concatenation and replacing the state variable in blowup' with zip or zipWith.<br>observe:<br>> zip [1..] "bang"<br>[(1,'b'),(2,'a'),(3,'n'),(4,'g')]<br></div><div><br></div><div>So blowup' n x becomes blowup' x:<br>  blowup x = concat (blowup' x)</div><div><br>  blowup' x  = map (\(a,b) replicate a b) zip [1..] x<br>==> definition of zipWith</div><div> blowup' x = zipWith replicate [1..] x</div><div>==></div><div>blowup x = concat (zipWith replicate [1..] x)</div><div><br></div><div>You can always push concat down into a function by unwrapping it with join, getting a more efficient version that creates the result directly.</div><div><br></div><div>  blowup x = concat (zipWith replicate [1..] x)</div><div>==></div><div>  blowup x = (join . zipWith replicate [1..] ) x</div><div>==></div><div>  blowup = join . zipWith replicate [1..]</div></div>
_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a><br>
</blockquote></div></blockquote></div>