flattener

flattener.hs

module Main where

import Data.List (nub)

-- Pattern Matching Flattener Algorithm
-- ====================================
-- 
-- This algorithm converts pattern matching expressions with multiple 
-- scrutinees into nested case trees with single scrutinees.
--
-- Example transformation:
--   match x y                =>    match x:
--   | Z     Z         = X0          case Z:
--   | (S x) Z         = X1            match y:
--   | Z     (S y)     = X2              case Z: X0
--   | (S x) (S Z)     = X3              case S y: X2
--   | (S x) (S (S z)) = X4            case S x:
--                                       match y:
--                                         case Z: X1
--                                         case S y_:
--                                           match y_:
--                                             case Z: X3
--                                             case S z: X4
--
-- The algorithm works column-by-column from left to right:
-- 1. Take the first scrutinee (x) and its column of patterns [Z, S x, Z, S x]
-- 2. Group rules by constructor (Z and S)
-- 3. For each constructor, extract its arguments and continue with remaining columns
-- 4. Handle variable patterns as default cases

-- Data Types
-- ----------

-- Expr represents expressions in our pattern matching language
-- Examples:
--   Ctr "Z" []           represents the zero constructor: Z
--   Ctr "S" [Var "x"]    represents successor: (S x)
--   Var "x"              represents a variable: x
--   Mat [e1,e2] rules    represents a pattern match on expressions e1,e2
data Expr = Ctr String [Expr] | Var String | Mat [Expr] [([Expr], Expr)] deriving (Show, Eq)

-- Utilities
-- ---------

-- Check if expression is a variable
-- Examples:
--   isVar (Var "x") = True
--   isVar (Ctr "Z" []) = False
isVar :: Expr -> Bool
isVar (Var _) = True
isVar _       = False

-- Extract constructor names from column
-- Example:
--   getCtrs [Ctr "Z" [], Var "x", Ctr "S" [Var "y"], Ctr "Z" []] 
--   = ["Z", "S"]
getCtrs :: [Expr] -> [String]
getCtrs col = nub [c | Ctr c _ <- col]

-- Get arity of constructor in column
-- Example:
--   getArity "S" [Ctr "Z" [], Ctr "S" [Var "x"], Var "y"]
--   = 1 (because S takes 1 argument)
getArity :: String -> [Expr] -> Int
getArity c col = maximum (0 : [length args | Ctr c' args <- col, c == c'])

-- Flattener
-- ---------

-- Convert a Mat expression to a flattened Mat (case tree representation)
-- The algorithm processes one scrutinee at a time, from left to right
-- Example transformation:
--   Mat [x, y] [([Z, Z], X0), ([S x, Z], X1), ([Z, S y], X2), ([S x, S y], X3)]
--   becomes a nested case tree on x then y
flatten :: Expr -> Expr
flatten e = flattenWithDepth 0 e

flattenWithDepth :: Int -> Expr -> Expr
flattenWithDepth d (Mat (x:xs) rules) = processColWithDepth d x (splitCol rules) xs
flattenWithDepth d (Mat [] [([], rhs)]) = rhs  -- No patterns left, return result
flattenWithDepth d (Mat [] _) = error "Incomplete pattern match"
flattenWithDepth d e = e  -- Non-Mat expressions are already flat

-- Split rules into first column of patterns and remaining rules
-- Example:
--   splitCol [([Z, Z], X0), ([S x, Z], X1), ([Z, S y], X2)]
--   = ([Z, S x, Z], [([Z], X0), ([Z], X1), ([S y], X2)])
--   First element: patterns from first column [Z, S x, Z]
--   Second element: remaining patterns and results
splitCol :: [([Expr], Expr)] -> ([Expr], [([Expr], Expr)])
splitCol rules = unzip [(p, (ps, rhs)) | (p:ps, rhs) <- rules]

-- Process a single column of patterns
-- This is the core of the algorithm: it decides how to handle the current column
-- Example with col = [Z, S x, Z] (mixed constructors):
--   Creates a Mat that switches on 'scrut' with cases for Z and S
processCol :: Expr -> ([Expr], [([Expr], Expr)]) -> [Expr] -> Expr
processCol = processColWithDepth 0

processColWithDepth :: Int -> Expr -> ([Expr], [([Expr], Expr)]) -> [Expr] -> Expr
processColWithDepth d scrut (col, rules) scruts
  | all isVar col = flattenWithDepth d (Mat scruts rules)       -- Skip variable-only columns
  | otherwise     = Mat [scrut] (ctrRules++varRules) -- Build case tree as Mat
  where ctrRules = makeCtrRulesWithDepth d col rules scruts
        varRules = makeVarRulesWithDepth d col rules scruts

-- Build constructor rules for case tree
-- For each constructor in the column, create a case branch
-- Example: if col has Z and S constructors, create two branches
makeCtrRules :: [Expr] -> [([Expr], Expr)] -> [Expr] -> [([Expr], Expr)]
makeCtrRules = makeCtrRulesWithDepth 0

makeCtrRulesWithDepth :: Int -> [Expr] -> [([Expr], Expr)] -> [Expr] -> [([Expr], Expr)]
makeCtrRulesWithDepth d col rules scruts = concatMap makeRule (getCtrs col) where

  -- Create a case branch for constructor c
  -- Example: for constructor "S" with patterns like (S x) and (S (S y)):
  --   fieldPats might be [Var "x"] or [Ctr "S" [Var "y"]]
  --   fieldVars uses existing names when available, fresh vars otherwise
  --   The result is a case branch: ([S x], <recursive match on x>)
  makeRule c = [([Ctr c fieldVars], subExpr) | not (null specialized)] where
    fieldPats   = getFieldPats c col rules
    -- Use existing variable names when available, otherwise create fresh ones
    fieldVars   = [case p of 
                     Var v -> Var v  -- Keep user-provided names
                     _     -> Var ("x" ++ show (d * 10 + i))
                  | (p, i) <- zip fieldPats [0..]]
    newScruts   = fieldVars ++ scruts  -- Always use variables as scrutinees
    specialized = specializeRules c col rules
    subExpr     = flattenWithDepth (d+1) (Mat newScruts specialized)

  -- Extract subpatterns from a constructor match
  -- Example: getFieldPats "S" [Z, S x, S (S y)] rules
  --   finds first S pattern and returns its arguments: [Var "x"]
  --   For nested patterns like (S (S y)), returns: [Ctr "S" [Var "y"]]
  --   If no S found, returns wildcards based on arity
  getFieldPats :: String -> [Expr] -> [([Expr], Expr)] -> [Expr]
  getFieldPats c col rules = 
    case [(args, rule) | (Ctr c' args, rule) <- zip col rules, c == c'] of
      ((args, _):_) -> args
      []            -> replicate (getArity c col) (Var "_")

  -- Specialize rules for a specific constructor
  -- Example: specializeRules "S" [Z, S x, Var y] [([Z], X0), ([Z], X1), ([S y], X2)]
  --   Row 1: Z doesn't match S, skip
  --   Row 2: (S x) matches S, extract x and prepend: ([x, Z], X1)
  --   Row 3: Variable matches anything, add wildcards: ([_, S y], X2)
  specializeRules :: String -> [Expr] -> [([Expr], Expr)] -> [([Expr], Expr)]
  specializeRules c col rules = concat (zipWith specialize col rules) where
    specialize (Ctr c' args) (ps, rhs) | c == c' = [(args ++ ps, rhs)]
    specialize (Var _)       (ps, rhs)           = [(replicate (getArity c col) (Var "_") ++ ps, rhs)]
    specialize _             _                   = []

-- Build variable/default rules for case tree
-- Creates a default case for patterns with variables
-- Example: if col = [Z, Var x, S y] and we've handled Z and S,
--   the variable case handles the middle rule
makeVarRules :: [Expr] -> [([Expr], Expr)] -> [Expr] -> [([Expr], Expr)]
makeVarRules = makeVarRulesWithDepth 0

makeVarRulesWithDepth :: Int -> [Expr] -> [([Expr], Expr)] -> [Expr] -> [([Expr], Expr)]
makeVarRulesWithDepth d col rules scruts
  | hasVars   = [([Var "_"], flattenWithDepth d (Mat scruts varRules))]
  | otherwise = []
  where
    hasVars  = any isVar col
    varRules = selectVarRules col rules

    -- Select rules that match on variables
    -- Example: selectVarRules [Z, Var x, S y] rules
    --   returns only the second rule (the one with Var x)
    selectVarRules :: [Expr] -> [([Expr], Expr)] -> [([Expr], Expr)]
    selectVarRules col rules = concat (zipWith select col rules) where
      select (Var _) clause = [clause]
      select _ _ = []

-- Pretty Printing
-- ---------------

-- Generate indentation
indent :: Int -> String
indent n = replicate n ' '

-- Pretty print expressions
ppExpr :: Expr -> String
ppExpr (Var v) = v
ppExpr (Ctr c []) = "(" ++ c ++ ")"
ppExpr (Ctr c args) = "(" ++ c ++ " " ++ unwords (map ppExpr args) ++ ")"
ppExpr (Mat scruts rules) = ppMat 0 (Mat scruts rules)

-- Print field variables if any
ppFields :: [String] -> String
ppFields [] = ""
ppFields fs = " " ++ unwords fs

-- Pretty print Mat expressions
ppMat :: Int -> Expr -> String
ppMat ind (Mat [] [([], e)]) = indent ind ++ ppExpr e
ppMat ind (Mat scruts rules) = 
  indent ind ++ "match " ++ ppScruts scruts ++ ":\n" ++
  concatMap (ppRule (ind + 2)) rules
ppMat ind e = indent ind ++ ppExpr e

-- Pretty print scrutinees (showing <pattern> for non-variables)
ppScruts :: [Expr] -> String  
ppScruts scruts = unwords (map ppScrut scruts)
  where ppScrut (Var v) = v
        ppScrut e       = "<" ++ ppExpr e ++ ">"

-- Print a rule
ppRule :: Int -> ([Expr], Expr) -> String
ppRule ind (pats, body) = 
  indent ind ++ "case " ++ ppPats pats ++ ":\n" ++
  ppBody (ind + 2) body ++ "\n"

-- Print patterns
ppPats :: [Expr] -> String
ppPats [Ctr c args] = c ++ ppFields [n | Var n <- args]
ppPats [Var v] = v
ppPats pats = unwords (map ppExpr pats)

-- Print rule body
ppBody :: Int -> Expr -> String
ppBody ind e@(Mat _ _) = ppMat ind e
ppBody ind e = indent ind ++ ppExpr e

-- Main
-- ----

-- Test the flattener
main :: IO ()
main = do
  let example = makeExample
      result  = flatten example
  
  putStrLn "Input:\nmatch x y"
  putStrLn "| Z     Z         = X0"
  putStrLn "| (S x) Z         = X1"
  putStrLn "| Z     (S y)     = X2"
  putStrLn "| (S x) (S Z)     = X3"
  putStrLn "| (S x) (S (S z)) = X4\n"
  putStrLn "Output:"
  putStrLn $ ppMat 0 result
  putStrLn "\nStep-by-step explanation:"
  putStrLn "1. First column has [Z, S x, Z, S x, S x] - mixed constructors"
  putStrLn "2. Create case on x with branches for Z and S"
  putStrLn "3. For Z branch: remaining patterns are [Z, S y] on y"
  putStrLn "4. For S branch: remaining patterns are [Z, S Z, S (S z)] on y"
  putStrLn "5. The nested pattern (S Z) and (S (S z)) create another level"
  putStrLn "6. User names (x, y, z) are preserved; fresh vars (x0, x1) only when needed"

-- Build example match expression
-- This represents:
--   match x y
--   | Z     Z         = X0
--   | (S x) Z         = X1  
--   | Z     (S y)     = X2
--   | (S x) (S Z)     = X3
--   | (S x) (S (S z)) = X4
makeExample :: Expr
makeExample = Mat [Var "x", Var "y"] 
  [ ([zero, zero], Var "X0")
  , ([suc (Var "x"), zero], Var "X1")
  , ([zero, suc (Var "y")], Var "X2")
  , ([suc (Var "x"), suc zero], Var "X3")
  , ([suc (Var "x"), suc (suc (Var "z"))], Var "X4")
  ]
  where
    zero = Ctr "Z" []
    suc x = Ctr "S" [x]

module Kind.Parse where

(imports omitted)

type Uses     = [(String, String)]
type PState   = (String, Int, Uses)
type Parser a = P.ParsecT String PState Identity a
-- Types used for flattening pattern-matching equations
type Rule     = ([Pattern], Term)
data Pattern  = PVar String | PCtr (Maybe String) String [Pattern] | PNum Word64 | PSuc Word64 String

(parser omitted)

-- Flattener
-- ---------

-- FIXME: the functions below are still a little bit messy and can be improved

-- Flattener for pattern matching equations
flattenDef :: [Rule] -> Int -> Term
flattenDef rules depth =
  let (pats, bods) = unzip rules
  in flattenRules pats bods depth

flattenWith :: Int -> [Term] -> [Rule] -> Term
flattenWith dep wth rul =
  -- Wrap the 'with' arguments and patterns in Pairs since the type checker only takes one match argument.
  let wthA = foldr1 (\x acc -> Ann True (Con "Pair" [(Nothing, x), (Nothing, acc)]) (App (App (Ref "Pair") (Met 0 [])) (Met 0 []))) wth
      rulA = map (\(pat, wth) -> ([foldr1 (\x acc -> PCtr Nothing "Pair" [x, acc]) pat], wth)) rul
      bod  = flattenDef rulA (dep + 1)
  in App bod wthA

flattenRules :: [[Pattern]] -> [Term] -> Int -> Term
flattenRules ([]:mat)   (bod:bods) depth = bod
flattenRules (pats:mat) (bod:bods) depth
  | all isVar col                 = flattenVarCol col mat' (bod:bods) (depth + 1)
  | not (null (getColCtrs col))   = flattenAdtCol col mat' (bod:bods) (depth + 1)
  | isJust (fst (getColSucc col)) = flattenNumCol col mat' (bod:bods) (depth + 1)
  | otherwise                     = error "invalid pattern matching function"
  where (col,mat') = getCol (pats:mat)
flattenRules _ _ _ = error "internal error"

-- Flattens a column with only variables
flattenVarCol :: [Pattern] -> [[Pattern]] -> [Term] -> Int -> Term
flattenVarCol col mat bods depth =
  -- trace (replicate (depth * 2) ' ' ++ "flattenVarCol: col = " ++ show col ++ ", depth = " ++ show depth) $
  let nam = maybe "_" id (getVarColName col)
      bod = flattenRules mat bods depth
  in Lam nam (\x -> bod)

-- Flattens a column with constructors and possibly variables
flattenAdtCol :: [Pattern] -> [[Pattern]] -> [Term] -> Int -> Term
flattenAdtCol col mat bods depth =
  -- trace (replicate (depth * 2) ' ' ++ "flattenAdtCol: col = " ++ show col ++ ", depth = " ++ show depth) $
  let ctr = map (makeCtrCase col mat bods depth) (getColCtrs col)
      dfl = makeDflCase col mat bods depth
      nam = getMatNam col
  in case nam of
    (Just nam) -> (Lam nam (\x -> App (Mat (ctr++dfl)) (Ref nam)))
    Nothing    -> Mat (ctr++dfl)

-- Creates a constructor case: '#Name: body'
makeCtrCase :: [Pattern] -> [[Pattern]] -> [Term] -> Int -> String -> (String, Term)
makeCtrCase col mat bods depth ctr =
  -- trace (replicate (depth * 2) ' ' ++ "makeCtrCase: col = " ++ show col ++ ", mat = " ++ show mat ++ ", bods = " ++ show (map showTerm bods) ++ ", depth = " ++ show depth ++ ", ctr = " ++ ctr) $
  let var           = getCtrColNames col ctr
      (mat', bods') = foldr (go var) ([], []) (zip3 col mat bods)
      bod           = flattenRules mat' bods' (depth + 1)
  in (ctr, bod)
  where go var ((PCtr nam cnam ps), pats, bod) (mat, bods)
          | cnam == ctr = ((ps ++ pats):mat, bod:bods)
          | otherwise  = (mat, bods)
        go var ((PVar "_"), pats, bod) (mat, bods) =
          let pat = map (maybe (PVar "_") PVar) var
          in ((pat ++ pats):mat, bod:bods)
        go var ((PVar nam), pats, bod) (mat, bods) =
          let vr2 = [maybe (nam++"."++show i) id vr | (vr, i) <- zip var [0..]]
              pat = map PVar vr2
              bo2 = Use nam (Con ctr (map (\x -> (Nothing, Ref x)) vr2)) (\x -> bod)
          in ((pat ++ pats):mat, bo2:bods)
        go var (_, pats, bod) (mat, bods) =
          (mat, bods)

-- Creates a default case: '#_: body'
makeDflCase :: [Pattern] -> [[Pattern]] -> [Term] -> Int -> [(String, Term)]
makeDflCase col mat bods depth =
  -- trace (replicate (depth * 2) ' ' ++ "makeDflCase: col = " ++ show col ++ ", depth = " ++ show depth) $
  let (mat', bods') = foldr go ([], []) (zip3 col mat bods) in
  if null bods' then [] else [("_", flattenRules mat' bods' (depth + 1))]
  where go ((PVar nam), pats, bod) (mat, bods) = (((PVar nam):pats):mat, bod:bods)
        go (_,          pats, bod) (mat, bods) = (mat, bods)

flattenNumCol :: [Pattern] -> [[Pattern]] -> [Term] -> Int -> Term
flattenNumCol col mat bods depth =
  -- Find the succ case with the value
  let (suc, var) = getColSucc col
      sucA       = fromJust suc
      varA       = maybe ("%n-" ++ show sucA) id var
      numCs      = map (makeNumCase col mat bods depth) [0..sucA-1]
      sucCs      = (makeSucCase col mat bods depth sucA varA)
  in foldr (\x acc -> Swi x acc) sucCs numCs

makeNumCase :: [Pattern] -> [[Pattern]] -> [Term] -> Int -> Word64 -> Term
makeNumCase col mat bods depth num =
  let (mat', bods') = foldr go ([], []) (zip3 col mat bods)
  in if null bods' then error $ "missing case for " ++ show num
     else (flattenRules mat' bods' (depth + 1))
  where go ((PNum val), pats, bod) (mat, bods)
          | val == num = (pats:mat, bod:bods)
          | otherwise  = (mat, bods)
        go ((PVar "_"), pats, bod) (mat, bods) =
          (pats:mat, bod:bods)
        go ((PVar nam), pats, bod) (mat, bods) =
          let bod' = Use nam (Num num) (\x -> bod)
          in (pats:mat, bod':bods)
        go (_, pats, bod) (mat, bods) =
          (mat, bods)

makeSucCase :: [Pattern] -> [[Pattern]] -> [Term] -> Int -> Word64 -> String -> Term
makeSucCase col mat bods depth suc var =
  let (mat', bods') = foldr go ([], []) (zip3 col mat bods)
      bod           = if null bods' then error $ "missing case for " ++ show suc ++ "+" ++ var
                      else (flattenRules mat' bods' (depth + 1))
  in Lam var (\x -> bod)
  where go ((PSuc _ _), pats, bod) (mat, bods) = (pats:mat, bod:bods)
        go ((PVar "_"), pats, bod) (mat, bods) = (pats:mat, bod:bods)
        go ((PVar nam), pats, bod) (mat, bods) = 
          let bodA = Use nam (Op2 ADD (Num suc) (Ref var)) (\x -> bod)
          in (pats:mat, bodA:bods)
        go (_, pats, bod)          (mat, bods) = (mat, bods)

-- Helper Functions

isVar :: Pattern -> Bool
isVar (PVar _) = True
isVar _        = False

getCol :: [[Pattern]] -> ([Pattern], [[Pattern]])
getCol (pats:mat) = unzip (catMaybes (map uncons (pats:mat)))

getColCtrs :: [Pattern] -> [String]
getColCtrs col = toList . fromList $ foldr (\pat acc -> case pat of (PCtr _ cnam _) -> cnam:acc ; _ -> acc) [] col

getVarColName :: [Pattern] -> Maybe String
getVarColName col = foldr (A.<|>) Nothing $ map go col
  where go (PVar "_") = Nothing
        go (PVar nam) = Just nam
        go _          = Nothing

-- For a column of patterns that will become a Mat,
-- return the name of the inner fields or Nothing if they are also Mats.
getCtrColNames :: [Pattern] -> String -> [Maybe String]
getCtrColNames col ctr = 
  let mat = foldr go [] col
  in map getVarColName (transpose mat)
  where go (PCtr nam cnam ps) acc
          | cnam == ctr = ps:acc
          | otherwise   = acc
        go _ acc        = acc

getMatNam :: [Pattern] -> Maybe String
getMatNam (PCtr (Just nam) _ _:_) = Just nam
getMatNam (_:col)                 = getMatNam col
getMatNam []                      = Nothing

-- If theres a PSuc, it returns (Just val, Just nam)
-- If there a PNum a PVar but no PSuc, it returns (Just (max val + 1), Nothing)
-- Otherwise, it returns (Nothing, Nothing)
getColSucc :: [Pattern] -> (Maybe Word64, Maybe String)
getColSucc pats =
  case findSuc pats of
    Just (val, name) -> (Just val, Just name)
    Nothing          -> case (maxNum pats Nothing) of
      Just maxVal -> (Just (maxVal + 1), Nothing) 
      Nothing     -> (Nothing, Nothing)
  where
    findSuc []                = Nothing
    findSuc (PSuc val name:_) = Just (val, name)
    findSuc (_:rest)          = findSuc rest

    maxNum []            acc        = acc
    maxNum (PNum val:ps) Nothing    = maxNum ps (Just val)
    maxNum (PNum val:ps) (Just max) = maxNum ps (Just (if val > max then val else max))
    maxNum (_:ps)        acc        = maxNum ps acc

NOTE: the code above implements the "flattening algorithm" for Kind's proof assistant.
It is a parse-time algorithm that converts expressions in the form (roughly):

foo : ℕ → ℕ → ℕ
foo Z     Z     = X0
foo (S x) Z     = X1
foo Z     (S y) = X2
foo (S x) (S y) = X3

into a tree of pattern-matching expressions, like:

foo = λx. λy.
  match x:
    case Z:
      match y:
        case Z:
          X0
        case (S y):
          X1
    case (S x):
      match y:
        case Z:
          X2
        case (S y):
          X3

it also supports Agda-like 'with' expressions, like:

foo : ℕ → ℕ → ℕ
foo Z     Z     = X0
foo (S x) Z     with (F x)
. | Nil         = X1
. | (Cons x xs) = X2
foo Z     (S y) = X3
foo (S x) (S y) with (G x y)
. | None        = X4
. | Some k with (H k)
.. | True       = X5
.. | False      = X6

which would be desugared to:

foo x y =
  match x:
    case Z:
      match y:
        case Z:
          X0
        case (S y):
          X3
    case (S x):
      match y:
        case Z:
          match (F x):
            case Nil:
              X1
            case (Cons x xs):
              X2
        case (S y):
          match (G x y):
            case None:
              X4
            case (Some k):
              match (H k):
                case True:
                  X5
                case False:
                  X6

it also supports nested constructors; for example:

...
foo (S (S x)) (S (S y)) = A

would be desugared to:

foo x y =
  match x:
    case (S x_):
      match x_:
        case (S x__):
          match y:
            case (S y_):
              match y_:
                case (S y__):
                  A
  ...

and so on.

finally, it also includes default cases.

now, we'd like to implement an isolated, simplified version of this algorithm.

it should work as follows.

first, we declare a generic type to represent pattern-matching clauses:

-- A tree expression: `(FooBar (Foo (Tic) x) (Bar (Tac) y))`
data Expr
  = Ctr String [Expr] -- a constructor
  | Var String        -- a variable

-- A clause is a list of expressions (lhs) plus a returned expression (rhs)
data Clause
  = Clause [Expr] Expr

-- A pattern-match is a list of scrutinees, followed by a list of clauses:
data Match
  = Match [Expr] [Clause]

second, we declare a generic type to reprent pattern-match trees:

-- A case-tree is either a return value, or a case-of expression
data CaseTree
  = Ret Expr                       -- return expression (rhs)
  | Mat Expr                       -- scrutinee
      [(String,[String],CaseTree)] -- constructor branches
      (Maybe (String, CaseTree))   -- default / variable branch

finally, we implement an algorithm that converts from a pattern-match to a case-tree

for example, such algorithm would convert from:

match x y
| Z     Z     = X0
| (S x) Z     = X1
| Z     (S y) = X2
| (S x) (S y) = X3

to:

match x:
  case Z:
    match y:
      case Z:
        X0
      case S:
        X2
  case S:
    match y:
      case Z:
        X1
      case S:
        X3

now, based on the document above, write a standalone main.hs file that
implements the flattener algorithm depicted above. that file must include the
relevant types (don't just copy/paste my types, review them to make sure they're
logically sound), a simple stringifier, the algorithm itself, and a main
function that tests it on the example above.