Little code review for mojjo

insert-sort-steps.hs

-- This program genereates all computation steps that the
-- imperative algorithm InserSort would take while sorting a list.
-- The output might be further used for vizualizations of the
-- alorithm behavior.

-- Example usage:
-- insertSortSteps [3,2,1]

-- Result:
-- [Step {i = 0, j = 1, xs = [3,2,1]},
--  Step {i = 1, j = 2, xs = [3,1,2]},
--  Step {i = 1, j = 1, xs = [1,3,2]}]

-- Wouldn't it be better to show xs after the step rather than before?

-- The List that will be sorted.
type Input a = [a]

-- A list of this type will be the result
data ComputationStep a =
  Step { i  :: Int
       , j  :: Int
       , xs :: [a]
       }
  deriving Show

-- I think making a type alias for a polymorphic list isn't very helpful
-- especially if the new name is as undescriptive as "Input". I guess this
-- is a matter of preference though.
--
-- Generates a list of all comutation steps the InsertSort
-- algorithm takes to sort a list.
insertSortSteps :: Ord a => Input a -> [ComputationStep a]
insertSortSteps xs =
  scanl f (Step i j xs) ijs
    where
      n = length xs
      (i, j):ijs = [(i, j) | i <- [0..n-2], j <- [i+1,i..1]]
      f (Step _ _ xs) (i, j) =
        Step i j (updateXs' (pred j) xs)
        -- Step i j (updateXs j xs)

-- Computes new xs based on an i and a j.
-- updateXs :: Ord a => [a] -> Int -> Int -> [a]
-- updateXs xs i j =
--   if (xs !! j) < (xs !! pred j)
--     then swap j (pred j) xs
--     else xs

-- You are not using i in this function, why pass it?
-- I would tend to use guards instead of "if then else" (but that's just personal preference).
-- Put the list as the last argument for better composition.
updateXs :: Ord a => Int -> [a] -> [a]
updateXs j xs
  | xs !! j < xs !! pred j = swap j (pred j) xs
  | otherwise              = xs

-- Swaps two elements in a list based on the given indices.
-- swap :: [a] -> Int -> Int -> [a]
-- swap xs i1 i2 =
--   zipWith f xs [0..]
--   where
--     f x i
--       | i == i1 = xs !! i2
--       | i == i2 = xs !! i1
--       | otherwise = x

-- Put the list as the last argument to make the function compose better.
-- What happens when the indices are out of bound? Would a safer version
-- of the function be more appropriate?
-- This version of swap works in one pass (unlike yours with (!!)) and should
-- work on infinite lists (like your version): take 10 . swap 2 3 $ [0..]
swap :: Int -> Int -> [a] -> [a]
swap i j xs
  | i == j    = xs
  | i > j     = swap j i xs
  | otherwise = before ++ (b : middle) ++ (a : end)
  where
    (before, a:rest) = splitAt i xs
    (middle, b:end)  = splitAt (j - i - 1) rest

-- Since you're always swaping with the next element why not exploit that to
-- make a simpler function?
swapAt :: Int -> [a] -> [a]
swapAt 0 (x:y:xs) = y:x:xs
swapAt n (x:xs)   = x : swapAt (pred n) xs
swapAt _ _        = error "Swapping out of bound indices"

-- While you're at it, why not do updateXs and swap in the same function in order
-- to avoid using (!!)
updateXs' :: Ord a => Int -> [a] -> [a]
updateXs' 0 (x:y:xs)
  | x < y     = x:y:xs
  | otherwise = y:x:xs
updateXs' n (x:xs) = x : updateXs' (pred n) xs

-- reminder InsertSort works like this in imperative languages, e.g. in JavaScript:

-- function insertSort (input)
-- {
--   const n = input.length;
--   for (var i = 0; i < n-1 ; i++)
--   {
--     for (var j = i + 1; j >= 1; j--)
--     {
--       if (input[j] < input[j - 1])
-- 	 {
--         swap(input, j, j - 1);
-- 	 }
--     }
--   }
-- }