• Create Account

### #ActualSamLowry

Posted 30 April 2013 - 03:12 PM

While your code is certainly correct and written in functional style, I would suggest you try to go one step further. Now, it seems that you are 'inlining' different steps into one big step. Functional programming has the advantage of giving the programmer the possibility to clearly distinguish between different 'levels' of operation, each following a certain pattern.

For example, let's say I have a list of numbers and want to take the sum of the squares of all uneven numbers. The following Haskell-code (I picked Haskell because even if you are not familiar with it, I believe it is more readable than Scheme, as long as I stay away from some of the more arcane notations) does this in a straightforward manner:

bizarreSum :: [Integer] -> Integer
----------------------------------
bizarreSum []     = 0                            -- empty list case
bizarreSum (x:xs)                                -- cons case (head = x, tail = xs)
| odd x       = x * x + bizarreSum xs        --    head is odd
| otherwise   = bizarreSum xs

But one can distinguish three different steps in this algorithm: first, we filter out the even numbers, then we square every number, and finally, we summate. This can be written as

bizarreSum' :: [Integer] -> Integer
-----------------------------------
bizarreSum' = foldl (+) 0 . map sqr . filter odd

The dot chains the operations together: filtering, mapping, folding. Filter, map and foldl are three well-known patterns, they are in a way higher-level functional loops. In my opinion, it is preferable to try to find these patterns and try to implement your algorithms using them, as you work on a higher level of abstraction.

Permutation can then be implemented as a series of mapping operations. My Haskell implementation looks like this:

split :: [a] -> [([a], a, [a])]
-------------------------------
split xs = [ (take n xs, xs !! n, drop (n+1) xs)
| n <- [ 0 .. length xs - 1 ] ]

permutations :: [a] -> [[a]]
----------------------------
permutations [] = [[]]
permutations xs = do (prefix, x, postfix) <- split xs
p <- permutations (prefix ++ postfix)
return (x : p)

The permutations function first splits a list [a(1), a(2), ..., a(n)] up in three parts: a prefix list [a(1)..a(i-1)], an element x=a(i), and a postfix list [a(i+1)..a(n)], for every possible i (this is a map). Then for all permutations p of prefix++postfix (again a map) it prepends x=a(i) to the front of p. So, this is akin to a nested loop, or in our case, a map within a map. In above Haskell code, you can interpret "x <- xs" as "for each x in xs" (it uses monads, which are  a very powerful concept, and I love to explain people about them, but now it is a bit out of scope of this post).

In your first attempt, insert-everywhere/in-all-words seems to be wrong:

(insert-everywhere/in-all-words 1 '((2 3)))
'((1 2 3) (1 3 2) (2 1 3) (3 2 1) (3 1 2) (2 3 1))

I don't think it is supposed to generate all permutations of (2 3) in this example. I didn't take the time to inspect your code thoroughly, but I did notice a lot of conds and recursion, which means that you are constantly reimplementing functional building blocks, map in your case.

Final note: it is true that bizarreSum' is less memory-efficient than bizarreSum, as each time a new list must be created in memory (however, this does not apply to Haskell as it is a nonstrict language, but in most other languages, this could be an actual issue). However, would performing your own inlining not be a case of premature optimisation? If it is your intention to practice functional programming, I believe it is more important to focus on learning to think on a higher level than to be efficient.

### #1SamLowry

Posted 30 April 2013 - 01:02 PM

While your code is certainly correct and written in functional style, I would suggest you try to go one step further. Now, it seems that you are 'inlining' different steps into one big step. Functional programming has the advantage of giving the programmer the possibility to clearly distinguish between different 'levels' of operation, each following a certain pattern.

For example, let's say I have a list of numbers and want to take the sum of the squares of all uneven numbers. The following Haskell-code (I picked Haskell because even if you are not familiar with it, I believe it is more readable than Scheme, as long as I stay away from some of the more arcane notations) does this in a straightforward manner:

bizarreSum :: [Integer] -> Integer
----------------------------------
bizarreSum []     = 0                            -- empty list case
bizarreSum (x:xs)                                -- cons case (head = x, tail = xs)
| odd x       = x * x + bizarreSum xs        --    head is odd
| otherwise   = bizarreSum xs

But one can distinguish three different steps in this algorithm: first, we filter out the even numbers, then we square every number, and finally, we summate. This can be written as

bizarreSum' :: [Integer] -> Integer
-----------------------------------
bizarreSum' = foldl (+) 0 . map sqr . filter odd

The dot chains the operations together: filtering, mapping, folding. Filter, map and foldl are three well-known patterns, they are in a way higher-level functional loops. In my opinion, it is preferable to try to find these patterns and try to implement your algorithms using them, as you work on a higher level of abstraction.

Permutation can then be implemented as a series of mapping operations. My Haskell implementation looks like this:

split :: [a] -> [([a], a, [a])]
-------------------------------
split xs = [ (take n xs, xs !! n, drop (n+1) xs)
| n <- [ 0 .. length xs - 1 ] ]

permutations :: [a] -> [[a]]
----------------------------
permutations [] = [[]]
permutations xs = do (prefix, x, postfix) <- split xs
p <- permutations (prefix ++ postfix)
return (x : p)

The permutations function first splits a list [a(1), a(2), ..., a(n)] up in three parts: a prefix list [a(1)..a(i-1)], an element x=a(i), and a postfix list [a(i+1)..a(n)], for every possible i (this is a map). Then for all permutations p of prefix++postfix (again a map) it prepends x=a(i) to the front of p. So, this is akin to a nested loop, or in our case, a map within a map. In above Haskell code, you can interpret "x <- xs" as "for each x in xs" (it uses monads, which are  a very powerful concept, and I love to explain people about them, but now it is a bit out of scope of this post).

In your first attempt, insert-everywhere/in-all-words seems to be wrong:

(insert-everywhere/in-all-words 1 '((2 3)))
'((1 2 3) (1 3 2) (2 1 3) (3 2 1) (3 1 2) (2 3 1))

I don't think it is supposed to generate all permutations of (2 3) in this example. I didn't take the time to inspect your code thorougly, but I did notice a lot of conds and recursion, which means that you are constantly reimplementing functional building blocks, map in your case.

Final note: it is true that bizarreSum' is less memory-efficient than bizarreSum, as each time a new list must be created in memory (however, this does not apply to Haskell as it is a nonstrict language, but in most other languages, this could be an actual issue). However, would performing your own inlining not be a case of premature optimisation? If it is your intention to practice functional programming, I believe it is more important to focus on learning to think on a higher level than to be efficient.

PARTNERS