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

Greg Buchholz haskell at sleepingsquirrel.org
Tue Mar 8 17:16:32 EST 2005

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...

Compiling Main             ( joy3.hs, interpreted )

    Occurs check: cannot construct the infinite type: l = HCons e l
        Expected type: HCons
                           (HCons e (HCons e l) -> HCons e l)
                                (HCons e3 l3 -> HCons e3 (HCons e3 l3))
                                     (HCons e1 l2 -> HCons e1 l2)
                                     (HCons (HCons e2 l1 -> HCons Bool l1) a)))
                       -> c
        Inferred type: HCons
                           (HCons e (HCons e l) -> HCons e (HCons e l))
                                (l4 -> l4)
                                (HCons (l4 -> HCons e (HCons e l))
(HCons (l4 -> l5) l4)))
                       -> HCons e (HCons e l)
    In the second argument of `(!)', namely `linrec'
    In the definition of `fact5':
        fact5 = ((((quote (nul)) ! (quote (suc))) ! (quote (dup ! pre)))
                 ! (quote (mult)))
                ! linrec
Failed, modules loaded: MainGhcGeneric1, TypeCastGeneric1, Label3,
TypeEqGeneric1, TypeEqBoolGeneric, GhcExperiments, GhcSyntax,
CommonMain, Datatypes2, Variant, TIC, TIP, HTypeIndexed, GhcRecord,
Record, HZip, HOccurs, HArray, HListPrelude, FakePrelude.

    Looks to me like a very similar error to the tuple case.

Greg Buchholz

--Joy combinators in Haskell
{-# OPTIONS -fglasgow-exts #-}
{-# OPTIONS -fallow-overlapping-instances #-}

import MainGhcGeneric1
import Data.Typeable

main = do   print $ ((lit 10)!(lit 4)!mult) bot  -- 4*10
            print $ ((lit 3) ! cube ) bot        -- 3^3
            print $ ((lit 4) ! fact5) bot        -- 4!

bot = HNil
square = dup ! mult
cube   = dup ! dup ! mult ! mult
nul = (lit 0) ! eq
suc = (lit 1) ! add
pre = (lit 1) ! sub

--In Joy:  [null]  [succ]  [dup pred]  [*]  linrec
fact5 :: HCons Integer a -> HCons Integer a
fact5 = quote(nul) ! quote(suc) ! quote(dup ! pre) ! quote(mult) ! linrec

--primitive combinators
(!) f g = g.f
i    (a, b)      = (a b)
add  (HCons a (HCons b c)) = (HCons (b+a) c)
sub  (HCons a (HCons b c)) = (HCons (b-a) c)
mult (HCons a (HCons b c)) = (HCons (b*a) c)
swap (HCons a (HCons b c)) = (HCons b (HCons a c))
pop  (HCons a b)           =  b
dup  (HCons a b)           = (HCons a (HCons a b)) 
dip  (HCons a (HCons b c)) = (HCons b, (a  c)) 
eq   (HCons a (HCons b c)) | a == b    = (HCons True c)
                           | otherwise = (HCons False c)

ifte (HCons f (HCons t (HCons b stack))) 
      | hHead(b stack) = (t stack)
      | otherwise      = (f stack)

linrec (HCons rec2 (HCons rec1 (HCons t (HCons p stack))))
      | hHead (p stack) = (t stack)
      | otherwise       = rec2 (linrec (HCons rec2 
                                       (HCons rec1 
                                       (HCons t 
                                       (HCons p (rec1 stack))))))

lit val stack = (HCons val stack)
quote = lit

More information about the Haskell-Cafe mailing list