string concatenation order in fold function

user_9724339 0
Viewed 250

I'm trying to understand the following problem : I've defined a list and i'm using fold function on this list for concatenating these strings.

with foldr

food = ["Pizza", "Apple", "Banana"]
let f = (\a b -> take 3 a ++ b)
foldr f "" food
-- result
"PizAppBan"

whilst with the foldl

food = ["Pizza", "Apple", "Banana"]
    let f = (\a b -> take 3 a ++ b)
    foldr f "" food
    -- result
    "BanAppPiz"

So i understood that the order change because, wherease we are doing some commutative operation the order does not important...for string concatenation instead is. so the question is how in fold left the string concatenation is evaluated and how i can visualize conceptually the operation order?because if i take step by step the following operation, the process would result always the same...

ps. I've seen that there is just some qestions about that but they not seem much clear regarding how the process work.

haskell
1 Answers

The order of the parameters of the folding function are "flipped". Indeed, if we look at the defintions for foldl and foldr we see:

foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

Here in both definitions the "accumulator" has a type b. But as you can see, in the foldl function, the fold function has type b -> a -> b, so the first parameter is the accumulator, the second the element, and it returns a new value for the accumulator. This to illustrate that the folding goes left-to-right.

For the foldr function the fold function has type a -> b -> b, so first it takes an element, next it takes the value for the accumulator after folding the rest of the list, and you should return the new value for the accumulator. It thus folds right-to-left.

If you want to let this work for foldl, you thus take \b a -> … with b the accumulator. In that case you return b ++ take a 3, so we append the first three characters of a at the right end of the accumulator:

Prelude> foldr (\a b -> take 3 a ++ b) "" ["Pizza", "Apple", "Banana"]
"PizAppBan"
Prelude> foldl (\b a -> b ++ take 3 a) "" ["Pizza", "Apple", "Banana"]
"PizAppBan"

Flipping the parameters is thus not enough. Evaluation is done from left-to-right in case of foldl and right-to-left in case of foldr, this thus means that you also need to swap the way you concatenate.

The foldl variant will however be less efficient here, since the (++) :: [a] -> [a] -> [a] function takes time linear in the length of the first operand.

The function \a b -> take 3 a ++ b, is not commutative, nor is it associative. Indeed, commutative means that f x y is equal to f y x for each x and y. But if we call f "foobar" "qux" we retrieve:

Prelude> f "foobar" "qux"
"fooqux"
Prelude> f "qux" "foobar"
"quxfoobar"

The concat operation (++) is not commutative either.

Furthermore the opperation is not associative either, because of the take 3 part. Indeed, an associative operation means that f x (f y z) is equal to f (f x y) z for each x, y and z. But we see:

Prelude> f (f "foo" "bar") "qux"
"fooqux"
Prelude> f "foo" (f "bar" "qux")
"foobarqux"

If you however first perform a map to take the first three characters of each string, then indeed the order does not matter:

Prelude> foldl (++) "" (map (take 3) food)
"PizAppBan"
Prelude> foldr (++) "" (map (take 3) food)
"PizAppBan"

The take 3 part thus makes the function non-associative, and therefore you can not use it in both foldl and foldr without adapting it properly.

user_675790
Related