I defined a binary tree and used my functions to create a new tree.
data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show)
singleton :: a -> Tree a
singleton x = Node x EmptyTree EmptyTree
treeInsert :: (Ord a) => a -> Tree a -> Tree a
treeInsert x EmptyTree = singleton x
treeInsert x (Node a left right)
| x < a = Node a (treeInsert x left) right
| x > a = Node a left (treeInsert x right)
| otherwise = Node a left right
when I executed this in the terminal:
let nums = [8,6,4,1,7,3,5]
let numsTree= foldl treeInsert EmptyTree nums
It returned an error.
Occurs check: cannot construct the infinite type: a ~ Tree a
Expected type: Tree a -> Tree a -> Tree a
Actual type: a -> Tree a -> Tree a
however, after I changed foldl to foldr, it works.
let numsTree= foldr treeInsert EmptyTree nums
Can anyone tell me why? And what is the difference between foldl and foldr in this case, I am not clear with it. Thanks!
There are two differences between foldr and foldl. The important one is the way they parenthesize their calculation:
foldl (+) 0 [1..3] = ((0 + 1) + 2) + 3
foldr (+) 0 [1..3] = 1 + (2 + (3 + 0))
The other one is that they expect their first argument (the function), to take its arguments in opposite order:
> :t foldl
foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b
> :t foldr
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
I believe the only reason for this second difference is to match the order that the expressions are written in the first code snippet. You should choose between the functions based on which order of parentheses you want, and flip your function to match if necessary.
So in your case, the two options are:
foldr treeInsert EmptyTree nums
foldl (flip treeInsert) EmptyTree nums
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments