[Haskell-beginners] questions on evaluation.

Rein Henrichs rein.henrichs at gmail.com
Tue Jan 12 00:11:28 UTC 2016


And really, I should have used concat instead of join there.

On Mon, Jan 11, 2016 at 4:10 PM Rein Henrichs <rein.henrichs at gmail.com>
wrote:

>  (blowup' n+1 xs) should be  (blowup' (n+1) xs) but otherwise this is spot
> on.
>
> On Mon, Jan 11, 2016 at 3:18 PM Peter McIlroy <pmcilroy at gmail.com> wrote:
>
>>
>> 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..]
>> _______________________________________________
>> Beginners mailing list
>> Beginners at haskell.org
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20160112/6fb28759/attachment-0001.html>


More information about the Beginners mailing list