I want to write a function that adds an item to a list in the correct order say 1 in [2, 3]. I am new to haskell and need help on how to do it without using Ord.
2 Answers
Your question makes no sense without using Ord.
Using Ord, the function you want is insert
The insert function takes an element and a list and inserts the element into the list at the last position where it is still less than or equal to the next element.
2 Comments
Louie
THe list passed in are in order
Dan Burton
@Louie then the next sentence in the documentation applies: "In particular, if the list is sorted before the call, the result will also be sorted."
It's not hard to write a function that inserts an element into a sorted list. It would look something like this:
insert :: Ord a => a -> [a] -> [a]
insert x [] = [x]
insert x (y:ys)
| x > y = y : insert x ys
| otherwise = x : y : ys
However, this is unlikely to be efficient for your use case. The problem with a list is that you end up creating a new copy of a large part of the spine repeatedly with this kind of insertion problem. You also have to scan linearly across the list until you find the right location, which isn't the fastest way to search for the right location.
You might be better off using a data structure such as the one in Data.Set or Data.IntSet. These are typically O(log n) for insertion because they use trees or other data structures that permit more sharing than a list does, and find the right location fast.
2 Comments
chrisdb
Just to be clear, for large n (list/set size), O(log n) is significantly better than O(n), which is what you would get if you use a list as you propose.
lesolorzanov
Do I have to return [a] ? can you elaborate on the answer?
Ordlouie 1 [2,3]andlouie 2 [1,3]are both supposed to be[1,2,3]. But, for example, what arelouie 1 [3,2]orlouie 2 [3,1]orlouie 6 [5,3,17,2]supposed to be?