Merge the rows with
fairConcat, retaining explicit empty-input cases:fairPair :: (a -> b -> c) -> [a] -> [b] -> [c]
fairPair _ [] _ = []
fairPair _ _ [] = []
fairPair f xs ys = fairConcat [[f x y | y <- ys] | x <- xs]For nonempty proper lazy lists, the occurrence
f (xs!!i) (ys!!j) belongs to row , position , so the proof in part d puts it in round . This supplies every pair after finite work, even when both input lists are infinite. The guards also return [] for either empty factor without traversing infinitely many empty rows.The ordinary list comprehension exhausts the inner list before advancing the outer one. Therefore it enumerates every argument pair when
ys is finite, or when xs has at most one element. If ys is infinite and xs has two or more elements, it stays with the first outer element forever and misses every pair with a later outer occurrence. Applying a constant f might hide missing pairs as duplicate values; it does not make the enumeration fair.An empty-result caveat remains when
ys = [] and xs is infinite: the literal comprehension traverses infinitely many empty rows and does not return a terminating empty list. Its occurrence requirement is vacuous, but its productivity as an empty-result computation fails. An explicit empty-input test avoids that particular failure.Use diagonal merging of lazy lists: introduce one new row each round, and advance every active row once. Each round contains finitely many active rows, even when the outer list is infinite.
fairConcat :: [[a]] -> [a]
fairConcat = concat . levels []
where
levels [] [] = []
levels active pending =
let (new,rest) = case pending of
[] -> ([],[])
r:rs -> ([r],rs)
live = [r | r@(_:_) <- active ++ new]
in map head live : levels (map tail live) restNumber rows and positions within each row from zero. An occurrence at is emitted in round : its row enters in round and advances once per subsequent round. All earlier rounds and each round's output are finite, so every required occurrence appears after finite work.
live discards only empty rows, and head emits only existing entries; no new value is invented.Simply nesting
interleave is unsafe here: foldr interleave [] ([1,2] : repeat []) emits 1 and then demands an undefined merge of the infinitely many empty rows before it can emit 2. The finite-round construction avoids that starvation. There is still an unavoidable termination qualification: after the last actual output, infinitely many empty pending rows cannot be certified empty in finite work. The result can then have an undefined tail instead of a terminating []. Every required occurrence has nevertheless appeared; no generic algorithm can promise a proper completed output in that exceptional situation, by the absence-detection obstruction for infinite lists.No universally correct sequential Haskell implementation has that guarantee for partial lists. Compare
undefined paired with [v], and [v] paired with undefined, where the element type is arbitrary. A generic program cannot fabricate v; it must eventually inspect an input spine to obtain it. Whichever input it first demands can be chosen to be the undefined one, blocking access to the available element in the other input.In particular, the implementation in part b can emit a defined prefix and then block when alternation reaches an undefined tail. Lazy evaluation postpones demands; it cannot recognize that a demanded computation will never finish. The result is the partial-list interleaving obstruction, not an objection to fairness under the proper-input hypothesis. Additional concurrent primitives would change the computational model.[ref]
Haskell 2010 Language Report. §3.1, errors and nontermination; §3.17, demands made by pattern matching
Swap roles after emitting one element:
interleave :: [a] -> [a] -> [a]
interleave [] ys = ys
interleave (x:xs) ys = x : interleave ys xsWhile both lists are nonempty, the function alternates between them. Their -th input occurrences appear after at most output steps, counting positions from zero; once either list ends, the other is returned directly. Every output constructor comes from one input constructor, and every input occurrence is eventually selected. This proves fair enumeration and productivity on the two proper lazy lists, including two infinite ones.
For proper lazy lists, the generic condition is a finite first list, or an empty second list. A finite first list reaches its terminating constructor, after which list concatenation exposes the second one. An infinite first list never yields control to the second; it therefore cannot deliver occurrences originating there unless there are none. This concerns input occurrences, rather than an accidental overlap of the two inputs' value sets.
Different move orders can lead to the same position, and the two occupancy lists also retain irrelevant insertion order. Thus this search tree repeatedly solves the same remaining game. For example, swapping the order of two
O moves while leaving the intervening X moves legal can reach the same occupied sets.Canonicalize each state by sorted occupancy sets, or by two bitboards, and apply memoization or a visited-state set. Expand each canonical position once, stopping at terminal states, and collect terminal positions in a set. There are at most cell assignments, many of which are illegal; this is much smaller than a tree of move permutations. Store positions, not histories, when the requested output is distinct final positions. Board rotations and reflections can reduce work further if handled as an additional equivalence: if the output must retain every oriented board, reconstruct those distinct orientations rather than silently returning one representative per symmetry class.
Record the outcome at the first completed board and otherwise branch over every available move:
data Outcome = Winner Player | Draw deriving (Eq,Ord,Show)
finals :: Board -> [(Board,Outcome)]
finals b@(os,xs,es)
| won os = [(b,Winner O)]
| won xs = [(b,Winner X)]
| null es = [(b,Draw)]
| otherwise = concatMap (\q -> finals (play b q)) esThe recursion terminates because each recursive call decreases the number of empty positions by one. For correctness, induct on that number. A completed board contributes exactly its own outcome. Otherwise every legal continuation has a unique first available move, and the induction hypothesis covers exactly all completions after that move. List concatenation collects these branches without extending completed games. Repeated final positions are allowed here because the computation deliberately explores every legal move sequence.
Construct each possible winning line, then test whether one is contained in the player's occupancy set:
winningLines :: [Places]
winningLines =
[[(r,c) | c <- [0..2]] | r <- [0..2]] ++
[[(r,c) | r <- [0..2]] | c <- [0..2]] ++
[[(i,i) | i <- [0..2]], [(i,2-i) | i <- [0..2]]]
won :: Places -> Bool
won ps = any (\line -> all (`elem` ps) line) winningLinesThe list comprehension generates three rows, three columns and two diagonals. Each has exactly three coordinates; therefore
all holds precisely when every coordinate of that line is occupied by this player. Taking any over the eight lines proves the win test correct.Assume the board satisfies the representation invariant. Reject completed boards and occupied or out-of-range coordinates; testing membership in the empty component covers both coordinate failures.
finished :: Board -> Bool
finished (os,xs,es) = won os || won xs || null es
play :: Board -> Place -> Board
play b@(os,xs,es) q
| finished b = error "play: completed game"
| q `notElem` es = error "play: unavailable place"
| length os == length xs = (q:os,xs,rest)
| otherwise = (os,q:xs,rest)
where rest = filter (/=q) esHere
won is defined in part d. Moving one available coordinate into the appropriate occupied component preserves the set partition and the alternating-count rule. Checking completion first preserves the no-moves-after-a-win invariant.The empty occupancy sets leave all nine coordinates available:
empty :: Board
empty = ([],[],[(r,c) | r <- [0..2], c <- [0..2]])This board satisfies the representation invariant and gives
O the next move.Use coordinates with row and column in :
type Place = (Int,Int)
type Places = [Place]
type Board = (Places,Places,Places)
data Player = O | X deriving (Eq,Ord,Show)The components of
Board record the positions occupied by O, occupied by X, and still empty, respectively. On a nonterminal legal board, equal occupied counts mean O moves next; one extra O means X moves next.The type synonym does not enforce the representation invariant: coordinates are in range; each component has no duplicates; the three represented sets form a set partition of the nine positions; and the occupied counts differ as just described. Both players cannot have won. A winning
O board has one extra O, and a winning X board has equal counts. More fundamentally, a legal tic-tac-toe state has a legal alternating history that stops at the first win: satisfying a type alone never licenses continuing an already completed game.buildUnfold :: [a] -> Tree a
buildUnfold = unfold step
where
step [] = error "build: empty input"
step [x] = Left x
step xs = Right (split (length xs `div` 2) xs)On a singleton seed,
unfold produces the same leaf as build; on a longer finite seed, it recursively builds the same two pieces. Induction on input length proves buildUnfold = build on finite nonempty inputs. The empty-input qualification remains essential: a tree unfold cannot supply a missing empty-tree constructor.The necessary domain is a finite, nonempty list: the datatype has no representation of an empty leaf sequence, and the supplied size-based balance condition does not specify an infinite-size construction.
build :: [a] -> Tree a
build [] = error "build: empty input"
build [x] = One x
build xs = Two (build ys) (build zs)
where
(ys,zs) = split (length xs `div` 2) xsFor length , the two nonempty pieces have and elements. Their sizes differ by at most one, and both are shorter than the input. Induction therefore proves termination and the required leaf-balanced binary tree property at every node. The same induction, using
ys ++ zs = xs, proves flatten (build xs) = xs. This straightforward implementation takes running time; computing the length repeatedly is acceptable here because no faster construction was requested.Let be the number of leaves; the total number of nodes is . List concatenation copies its left operand. For a tree whose left subtree contains leaves at each successive internal node, these copied lengths are . Their sum is , so the worst-case running time is .
A difference list representation avoids copying prefixes:
flattenFast :: Tree a -> [a]
flattenFast t = go t []
where
go (One x) acc = x:acc
go (Two l r) acc = go l (go r acc)The recursion invariant is
go t acc = flatten t ++ acc. The leaf case is immediate; the internal-node case uses associativity of list concatenation. Each node is visited once and each leaf contributes one output constructor, giving running time when the result is fully consumed. This is linear flattening of a binary tree and does not assume balance.Both versions preserve left-to-right leaf order:
flatten :: Tree a -> [a]
flatten (One x) = [x]
flatten (Two l r) = flatten l ++ flatten r
flattenFold :: Tree a -> [a]
flattenFold = foldTree (\x -> [x]) (++)The tree fold replaces each leaf by a singleton list and each internal node by list concatenation. The defining equations of
flattenFold are consequently those of flatten, proving their equality by structural induction.For the paper's leaf-labelled binary tree, the combining operation receives the results of the two subtrees, and the other argument handles a leaf:
foldTree :: (a -> b) -> (b -> b -> b) -> Tree a -> b
foldTree f g (One x) = f x
foldTree f g (Two l r) = g (foldTree f g l) (foldTree f g r)Its constructor equation is
foldTree One Two = id. More generally, a function h satisfying h (One x) = f x and h (Two l r) = g (h l) (h r) equals foldTree f g on finite trees, by structural induction. This is the tree fold specialized to a datatype with labels only at leaves, rather than at internal nodes.split :: Int -> [a] -> ([a],[a])
split n xs | n <= 0 = ([],xs)
split _ [] = ([],[])
split n (x:xs) = (x:ys,zs)
where (ys,zs) = split (n-1) xsFor a defined count and a spine with available constructors before termination, each of
take and drop makes recursive calls, whereas split makes that many once. The number of recursive calls is halved. The irrefutable pattern in the local pair binding also avoids evaluating the recursive pair merely to expose the first output element.On proper lazy lists this has the intended two component values. There is a small bottom value distinction outside that domain: the displayed single-pass definition must inspect a positive-count input spine before returning its outer pair, whereas the literal expression
(take n xs, drop n xs) exposes the pair constructor even if xs is undefined. The algorithmic answer concerns the two components and the stated call count; it need not silently claim equality under a test that observes this outer constructor alone.Include nonpositive counts and exhausted input explicitly:
take :: Int -> [a] -> [a]
take n _ | n <= 0 = []
take _ [] = []
take n (x:xs) = x : take (n-1) xs
drop :: Int -> [a] -> [a]
drop n xs | n <= 0 = xs
drop _ [] = []
drop n (_:xs) = drop (n-1) xsThe tests on the count precede inspection of the input list. Thus
take 0 undefined = [], while drop 0 undefined = undefined, exactly as these list prefix and list suffix operations require. No element value is inspected merely to traverse the spine.[ref]Haskell 2010 Language Report. Chapter 9, PreludeList: take and drop
Fix
s and put . The right fold equations giveThese are exactly the left fold equations. Structural induction, with the induction hypothesis quantified over all accumulators, proves equality on finite terminating lists.To include the other input spines, first observe that both applied expressions give on an undefined spine. The same induction proves equality on every finite prefix ending in : the step
k s x f a demands the continuation f when its result is demanded. Finally use that the two applied operations are Scott continuous maps, taking the limit over prefixes interpreted as a finite approximation of a lazy list. This covers infinite spines, on which both applied expressions are , and proves the identity for all lists under the stated Haskell semantics. The intermediate right fold builds an accumulator-transforming function; it does not provide a terminating left fold of an infinite list. There are unlisted articles, also show them or only show them.
