Sorting an unsorted list and filtering

Learn
#1

Hello guys I am learning Haskell and trying to apply a filter on a list which is sorted from an unsorted list. Here are some backing functions:

data BST = Leaf | Node BST Int BST -- a binary search tree
insertTree :: Int -> BST -- insert an element to the BST
buildTree :: [Int] -> BST -- Build a binary search tree with insertTree
inOrder :: BST -> [Int] -- Conduct an in-order traversal so as to get a sorted list

Then, I need to implement a filter function which takes an unordered list, sort it with the help of the BST, filter out desired results, and output the results in order. I tried two ways:
One is

filter :: [Int] -> [Int]
filter lst = case inOrder (buildTree lst) of
                [] -> []
                hd : tl -> if hd > 50 then hd : filter tl else filter tl

The other is

filter_ordered :: [Int] -> [Int]
filter_ordered lst = case lst of
                        [] -> []
                        hd : tl -> if hd > 50 then hd : filter tl else filter tl
filter :: [Int] -> [Int]
filter lst = filter_ordered (inOrder (buildTree lst))

It turns out that the first solution is extremely slow due to repeated execution of inOrder (buildTree lst). I wonder why the first one does repeated execution while the second does not. Does encapsulating an operation into a function avoid this?

#2

In the first case, at each step of the recursive function, you create a tree from the list you receive in input, and then create a list from the tree you created. Apart from the multiple creations of trees, this is useless after the first passage, because the list you receive in input will already be sorted after the first recursion step . The execution pattern is something like list->tree->list->tree->list->tree…

In the second case, you create a tree from the original list, then get back an ordered list, and then you just recurse over this list, never creating new trees or lists again (just the return value). The pattern is something like list->tree->list->list->list->…

2 Likes