[Haskell-cafe] Joy Combinators (Occurs check: infinite type)

Keean Schupke 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 
and the
HList library (its not debugged... so there might be some mistakes).


-------------- next part --------------
A non-text attachment was scrubbed...
Name: Joy.hs
Type: text/x-haskell
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 mailing list