Use the source's constructor order: left subtree, root value, right subtree.A tree fold replaces the two constructors by an algebra on already folded children. A tree unfold expands a seed either into the empty tree or into a root value and two new seeds. The definitions themselves work on arbitrary binary trees; preserving the binary search tree ordering requires the supplied algebra or seed expansion to respect its bounds.
data Tree a = Tree (Tree a) a (Tree a) | Empty
foldTree :: (b -> a -> b -> b) -> b -> Tree a -> b
foldTree node empty Empty = empty
foldTree node empty (Tree l x r) =
node (foldTree node empty l) x (foldTree node empty r)
unfoldTree :: (s -> Maybe (s,a,s)) -> s -> Tree a
unfoldTree next seed = case next seed of
Nothing -> Empty
Just (ls,x,rs) ->
Tree (unfoldTree next ls) x (unfoldTree next rs)Let be the number of distinct dictionary candidates. A wrong guess is itself a current candidate, but its actual score differs from its score against itself, which has all positions as bulls. Therefore each wrong reply removes at least that candidate while retaining the true secret. There can be at most wrong guesses. A correct guess leaves only the secret consistent with the all-bull reply. Hence every such infinite game's history eventually has the constant tailThis is the finite candidate elimination bound; it assumes a nonempty finite dictionary of fixed-length secrets and a strategy that chooses from the remaining candidates.
The stated end condition is identification, so stop when just one candidate remains, even if it has not been guessed. Replace the worker above byThe scorer can stay
play [] _ = []
play [_] _ = []
play candidates replies =
let g = strategy candidates
in g : case replies of
[] -> []
r:rs -> play [s | s <- candidates, score s g == r] rsmap (score secret): once the guess list ends, its score list ends too. The unchanged game then returns a finite history, with at most rounds; a singleton initial dictionary needs no round. If the identified secret is also wanted as an explicit output, return that sole surviving candidate alongside the history.The score function takes a proposed secret first and a guess second:Assume that the initial dictionary contains the secret, that scores are truthful, and that
mkGuesser :: Eq score
=> (guess -> guess -> score)
-> ([guess] -> guess)
-> [guess] -> [score] -> [guess]
mkGuesser score strategy dictionary = play dictionary
where
play candidates replies =
let g = strategy candidates
in g : case replies of
[] -> []
r:rs -> play [s | s <- candidates, score s g == r] rsstrategy returns a candidate from its nonempty input. The candidate invariant is exactly the dictionary entries consistent with every score already received. Filtering by score s g == r establishes the same invariant after the next reply and retains the true secret.Crucially, the next guess
g is placed under the outer list constructor before replies is inspected. It depends on earlier replies only; the first guess depends on none. This guarded lazy feedback stream makes the mutually recursive game productive whenever the strategy and scoring operations terminate. Moving the case replies outside the constructor would create a circular demand before the first guess.A scorer applies the same scoring rule, with the fixed secret, independently to each guess:The first score depends only on the first guess, and every later score only on the corresponding guess. Thus this player has no unguarded dependence on its own future output when connected to the guesser by a lazy feedback stream. Neither the dictionary nor a strategy is needed by a truthful scorer once the secret and scoring rule are fixed.
mkScorer :: (secret -> guess -> score)
-> secret -> [guess] -> [score]
mkScorer score secret = map (score secret)Use a distinct constructor for each mark, and reserve every bull before allocating any cow:The multiset
data Mark = Bull | Cow | Miss deriving (Eq,Show)
scoreWordle :: Eq a => [a] -> [a] -> [Mark]
scoreWordle secret guess = mark pairs pool
where
pairs = zip secret guess
pool = [s | (s,g) <- pairs, s /= g]
mark [] _ = []
mark ((s,g):ps) available
| s == g = Bull : mark ps available
| otherwise = case pluck g available of
Nothing -> Miss : mark ps available
Just rest -> Cow : mark ps restpool contains exactly the unused secret tokens after all bulls have been set aside. The recursive invariant is that available contains those tokens not yet allocated to cows. A successful pluck consumes one, and failure leaves the pool unchanged. This proves both multiplicity correctness and the priority of bulls over cows. Among duplicate non-bull guess tokens, the leftmost eligible ones receive cows. For secret "alpha" and guess "aaabb", the result is [Bull,Cow,Miss,Miss,Miss]. This implements duplicate-aware positional scoring.First remove a single matching token, so duplicates cannot be reused:Equal game lengths are assumed. For each token,
pluck :: Eq a => a -> [a] -> Maybe [a]
pluck _ [] = Nothing
pluck x (y:ys)
| x == y = Just ys
| otherwise = case pluck x ys of
Nothing -> Nothing
Just zs -> Just (y:zs)
overlap :: Eq a => [a] -> [a] -> [a]
overlap [] _ = []
overlap (x:xs) ys = case pluck x ys of
Nothing -> overlap xs ys
Just zs -> x : overlap xs zs
scoreBC :: Eq a => [a] -> [a] -> (Int,Int)
scoreBC secret guess = (bulls, matches - bulls)
where
bulls = length [() | (s,g) <- zip secret guess, s == g]
matches = length (overlap guess secret)overlap retains exactly the smaller of its two multiplicities, so its length is the multiset overlap. It never spends a secret occurrence twice. Positional matches account for bulls; after reserving them, each token's remaining possible matches decrease by exactly its bull count. Hence matches - bulls counts precisely the cows. The source example gives (1,1). With equality as the only operation on tokens, these definitions take time for length .For finite, fully defined representations, yes; for arbitrary infinite ones in Haskell, no. At the level of mathematical occurrence sets, splitting by parity, dividing by two, and then applying the inverse index transformations recovers every original position exactly once. Thus the equality holds on finite total position lists.
For a proper infinite representation, take the alternating Boolean sequence, represented byThis is a total representation: both queries return productive infinite occurrence lists. Butfilters for odd indices in uses
alternating :: Seq Bool
alternating False = [0,2..]
alternating True = [1,3..]odds alternating False[0,2..], so it produces no outer constructor and denotes . The callilv (evens alternating) (odds alternating) FalsemergePos to inspect both transformed lists before emitting its first result; it therefore also diverges. In contrast, alternating False starts with 0. Applying head distinguishes the two. The productivity failure is real even though the mathematical position-set identity is correct; the hypothesis that the input properly represents an infinite sequence does not remove it.Define the ordered merge algorithm explicitly:The first sequence occupies even positions and the second occupies odd positions. Within each transformed list, order is preserved; merging puts all positions for a queried token into increasing order. The two transformed lists have disjoint parities, so equality cannot occur between their heads on valid inputs. The length assumption ensures that these positions describe the intended interleaved sequence without a gap at its finite end.
mergePos :: [Integer] -> [Integer] -> [Integer]
mergePos [] ys = ys
mergePos xs [] = xs
mergePos xs@(x:xt) ys@(y:yt)
| x <= y = x : mergePos xt ys
| otherwise = y : mergePos xs yt
ilv :: Seq a -> Seq a -> Seq a
ilv s t v = mergePos (map (2*) (s v))
(map (\j -> 2*j+1) (t v))Even and odd original positions become consecutive new positions:An occurrence at belongs to
evens :: Seq a -> Seq a
evens s v = map (`div` 2) (filter even (s v))
odds :: Seq a -> Seq a
odds s v = map (`div` 2) (filter odd (s v))evens at position ; one at belongs to odds at position . Thus the formulas preserve increasing position order and produce the specified finite examples. For infinite occurrence lists, filtering can search forever when no further position of the chosen parity exists. Consequently these otherwise direct formulas need not preserve productivity for every query.The most informative occurrence-position representation of a sequence of natural numbers isEach nonnegative integer occurs once at its own index, and negative integers never occur.
naturals :: Seq Integer
naturals v
| v < 0 = []
| otherwise = [v]This is not equal to
rep [0..] under lazy evaluation. For a nonnegative query v, rep eventually emits v, but then searches forever for another occurrence: its result has the shape v : undefined, rather than the terminating singleton [v]. For a negative query, even the outer constructor is never produced, whereas naturals immediately returns [].No general, correct
rep :: Eq a => [a] -> Seq a can always certify those absences from an arbitrary infinite input. A terminating certification has inspected only finitely many elements, and the same prefix could be followed by the supposedly absent value, or by a further occurrence of it. Extra knowledge changes the problem: for a promised strictly increasing integer input, a search can stop with [] when it first exceeds the query and return [i] immediately upon equality. That specialised representation can produce naturals; a generic search cannot. This is the absence-detection obstruction for infinite lists.With nonpositive counts treated as in the standard list operations:An occurrence survives
takeSeq :: Integer -> Seq a -> Seq a
takeSeq n s
| n <= 0 = const []
| otherwise = \v -> takeWhile (< n) (s v)
dropSeq :: Integer -> Seq a -> Seq a
dropSeq n s
| n <= 0 = s
| otherwise = \v -> map (subtract n) (dropWhile (< n) (s v))takeSeq n exactly when its original index is less than , and its index stays unchanged. It survives dropSeq n exactly when its original index is at least , and its new index is the original one minus . Sorted occurrence lists justify takeWhile and dropWhile. No equality constraint on the element type is needed because the operations only transform positions. The first guard also lets takeSeq 0 s v return [] without inspecting s v.Use arbitrary-precision integers for positions, avoiding overflow on infinite sequences:The type synonym
type Seq a = a -> [Integer]
rep :: Eq a => [a] -> Seq a
rep xs v = [i | (i,x) <- zip [0..] xs, x == v]Seq a needs no equality constraint; the equality test is required specifically by rep. The list comprehension visits input positions in increasing order, so the output is an increasing list of precisely the matching positions. For finite inputs this includes a terminating empty list when the value is absent. Infinite inputs require the additional productivity distinctions discussed below. This is an occurrence-position representation of a sequence.inits is not a direct list fold: inits undefined = [] : undefined has a defined outer constructor, while foldr c z undefined is .Both For
pinits and ninits are direct list folds:pinitsFold :: [a] -> [[a]]
pinitsFold = foldr (\x yss -> [] : map (x:) yss) []
ninitsFold :: [a] -> [[a]]
ninitsFold = foldr (\x yss -> [x] : map (x:) yss) []pinits, the combining function is exactly the recursive step above. For ninits, expand inits xs = [] : ninits xs and useNeither step needs to inspect yss before producing its first outer constructor. Thus the definitions satisfy the fold factorisation criterion on partial as well as total lazy lists.For prefixes of a list, the corresponding Haskell definitions areThe empty prefix is available without inspecting the input in
inits :: [a] -> [[a]]
inits xs = [] : ninits xs
pinits :: [a] -> [[a]]
pinits [] = []
pinits (x:xs) = [] : map (x:) (pinits xs)
ninits :: [a] -> [[a]]
ninits [] = []
ninits (x:xs) = map (x:) (inits xs)inits. Every nonempty prefix of a list begins with its input's head, explaining the last equation. For pinits (x:xs), prepend x only to proper prefixes of xs, and include the empty prefix.On finite inputs,
inits [] = [[]], whereas both other functions return []. On an infinite input, all finite prefixes are proper and these definitions produce them incrementally. Fully constructing all elements of all prefixes takes work for an input of length , matching the size of that output; there are no repeated end-append operations to add another factor.tails is not a direct list fold. Every foldr c z is strict in its list argument, but tails undefined = undefined : undefined has a defined outer constructor. Applying null distinguishes this result from .ptails is not a direct list fold either. On a type with distinct values u and v,A fold step given the same new head x and these equal folded tails must return the same result. However,Thus the tail information needed by the next step does not factor through ptails; this violates the fold factorisation criterion even on finite total lists.ntails is a direct list fold:ntailsFold :: [a] -> [[a]]
ntailsFold = foldr step []
where
step x yss = (x : original yss) : yss
original [] = []
original (ys:_) = ys[]. Hence original (ntailsFold xs) = xs. The inner case distinction is delayed beneath constructors, so the definition also preserves the required behaviour on partial and infinite lazy lists. Building a suffix head does not first demand the whole folded tail.Use these structural recursion definitions in Haskell:The first definition returns a known outer constructor even when
tails :: [a] -> [[a]]
tails xs = xs : ptails xs
ptails :: [a] -> [[a]]
ptails [] = []
ptails (_:xs) = tails xs
ntails :: [a] -> [[a]]
ntails [] = []
ntails xs@(_:rest) = xs : ntails restxs is undefined, so null (tails undefined) is False, as required. The pattern in ntails must first determine whether the input is empty. Each suffix of a list is shared with the original list; on a finite input of length , constructing the outer lists takes work and additional outer-list space. No suffix is copied or measured repeatedly.The list fold criterion is: there must be a value
z and a definable combining function c such thatThe last equality says that all information needed about the tail factors through f xs; the combining function receives no other access to xs. These conditions give f = foldr c z.Necessity follows from the defining equations of
foldr, including its case distinction on the input list. Sufficiency follows by structural induction for finite lists and finite partial-list approximations. For infinite or partial lazy lists, the usual continuous semantics of these definable functions extends equality from the approximations to their limit. The strictness condition matters: agreement only on finite total lists does not establish agreement at . This is the fold factorisation criterion.A strict function satisfies , where is the bottom value representing an undefined or nonterminating computation. This is a semantic implication: obtaining a defined result requires enough definedness of the argument. It does not prescribe an evaluation order or say that every component of a structured argument is evaluated.[ref]
For example, in Haskell,is strict, since every result is , but never needs to inspect its argument. Moreover, lazy evaluation may leave an entire application unevaluated when its result is unused. Strictness is therefore different from the operational statement that an argument is evaluated on every call.
f :: a -> b
f _ = undefined There are unlisted articles, also show them or only show them.