# Implementing Haskell's insert

Learn You a Haskell shows the insert function.

insert takes an element and a list of elements that can be sorted and inserts it into the last position where it's still less than or equal to the next element. In other words, insert will start at the beginning of the list and then keep going until it finds an element that's equal to or greater than the element that we're inserting and it will insert it just before the element.

ghci> insert 4 [3,5,1,2,8,2]
[3,4,5,1,2,8,2]
ghci> insert 4 [1,3,4,4,1]
[1,3,4,4,4,1]


How's my implementation?

insert' :: (Ord a) => a -> [a] -> [a]
insert' x []     = [x]
insert' x yys@(y:ys) = if x <= y then x : yys else y : insert' x ys

• Looks good! I'd use guards in place of an if, but that's a stylistic choice. If you ignore the overloading and micro-optimizations, that's the way Data.List defines insert. May 15, 2014 at 8:05

In my experience idiomatic Haskell does not use if/else very much. Guards are definitely the preferred approach. The idea is to have the core of your logic in a function and let the checks and edge cases be handled at the edges. This also tends to end up with cleaner, more open code. Using the guard lets the reader see exactly what is happening without having to look inside the if/else branches.

insert' :: (Ord a) => a -> [a] -> [a]
insert' x []         = [x]
insert' x yys@(y:ys)
| x <= y           = x : yys
| otherwise        = y : insert' x ys


If you are concerned about speed, the compiler transforms the guards and the if/else into the same case structure internally. I made a simple main:

main = putStrLn $show$ insert' 2 $insert' 4 [3,2,1]  Below is the relevant section from ghc -O2 -ddump-simpl insert.hs. I added comments to shows where your original code is to help you read it. Rec { Main.main_$sinsert' [Occ=LoopBreaker]
:: GHC.Integer.Type.Integer
-> [GHC.Integer.Type.Integer] -> [GHC.Integer.Type.Integer]
[GblId, Arity=2, Caf=NoCafRefs, Str=DmdType LS]
Main.main_$sinsert' = \ (x_akb :: GHC.Integer.Type.Integer) (ds_dxR :: [GHC.Integer.Type.Integer]) -> case ds_dxR of wild_X8 { [] -> GHC.Types.: @ GHC.Integer.Type.Integer x_akb (GHC.Types.[] @ GHC.Integer.Type.Integer); {- [x] case -} : y_ake ys_akf -> case GHC.Integer.Type.leInteger x_akb y_ake of _ { GHC.Types.False -> GHC.Types.: @ GHC.Integer.Type.Integer y_ake (Main.main_$sinsert' x_akb ys_akf); {- recurse -}
GHC.Types.True ->
GHC.Types.: @ GHC.Integer.Type.Integer x_akb wild_X8 {- return of final list -}
}
}
end Rec }


Your version is fine. As bisserlis mentioned, guards would probably look nicer.

I find the following more readable, but of course it has worse performance:

insert' x ys = let (small, big) = span (< x) ys
in small ++ [x] ++ big