Let again be the total. Reject unless is divisible by three, and put . Define to mean that the first occurrences can be assigned to three groups so that the first two groups have sums and . Their third sum is already determined by the processed list prefix sum minus , so it need not be stored as another coordinate.
Initialize true and all other states false. For each reachable state, assign the next occurrence to exactly one group:
threeEqualParts(A):
    S = sum of A
    if S mod 3 != 0: return false
    h = S/3
    D[0..h,0..h] = false
    D[0,0] = true
    for each indexed entry a in A:
        Next[0..h,0..h] = false
        for x from 0 to h:
            for y from 0 to h:
                if D[x,y]:
                    Next[x,y] = true
                    if x+a <= h: Next[x+a,y] = true
                    if y+a <= h: Next[x,y+a] = true
        D = Next
    return D[h,h]
The three transitions put the occurrence in the third, first or second group, respectively. Using a fresh layer prevents reusing it. Conversely, deleting the last occurrence from any valid list prefix assignment leaves exactly one predecessor state, so induction proves completeness as well as soundness. At the final state , the third sum is , giving precisely the required disjoint partition.
There are states per layer and a constant number of transitions per state. Thus the time is , and rolling layers use space for nonempty inputs. The source mentions an additional integer in this part, but it does not occur in the stated equal-partition condition; the required target is determined by . Empty groups are allowed by the stated subset formulation.
Treat array entries as indexed occurrences, so equal numerical values may be selected independently. Put . Reject or . Define to mean that some subset of the first indices sums to . The base is and all other base entries are false. Considering whether index is selected gives
Only is needed, because all entries are positive. A one-dimensional implementation is
subsetSum(A, s):
    S = sum of A
    if s < 0 or s > S: return false
    D[0..s] = false
    D[0] = true
    for each indexed entry a in A:
        for t from s down to a:
            D[t] = D[t] or D[t-a]
    return D[s]
Descending updates make both right-hand-side values belong to the previous list prefix: when updating , the smaller location has not yet been updated for this entry. This prevents using the same occurrence repeatedly. Induction on the list prefix proves the recurrence and the returned answer.
The time is for nonempty input with , and space is . More generally one may fill through and answer every target from the same table. For a two-way equal partition, reject odd ; otherwise ask for target . A selected subset with that sum leaves its complement with the same sum. These are bounds polynomial in the numerical bound ; without that bound the method is pseudopolynomial in a binary-encoded unrestricted target.[ref]
A strict majority element in the whole array must be a strict majority element in at least one half: otherwise summing the two non-majority element frequency bounds would give at most half of all entries. This observation supplies at most two candidates, but they must still be verified in the whole subarray.
majority(A, left, right):
    if left == right: return NoMajority
    if right - left == 1: return Candidate(A[left])
    middle = floor((left + right)/2)
    first = majority(A, left, middle)
    second = majority(A, middle, right)
    for candidate in the two returned tagged results:
        if candidate is Candidate(x):
            count = 0
            for i from left to right-1:
                if A[i] == x: count = count + 1
            if 2*count > right-left: return Candidate(x)
    return NoMajority
NoMajority is a separate result tag, not a possible input element. The two-candidate loop does not require ordering, hashing or conversion of arbitrary elements to a set. It may count the same candidate twice without changing correctness or the bound.
Induction proves the recursive candidates correct. If the whole subarray has a majority element, the observation ensures it reaches the verification step; if a candidate passes the strict frequency test, it really is a majority element. The worst-case recurrence has two balanced recursive calls and linear combination work, so the running time is , with auxiliary recursion depth when the array is passed by index ranges. A different cancellation-based method can achieve linear time, but is not needed for this divide-and-conquer construction.
Sequential accumulation writes merged outputs of lengths . Its total work is
The growing list prefix is repeatedly copied, even though its internal order is already known.
Instead, divide the family of arrays into two nearly equal halves, recursively merge each half, and merge the two resulting sorted arrays. A balanced merge tree has levels; at each level at most entries are read or written in merges. Thus the bound is for , including the output work. Equivalently the recurrence in the number of arrays is . The one-array case simply returns it, or costs if a fresh output array is required.
There are three unnumbered cases inside this leaf.
For the nine-child recurrence, a recursion tree has subproblems of size about . There are constant-size leaves, and the total unit work over earlier levels is a geometric sum of the same order. Hence . This is also the first case of the master theorem, since and the additive work is constant.
For the decrementing recurrence, summing from the supplied base at three gives
so here as well. Values at the smaller base indices remain one as specified.
For the recurrence that squares its recursive result, set . Then above the base range. Let
After expansions, , giving the exact answer
For powers of two this is . For arbitrary positive integer , the exact values form plateaux: , while . In general . It is not uniformly over integer : near the top of a plateau the exponent is closer to . Keeping the integer halving is essential; the ordinary linear master theorem does not apply to squaring .
Merge by comparing the present heads and consuming just the chosen one. The implementation uses only the functional representation:
merge' :: Ord a => List a -> List a -> List a
merge' left right
  | null' left  = right
  | null' right = left
  | head' left <= head' right =
      cons' (head' left) (merge' (tail' left) right)
  | otherwise =
      cons' (head' right) (merge' left (tail' right))

mergeSort' :: Ord a => List a -> List a
mergeSort' input =
  let n = length' input
      middle = n `div` 2
  in if n <= 1 then input
     else merge' (mergeSort' (take' middle input))
                 (mergeSort' (drop' middle input))
The two recursive inputs are the disjoint initial and final portions of the represented sequence; they preserve every occurrence and have smaller lengths when . In merge', the smaller current head can precede every remaining value in both sorted inputs. Selecting the left head on equality preserves stability. Each merge step reduces the total number of remaining elements, and induction proves a sorted permutation of the original sequence.
This establishes algorithm termination and correctness on total finite representations, not an unconditional implementation bound. Nested index functions can make queries costly, and repeatedly finding lengths or heads may revisit them. The familiar merge-sort bound assumes suitable constant-time access or consumption primitives; the source's function-only representation supplies no such cost guarantee.
Clamp a nonpositive count to zero. Taking restricts the domain of present indices; dropping translates that domain:
take' :: Int -> List a -> List a
take' count (List f) = List query
  where
    k = max 0 count
    query i
      | i < 0 || i >= k = Nothing
      | otherwise      = f i

drop' :: Int -> List a -> List a
drop' count (List f) = List query
  where
    k = max 0 count
    query i
      | i < 0 || i > maxBound - k = Nothing
      | otherwise                = f (i+k)

length' :: List a -> Int
length' (List f) = countFrom 0
  where
    countFrom i = case f i of
                    Nothing -> i
                    Just _  -> countFrom (i+1)
For finite length , the first two operations give lengths and , respectively. The length loop reaches the first absent index, namely , so it terminates for a total finite representation. It does not terminate on an infinite represented sequence. There is no assumption that an arbitrary stored query function takes constant time.
Preserve absence and transform only a present value:
map' :: (a -> b) -> List a -> List b
map' g (List f) = List (\i -> case f i of
                              Nothing -> Nothing
                              Just x  -> Just (g x))
Every query keeps its presence status, so the represented length and the no-holes invariant are unchanged. The transformed element is computed only when demanded.
Inspect index zero for emptiness and the head; removing the head shifts the query in the other direction:
null' :: List a -> Bool
null' (List f) = case f 0 of
                  Nothing -> True
                  Just _  -> False

head' :: List a -> a
head' (List f) = case f 0 of
                  Nothing -> error "head of empty representation"
                  Just x  -> x

tail' :: List a -> List a
tail' input@(List f)
  | null' input = error "tail of empty representation"
  | otherwise   = List query
  where
    query i
      | i < 0 || i == maxBound = Nothing
      | otherwise             = f (i+1)
The no-holes invariant makes the zero-index test sufficient for emptiness. Both head' and tail' have the precondition that the representation is nonempty and signal an error when it is violated. On a nonempty representation, tail' removes exactly one position. The overflow guard is consistent with finite lengths at most maxBound.
The embedding is a right fold interpreting each source constructor by its new counterpart:
list' :: [a] -> List a
list' = foldr cons' nil'
Induction on the finite source list proves that querying index returns its th element exactly when lies in range. The empty case is nil'; the cons case shifts every tail index as established in part (b). This is the only part of Question 4 whose implementation uses the conventional list type.
The empty representation is nowhere present; prepending shifts all old positions by one:
nil' :: List a
nil' = List (\_ -> Nothing)

cons' :: a -> List a -> List a
cons' x (List f) = List query
  where
    query i
      | i < 0     = Nothing
      | i == 0    = Just x
      | otherwise = f (i-1)
For a represented length , cons' represents length , provided that length is representable. Index zero is the new head and each later valid index asks for the preceding old position. The no-holes invariant is preserved. No conventional list is built by either constructor.
A function returning an optional value supplies the representation:
newtype List a = List (Int -> Maybe a)
For a finite represented list, require a length such that every index returns Just its element and every other index returns Nothing. Thus there are no holes: absence at a nonnegative index implies absence at every later index. The type alone does not enforce this invariant, or algorithm termination of a query. An infinite represented sequence may instead have a present value at every nonnegative index; operations requiring its length will not terminate.
The implementations below return Nothing at negative indices. Finite lengths, requested counts and intermediate indices are assumed to fit Int; explicit guards on index shifts also prevent arithmetic wraparound from exposing an invalid element.
Generate a row while respecting the forbidden symbols in each column. Selection returns an element together with the still-available elements:
select :: [a] -> [(a,[a])]
select [] = []
select (x:xs) = (x,xs) : [(y,x:ys) | (y,ys) <- select xs]

row :: [Int] -> [[Int]] -> [[Int]]
row [] [] = [[]]
row remaining (used:otherColumns) =
  [x:rest | (x,available) <- select remaining,
            x `notElem` used,
            rest <- row available otherColumns]
row _ _ = []

latinPruned :: Int -> [[[Int]]]
latinPruned n
  | n < 0     = error "negative order"
  | otherwise = build n (replicate n [])
  where
    build 0 usedColumns = [[]]
    build remainingRows usedColumns =
      [r:rest | r <- row [1..n] usedColumns,
                rest <- build (remainingRows-1)
                              (zipWith (:) r usedColumns)]
The invariant of row is that remaining contains exactly the unused symbols of this row, while each member of the column list records symbols used by earlier rows. Selecting removes a symbol, so it cannot repeat in the current row; the membership test prevents a column repetition. A complete row uses every symbol once. Updating the column histories preserves the invariant for the next recursive call.
Every complete generated square is therefore valid without a final filter. Conversely, take any valid target square: its next row passes every selection and column test, so induction keeps a branch constructing that target. Distinct choices from the initially distinct symbols cannot generate the same square twice. Dead-end partial squares may still be explored; the method promises to avoid constructing complete invalid squares, not to foresee every future dead end. Independent enumeration gives 1, 2, 12 and 576 squares at orders one through four.
Choose each row from the permutations of the symbols:
squaresRows :: Int -> [[[Int]]]
squaresRows n
  | n < 0     = error "negative order"
  | otherwise = cp (replicate n (perms [1..n]))

latinRows :: Int -> [[[Int]]]
latinRows = filter valid . squaresRows
Every Latin square remains a candidate, because each of its rows is one of those permutations. Conversely every candidate has valid rows, so only its columns still need checking. There are candidates instead of : at order four, rather than more than four billion. The improvement is substantial but does not make exhaustive generation practical at arbitrary orders. One can replace valid by a column-only test here, since row validity is guaranteed by construction.
The generation count, before any validity test, is . It is at order three, at order four, and approximately at order five. Even an illustrative rate of one million complete candidates per second would require about 72 minutes at order four and about 9,444 years at order five, before accounting for the actual validity-checking cost. Thus order four is already expensive and order five is plainly impractical for this strategy; the exact threshold depends on the implementation and hardware, not just the mathematical count.
Figure 1.
Candidate growth before filtering in two Latin-square generation strategies
. Original exact candidate counts, plotted on a base-ten logarithmic vertical axis. These are mathematical counts, not measured running times; pruning can avoid many invalid partial extensions as well. Details.
The following predicate also checks the square's shape; sort is the three-way sorting function from Question 2:
valid :: [[Int]] -> Bool
valid rows =
  let n = length rows
      symbols = [1..n]
      goodRows = all (\r -> sort r == symbols) rows
      goodColumns = all (\j -> sort [r !! j | r <- rows] == symbols)
                        [0..n-1]
  in goodRows && goodColumns

latin :: Int -> [[[Int]]]
latin = filter valid . squares
The row tests guarantee that each row has length and contains each allowed symbol once. Because && tests this condition first, the later column indexing is safe for a finite total input. The column tests establish the remaining Latin-square condition. Filtering therefore retains precisely the valid squares; it does not remove any different ordering of rows, columns or symbols as an alleged symmetry duplicate.
For a nonnegative order, first enumerate every possible row and then every possible ordered selection of rows:
squares :: Int -> [[[Int]]]
squares n
  | n < 0     = error "negative order"
  | otherwise = cp (replicate n (cp (replicate n [1..n])))
Every one of the positions chooses one of symbols independently. Consequently the enumeration contains candidate squares for , each exactly once. The conventional order-zero extension produces one empty square. This is generation only; repeated symbols have not yet been rejected.
The empty family has one choice, the empty selection:
cp :: [[a]] -> [[a]]
cp = foldr extend [[]]
  where
    extend choices suffixes = [x:ys | x <- choices, ys <- suffixes]
A selection from the whole family consists uniquely of a choice from its first member and a selection from the remaining family. This bijection proves the combining equation and completeness by induction. If a member family is empty, there are no selections. The base is [[]], not []: otherwise every Cartesian product would incorrectly be empty.
An unfold expands a seed into either no node or a bucket and two new seeds:
unfoldTree :: (s -> Maybe (s,[a],s)) -> s -> Tree a
unfoldTree split seed =
  case split seed of
    Nothing -> Empty
    Just (left,equal,right) ->
      Node (unfoldTree split left) equal (unfoldTree split right)

toTreeUnfold :: Ord a => [a] -> Tree a
toTreeUnfold = unfoldTree split
  where
    split [] = Nothing
    split (pivot:xs) =
      let (lo,eq,hi) = partition3 pivot xs
      in Just (lo,pivot:eq,hi)
The seed is the remaining list. Expanding a nonempty seed partitions it exactly as toTree does, and both child seeds are shorter. Induction establishes toTreeUnfold = toTree and algorithm termination on finite inputs. The unfold separates the local decomposition rule from the recursive construction of the tree.
A tree fold replaces each constructor by its interpretation:
foldTree :: (b -> [a] -> b -> b) -> b -> Tree a -> b
foldTree combine zero Empty = zero
foldTree combine zero (Node left equal right) =
  combine (foldTree combine zero left)
          equal
          (foldTree combine zero right)

fromTreeFold :: Tree a -> [a]
fromTreeFold = foldTree (\left equal right -> left ++ equal ++ right) []
Induction on the finite tree shows equality with fromTree: the empty tree produces the empty output, and the combining function concatenates the two correctly flattened children around the node's bucket. The result type is independent of the key type; other choices can compute a size or another summary using the same structural recursion.

There are unlisted articles, also show them or only show them.