[Haskell-cafe] Joy Combinators (Occurs check: infinite type)
k.schupke at imperial.ac.uk
Wed Mar 9 07:20:03 EST 2005
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
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
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
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
HList library (its not debugged... so there might be some mistakes).
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 2357 bytes
Desc: not available
Url : http://www.haskell.org//pipermail/haskell-cafe/attachments/20050309/47280f82/Joy.bin
More information about the Haskell-Cafe