Collect the matching replacements and distinguish all three possible multiplicities:The list comprehension selects precisely the rules whose left-hand character is
applyRule :: [Rule] -> Char -> String
applyRule rules c =
case [replacement | (key, replacement) <- rules, key == c] of
[] -> error ("no rule for " ++ [c])
[result] -> result
(_:_:_) -> error ("multiple rules for " ++ [c])c. A singleton is the required unique match. The third branch also rejects duplicate rules with identical right-hand sides: there are still two matching rules. Finiteness of the rule list makes the uniqueness test decidable. The returned replacement may itself be empty.Apply one replacement to each original character and concatenate the results:The concatMap operation combines a map function and list concatenation. Replacements occur in original-character order, so a character produced by a replacement is not processed again during the same step. This is parallel string rewriting. In particular
step :: [Rule] -> State -> State
step rules = concatMap (applyRule rules)step rules "" = "", with no rule lookup required for the empty state.Generate successive states lazily and take exactly their initial nonempty segment:The iterate function starts with
runSystem :: (State, [Rule]) -> [State]
runSystem (state, rules) =
takeWhile (not . null) (iterate (step rules) state)state itself and repeatedly applies step rules. The takeWhile function excludes the first empty state and everything after it. If the initial state is empty, the result is []. If the process never reaches an empty state, the answer is a potentially infinite list whose finite prefixes can be observed through lazy evaluation. No artificial maximum number of rewriting steps is introduced.The principal type needs an equality type class constraint:The empty list is a prefix of every list, witnessed by the second list itself as the remaining suffix. A nonempty prefix cannot fit in the empty list. Otherwise the first elements must agree, and the remaining first list must be a prefix of the remaining second list. These cases prove correctness by structural induction on the candidate prefix. The
isPrefix :: Eq a => [a] -> [a] -> Bool
isPrefix [] _ = True
isPrefix (_:_) [] = False
isPrefix (x:xs) (y:ys) = x == y && isPrefix xs ysEq a constraint is required by x == y; no ordering constraint is needed.Attach zero-based indices before filtering:The zip function pairs each state with its position in the original sequence. The list comprehension retains exactly those pairs satisfying the prefix test, preserving their order and their original indices. The declared result makes
findStates :: [State] -> String -> [(State, Integer)]
findStates states str =
[(state, i) |
(state, i) <- zip states [0..],
isPrefix str state][0..] a stream of Integer indices. An empty search string matches every state, including an empty state, because the empty list is a prefix of every list. Articles by others on the same topic
There are currently no matching articles.