Greg Buchholz wrote:
Keean Schupke wrote:
I dont see why this is illegal... what do we want? take the top two items from the stack?
With the code below (direct translation from tuples to HLists) I still get an occurs check error when trying to define fact5...
Okay the reason is that types in the code end up depending on values. The type of the stack changes when items are pushed or popped. So the type of the stack returned from recursive functions depends on the recursion count... Haskell is not dependantly typed, so cannot deal with types that "depend" on values. This is why your code with tuples, and the HList code (which is really doing the same thing through a defined API) both fall down on the recursion. One solution is to make all elements the same type and use lists... like: data Elem = ElemInt Int | ElemChar Char... But this looses any static type checking. The alternative is to lift the "values" to the type level, using something like Peano numbers to represent naturals: data HZero = HZero data HSucc x = HSucc x Now different values have explictly different types, so we can have types which depend on them... Attached is an example implementation of "times" using this technique and the HList library (its not debugged... so there might be some mistakes). Keean.