hs.py

class Empty:
    def __init__(self):
        pass

    def __repr__(self):
        return '[]'

    def reduce(self):
        yield Empty()


class Char:
    def __init__(self, x):
        self.x = x

    def __repr__(self):
        return self.x

    def reduce(self):
        yield Char(self.x)


class Add:
    def __init__(self, x, s):
        if isinstance(x, str):
            x = Char(x)
        self.head = x
        self.tail = s

    def __repr__(self):
        return f'{self.head} : {self.tail}'

    def reduce(self):
        curr = self
        for i in self.head.reduce():
            curr = Add(i, curr.tail)
            yield curr
        for i in self.tail.reduce():
            curr = Add(curr.head, i)
            yield curr


class init:
    def __init__(self, s):
        self.s = s

    def __repr__(self):
        return f'init({self.s})'

    def reduce(self):
        s = self.s
        if isinstance(s, Empty):
            raise Exception("Init on empty list")
        if isinstance(s, Add):
            if isinstance(s.tail, Empty):
                res = Empty()
            elif isinstance(s.tail, Add):
                res = Add(s.head, init(s.tail))
            else:
                for i in s.tail.reduce():
                    res = init(Add(s.head, i))
                    yield res
                yield from res.reduce()
                return
        else:
            for i in s.reduce():
                res = init(i)
                yield res
            yield from res.reduce()
            return
        yield res
        yield from res.reduce()


class rev_helper:
    def __init__(self, t, a):
        self.t = t
        self.a = a

    def __repr__(self):
        return f"rev'({self.t}, {self.a})"

    def reduce(self):
        if isinstance(self.t, Empty):
            res = self.a
        elif isinstance(self.t, Add):
            res = rev_helper(self.t.tail, Add(self.t.head, self.a))
        else:
            for i in self.t.reduce():
                res = rev_helper(i, self.a)
                yield res
            yield from res.reduce()
            return
        yield res
        yield from res.reduce()


class rev:
    def __init__(self, xs):
        self.xs = xs
    def __repr__(self):
        return f'rev({self.xs})'
    def reduce(self):
        res = rev_helper(self.xs, Empty())
        yield res
        yield from res.reduce()


def evaluate(expr):
    prev = None
    print(repr(expr))
    for state in expr.reduce():
        i = repr(state)
        if i != prev:
            print(i)
            prev = i

evaluate(
    init(rev(init(
        Add('с', Add('т', Add('у', Add('д', Add('е', Add('н', Add('т', Empty())))))))
    )))
)