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..]
(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@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@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
And really, I should have used concat instead of join there. On Mon, Jan 11, 2016 at 4:10 PM Rein Henrichs <rein.henrichs@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@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@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
On 12/01/2016 00:18, Peter McIlroy 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.
Thanks for the hint Peter -- Fabien
participants (3)
-
Fabien R -
Peter McIlroy -
Rein Henrichs