Comment by marvinborner

14 hours ago

> Scott-Mogensen encoding

just Scott encoding, Scott-Mogensen refers to a meta encoding of LC in LC. Scott's encoding is fine but requires fixpoint recursion for many operations as you said.

Interestingly though, Mogensen's ternary encoding [1] does not require fixpoint recursion and is the most efficient (wrt being compact) encoding in LC known right now.

> Just use [..], seriously

do you have any further arguments for Scott's encoding? There are many number encodings with constant time predecessor, and with any number requiring O(n) space and `add` being this complex, it becomes quite hard to like

[1]: https://dl.acm.org/doi/10.5555/646802.705958

0 comments

marvinborner

Reply