Reverse List Using Map/reduce

I am learning concepts of functional programming and trying out problem exercises. An exercise, Reverse a list using map/reduce. My solution: lists = [ 1, 2, 3, 5 ,6] def tree_r

Solution 1:

At first, i don't know Python good enough, but as you marked the question as "functional-programming" and you stated you want to learn in general about functional programming i want to give some general explanation of your problem. At first, you should rethink what the map and reduce operation do and what they expect. Let's start with the map function.

A map function for a list (in functional programming you don't have only one map, you have one map for every generic type) executes a function on every single argument. That function can operate on that single argument and transform it. The result of this transformation is turned into a new list. One important note is that the function you pass to map only ever sees one element, so you cannot use map itself to transform a list as a whole. You only can transform every single element of a list. But changing the order needs the idea of having at least two elements of a list, and a map only ever gets a single element. This is the reason why the reverse logic cannot be in map and has to be part of the reduce operation.

The reduce function on the other hand expects a function that takes two things of the same type, and returns a single item of the same type. For example the reduce function could take the "+" function. "+" is a function that takes two int and returns a new int. The signature is basically int + int = int. The essence of reduce is to take two things and turn it into a single new item. If you for example had something more complex like a class "Foo", then the function you have to provide to reduce need to have the signature Foo * Foo -> Foo. Meaning take a Foo as first and second argument, and return a single new Foo.

It is also important to note how reduce will work with that function. Let's assume you have the List [1,2,3,4,5] on top let's assume you have an accumulator function that takes two int that just adds them together. What you can think of what will happen is the following.

1. The reduce function takes the first two arguments of your list (1 and 2 in this case)
2. Passes those to the accumulator function (1 + 2 = 3)
3. And replaces the two arguments in the list with the result. [3,3,4,5]
4. Go back to 1) and repeat that process until your List only have a single item
5. Return that single item

So what you can imagine what happens is the following

[1,2,3,4,5] -> 1 + 2 = 3
[3,3,4,5]   -> 3 + 3 = 6
[6,4,5]     -> 6 + 4 = 10
[10,5]      -> 10 + 5 = 15
[15]        -> Return just "15". Not a "[15]"

Actually the process internal usually works a little bit different. But this is the process you can imagine what happens. It is important to note that you never modify a list. You always create new lists in that process. Another important note. At the end of the reduce function you have a list of an single item. But the reduce function does not return the whole list. It returns just the single element. So you get 15 an int as a result. You don't get a list with a single item containing 15. Reduce will just return that single element. Whatever it is. One other way to think about it. You always get exactly the type back of your accumulator function. If you pass a accumulator function that takes two int adds them and returns a new int. Your reduce function will also return an int. If you pass an accumulator function that takes two Foo classes and returns a new Foo. Your reduce function will also return a Foo as its result. The return type of reduce is always the same as the types of your accumulator function.

Now let's take all those pieces and put them together. The goal is to reverse a list. The first important thing is. Your result type will be a list. That also means that the function you pass into reduce also have to return a list. But as the input are always the same as the output. You now have to provide a accumulator function that takes two lists, and returns a single new list.

But now let's step back. What happens if you use your list "[1,2,3,4,5]" directly as the input to reduce? The short answer is, it will not work. reduce will take two argument of your list. But what you have is a list of int. But your accumulator function expects two lists not two int. To solve that problem, what you now can do is try to convert every single element of the list into its own list. So how do we transform every single element of a list? Right! With map! So what you have to do is the following. You first map your list into a list of lists.

[1,2,3,4,5] -> [[1],[2],[3],[4],[5]]

Now your reduce function gets the first two elements of your first list. It means you now have an accumulator function that gets [1] and [2] as its argument. Two separate lists. But your accumulator function has to return a single new list. If unclear, just remind what the accumulator function takes and return.

int, int    -> intfloat,float -> float
Foo,Foo     -> Foo
list,list   -> list

So what you now have to do is to combine those two lists into a single new list. Or in other words you have to append/concat those two lists. I don't knew exactly how you concat two lists in Python let's assume here the operation would be "++". So if you concat just the first argument and the second argument, you will not get what you want.

[[1],[2],[3],[4],[5]] -> [1]       ++ [2] = [1,2]
[[1,2],[3],[4],[5]]   -> [1,2]     ++ [3] = [1,2,3]
[[1,2,3],[4],[5]]     -> [1,2,3]   ++ [4] = [1,2,3,4]
[[1,2,3,4],[5]]       -> [1,2,3,4] ++ [5] = [1,2,3,4,5]
[[1,2,3,4,5]]         -> Return first element [1,2,3,4,5]

So what you have to do is to concat the second argument with the first one.

[[1],[2],[3],[4],[5]] -> [2] ++ [1]       = [2,1]
[[2,1],[3],[4],[5]]   -> [3] ++ [2,1]     = [3,2,1]
[[3,2,1],[4],[5]]     -> [4] ++ [3,2,1]   = [4,3,2,1]
[[4,3,2,1],[5]]       -> [5] ++ [4,3,2,1] = [5,4,3,2,1]
[[5,4,3,2,1]]         -> Return first element [5,4,3,2,1]

And now what you get is your reversed list. So what you have todo

1. map every element to a list. So you get a list of list
2. use reduce to concat every list of list into a new list in reversed order.

For example, in F# the whole code would look like this.

let list = [1;2;3;4;5]

let reversed =
    list
    |> List.map    (fun x -> [x]) // map every element to a list
    |> List.reduce (fun xs ys -> List.append ys xs) // Note ys ++ xs - reversed order for appending

printfn "%A" reversed
// prints: [5;4;3;2;1]

I think you should be able to translate this to Python. As a further notice. Doing "map" and then a "concat" operation (without reversing) is also named "bind" in functional programming.

Solution 2:

Your reduce operation is appending a None to the end of the list a because a.insert(0,x) will return None.

So you are modifying the list a in-place, but appending a None value at the same time.

If you rewrite your reduce operation to use a for loop, it'd look like:

def reverse_list(lists):
    r = []
    for x in lists:
        val = r.insert(0,x)
        r = r + [val]  # val (the return value of r.insert) is None
    return r

Solution 3:

In case of nested list. I am posting answer for reference.

lists = [ 1 ,2 ,3 , [5,6,7], 8, [9, 0, 1 ,4 ]]

deftree_reverse(lists):
    return  reduce(lambda a, x: ( map(tree_reverse, [x]) ifisinstance(x,list) else [x] ) + a  , lists , [] )

print tree_reverse(lists) 

Output :

[[4, 1, 0, 9], 8, [7, 6, 5], 3, 2, 1]

Solution 4:

Functional programming languages will often use recursion to implement iteration.

A recursive tree_reverse function might look like

deftree_reverse(lists):
    return tree_reverse(lists[1:]) + [lists[0]] if lists else []

If you look at Haskell it might be implemented like this

reverse' :: [a] -> [a]  
reverse' [] = []  
reverse' (x:xs) = reverse' xs ++ [x]

Where the x is the head of the list (first element) and xs is the tail (the list minus the head) and you can see that reverse' is called recursively with those elements reversed and the reversed list is built up iteratively.