The problem of understanding trees in Haskell
I'm trying to figure out exactly how the tree s work here (I understand flatten, insert and collapse).
I suppose what is being done in treeort is applying insertion to every item in the list , thus creating a tree and then flattening it. The only problem I cannot get over is where the list (i.e. the function argument) is hidden (because it is not written anywhere as an argument other than the function type declaration).
One more thing: since the dot operator is part of the function, why is it an error when changing: treesort = flatten . foldr insert Leaf
to treesort = flatten( foldr insert Leaf )
?
a source to share
what treeort does is apply insertion to each item in the list, thus creating a tree and then flattening it.
Right.
[Where is the list hiding?]
In a functional language, you don't need to specify value arguments of the function type. For example, if I write
f = concat . map (map toUpper)
I am getting a function like [[Char]] -> [Char]
. This function expects an argument even if there is no argument in the defining equation. This is exactly the same as if I wrote
f strings = (concat . map (map toUpper)) strings
Since the dot operator is part of the function, why is it wrong to change
f . g
tof (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 that apps are related in different ways, but f. g
different from f g
.
This is a type error because it foldr insert Leaf
is a list-to-tree function and is flatten
intended to be applied to a single tree, not a function.
a source to share
To answer your last question, you get 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 using .
, you 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)
It also explains where the parameter was hiding list
. When linking functions, you don't need to write parameters explicitly, because the result of an 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)
a source to share
Sometimes, until you are familiar with the meaningless style, it is helpful to mentally do an epsilon transform.
If f is an expression with a function type, then you can convert it to \ e → (f) e
And if we have a type definition
a = \e -> (f) e
we can always safely rewrite it as
a e = (f) e
In this way,
treesort = flatten . foldr insert Leaf
coincides with
treesort list = (flatten . foldr insert Leaf) list
a source to share