I am trying to create a tree from a list.
I have written the function using foldl and foldr (latter not shown)
treeFromList l
| null l = error "no elements in list"
| otherwise = foldl insertIfAbsent (initTree (head l)) (tail l)
where the Tree DS is defined in a separate module as
data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving Show
initTree x = (Node x EmptyTree EmptyTree)
and treeFold is manually written (not derived) as
foldTree f acc t
| (empty t) = acc
| otherwise = foldTree f outerVal (leftSub t)
where
outerVal = f (value t) rightVal
rightVal = foldTree f acc (rightSub t)
After giving this some thought, I believe this cannot be done because of a type conflict. In theory, the tree would need to be build up in the accumulator while the list is constantly reduced/folded over.
On the contrary, I was able to convert to foldl version to foldr, and apparently foldr can be expressed using foldTree.
Any suggestions? Thank you!
You seem to be confused about the different folds.
List-related folds foldr and foldl consume a list (or, more in general, a foldable) to produce something else (which might not be a list).
The tree-related fold foldTree consumes a tree to produce something else (which might not be a tree).
Hence, you can not switch from one to the other: if you only have a list as input, you do not have a tree to call foldTree with.