3 ms·
I believe GHC's type system is also Turing complete. As an example, you can implement BrainFuck in the GHC type system. I haven't looked over the details, but
by Periodic 17y ago
I believe GHC's type system is also Turing complete. As an example, you can implement BrainFuck in the GHC type system. I haven't looked over the details, but it looks promising.
http://killersmurf.blogspot.com/2009/11/typefuck.html http://killersmurf.blogspot.com/2009/11/typefuck.html
- camccann 17y agoType-level computation is actually quite limited by default in GHC; it becomes quasi-Turing-complete only when using the UndecidableInstances extension, and even then it has a very shallow stack by default, though you can increase it if you want deeper recursion. If memory serves me, Oleg Kiselyov has a type-level implementation of the untyped lambda calculus, which is rather more pleasant than brainfuck.