Adding an element to a list

I want to write a function that adds开发者_Python百科 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.

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.

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.