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

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 }

StackExchange Code Review Q#49791, answer score: 2