# Собачка

Paradigm(s) String-rewriting User:Hakerh400 2022 Unknown Implemented .txt

Собачка is a string-rewriting esolang invented by User:Hakerh400 in 2022.

## Overview

Source code consists of a list of decimal digits. The interpreter rewrites the list until the program halts. The output is a single digit.

## Rewriting rules

Repeat this until the program halts. If the list is empty, output digit 0 and halt. If the list contains exactly one digit, output that digit and halt. Otherwise, rewrite the list using the following algorithm.

For each two consecutive digits ${\displaystyle a}$ and ${\displaystyle b}$:

• If ${\displaystyle a+b\leq 9}$, produce list [a + b]
• Otherwise, if ${\displaystyle a=b}$, produce list [a]
• Otherwise, if ${\displaystyle a, produce list [1, a + b - 10]
• Otherwise produce an empty list

Concatenate all productions in order. It represents the new list of digits.

## Example

Program:

4866857774615622223321


Computation steps:

4866857774615622223321
12614127710761184445653
38755397817729889118
1158121598791181729
2613933614162998911
874126975578119172
5381551215921089
81196563361431817
9210119697574998
3112101512139
4233116633412
656427696753
116915138
271566411
98611652
7277
997
9


The output is 9.

## Implementation

type N = Integer
infixr 0 #
(#) = id

xs :: [N]
xs = [1, 2, 3, 4, 5]

f :: N -> N -> [N]
f a b = let c = a + b in
if c <= 9 then [c] else
if a == b then [a] else
if a < b then [1, c - 10]
else []

step :: [N] -> [N]
step xs = concat # zipWith f xs # tail xs

run :: [N] -> [[N]]
run xs = if null xs then [[0]] else
xs : if length xs == 1 then [] else run # step xs

main :: IO ()
main = mapM_ (putStrLn . (>>= show)) # run xs


## Computational class

We conjecture that this language is total.