[Haskell-beginners] questions on evaluation.

[Peter McIlroy]

Fabian,

For your problem of bang ->  baanngggg
You can derive Rein's hairy idiom from a more straightforward technique for
getting a recursive definition:

First get a basic implementation using ++ and recursion:

* add a helper function with any "state variables" as arguments.
* Ignore concatenation while thinking about a problem.
* Use pattern matching for recursion step.

This gives the basic (naïve) implementation:

blowup :: [a] -> [a]
blowup x = concat (blowup' 1 x)

-- returns (e.g.) ["b", "aa", "nnn", "gggg" ]
blowup' a b :: Integer a => a -> [b] -> [[b]]
blowup' n (x:xs)  = (replicate n x : blowup' n+1 xs)
blowup' _ _ = [] -- base case

You can distribute concatenation into blowup', to get recursion over
concatenation, but this really is going the wrong direction:

blowup' n (x:xs)  = (replicate n x) ++ (blowup' n+1 xs)
blowup' _ _ = []

Instead, derive Rein's hairy-looking version by (as always) ignoring
concatenation and replacing the state variable in blowup' with zip or
zipWith.
observe:
> zip [1..] "bang"
[(1,'b'),(2,'a'),(3,'n'),(4,'g')]

So blowup' n x becomes blowup' x:
  blowup x = concat (blowup' x)

  blowup' x  = map (\(a,b) replicate a b) zip [1..] x
==> definition of zipWith
 blowup' x = zipWith replicate [1..] x
==>
blowup x = concat (zipWith replicate [1..] x)

You can always push concat down into a function by unwrapping it with join,
getting a more efficient version that creates the result directly.

  blowup x = concat (zipWith replicate [1..] x)
==>
  blowup x = (join . zipWith replicate [1..] ) x
==>
  blowup = join . zipWith replicate [1..]
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20160111/9a43daac/attachment.html>