Problem understanding treesort in Haskell

Question

I am trying to figure out how exactly does treesort from here work (I understand flatten, insert and foldr).

I suppose what's being done in treesort is applying insert for each element on the list thus generating a tree and then flattening it. The only problem I can't overcome here is where the list (that is the argument of the function) is hiding (because it is not written anywhere as an argument except for the function type declaration).

One more thing: since dot operator is function composition, why is it an error when I change: treesort = flatten . foldr insert Leaf to treesort = flatten( foldr insert Leaf )?

Answer 1

To answer your last question first, you're getting an error because . is a function composition operator that takes two functions (in this case flatten and foldr insert Leaf). If you want to rewrite the code without the use of ., you'll need to create a function that takes some parameter:

-- // Pass the 'list' to the first function and the 
-- // result of the call to the second function
treesort list = flatten (foldr insert Leaf list)

This also explains where the list parameter was hiding. When composing functions, you don't need to write parameters explicitly, because the result of the expression f . g is a function that takes some parameter, calls g and then calls f:

-- // function composition..
composed = f . g
-- // ..is equivalent to declaring a function:
composed x = f (g x)

Answer 2

what's being done in treesort is applying insert for each element on the list thus generating a tree and then flattening it.

Exactly right.

[Where is the list hiding?]

In a functional language, you don't have to give the arguments of a value of function type. For example if I write

f = concat . map (map toUpper) 

I get a function of type [[Char]] -> [Char]. This function expects an argument even though there's no argument in the defining equation. It's exactly the same as if I had written

f strings = (concat . map (map toUpper)) strings

Since the dot operator is function composition, why is it wrong to change f . g to f (g)?

They don't mean the same thing. What happens when each is applied to x?

(f . g) x  = f (g x)

(f (g)) x  = (f g) x

You can see the applications associate differently, and f. g is different from f g.

It's a type error because foldr insert Leaf is a function from lists to trees, and flatten is meant to be applied to a single tree, not to a function.

Answer 3

Sometimes, as long as you are not familiar with the pointless style, it is useful to do epsilon-conversion mentally.

If f is an expression with function type, then one can convert it to \e -> (f) e

And, if we have a definition like

a = \e -> (f) e

we can always safely rewrite it as

a e = (f) e

Thus

treesort = flatten . foldr insert Leaf 

is the same as

treesort list = (flatten . foldr insert Leaf) list