CODEWITHSUNDEEP
listhaskellnodes
sudobangbang
sudobangbang

Reputation: 1456

Haskell, inserting into an ordered list

I am beginning to learn about Haskell and have been closely following the guides at http://learnyouahaskell.com and the documentation at https://wiki.haskell.org/How_to_work_on_lists. I have been working with nodes and binary trees as of late and have run into a problem that I cannot seem to figure out the correct syntax for.

If I have an ordered list of nodes:

[(2 , Nil, Nil), (4, Nil, Nil), (10, Nil, Nil)]

And I want to insert a new node (3, Nil, Nil) into the list so that it could be represented as:

[(2, Nil, Nil), (3, Nil, Nil),(4, Nil, Nil), (10, Nil, Nil)]

What is the most elegant solution to do this? From what I have read here it looks as if you have to split the list in two parts once you detect the correct position but as a beginner im not sure how to do this. Obviously the pseudo code would be something a long the lines of For every Node in the list, compare its number value versus the count value of the new Node . Once this value is greater than or equal to the current index, split the list into two parts (a and b) and then combine the list in this order a ++ [newElement] ++ b.

In my mind (again, at a beginner level) when trying to implement this it would look like:

sortedInsert

Upvotes: 1

Views: 2781

Answers (3)

amalloy
amalloy

Reputation: 92057

My suggestion looks a lot like Carsten's, but I think it's a bit nicer to use an auxiliary go function to avoid having to pass around the x argument manually so often:

insertOrdered :: Ord a => x -> [a] -> [a]
insertOrdered x = go where
  go [] = [x]
  go all@(y:ys) | x < y = x : all
                | otherwise = y : go ys

Upvotes: 1

SlySherZ
SlySherZ

Reputation: 1661

I suggest starting with simple lists, like lists of Nums. Here's a function that inserts a member in a list, as long as the elements can be compared:

insertOrdered :: Ord a => a -> [a] -> [a]   -- Ord means the elements of the list can be ordered
insertOrdered item [] = [item]              -- Empty list, return list with a single argument
insertOrdered item (first:ls)               -- Split list between first element and the rest of it
    | item <= first = item : first : ls     -- Append our item at the start and merge everything
    | otherwise = first : (insertOrdered item ls)   -- Merge the first element with the result of calling this again

You can test it immediatly with something like:

insertOrdered 1 [0, 2, 3]    -- [0, 1, 2, 3]

Now that it works for the simple case, you can think about your harder one. That means telling Haskell that you type can be ordered and how to do it, which you can learn here.

Upvotes: 1

Random Dev
Random Dev

Reputation: 52290

Well the pattern-matching is the usual one.

This is the general case:

insertOrdered :: Ord a => a -> [a] -> [a]
insertOrdered a [] = [a]
insertOrdered a bs'@(b:bs)
  | a <= b     = a : bs'
  | otherwise = b : insertOrdered a bs

your turn: replace the undefined with some code of yours ;)

Note

  • Whatever Nil here is you have to either make it an instance of Ord or you have to change the function to directly deal only with the first component of the tuple

I choose to just use:

data Nil = Nil
         deriving (Show, Eq, Ord)

and it will work as is:

λ> let xs = [(2 , Nil, Nil), (4, Nil, Nil), (10, Nil, Nil)]
λ> insertOrdered (3,Nil,Nil) xs
[(2,Nil,Nil),(3,Nil,Nil),(4,Nil,Nil),(10,Nil,Nil)]

but maybe you have to change this for you like this:

insertOrdered :: Ord a => (a,b,c) -> [(a,b,c)] -> [(a,b,c)]
insertOrdered x [] = undefined
insertOrdered x@(a,_,_) ((a',_,_):ys)
  | a <= a'   = undefined
  | otherwise = undefined -- probably something with insertOrdered?

Upvotes: 3

Related Questions