CODEWITHSUNDEEP
haskelltypes
MaiaVictor
MaiaVictor

Reputation: 52987

Is there any way to make this Church-encoded program compile?

{-# LANGUAGE RankNTypes, ScopedTypeVariables, NoMonomorphismRestriction #-}

type CList a = (forall t . (a -> t -> t) -> t -> t)

ccons :: forall a . a -> CList a -> CList a
ccons h t = (\ c n -> c h (t c n))

cnil :: forall h . CList h
cnil = (\ c n -> n)

cToList :: forall a . CList a -> [a]
cToList list = list (:) []

cFromList :: forall a . [a] -> CList a
cFromList = foldr ccons cnil

main = print (cToList (cFromList [1,2,3]))

I understand the reason it doesn't compile has to do with the usage of forall on ccons. Commenting the ccons type will make it compile, but with an awkward type for ccons. What is the right way to fix it?

test.hs:15:23:
    Couldn't match type ‘(a -> t -> t) -> t -> t’
                   with ‘forall t1. (a -> t1 -> t1) -> t1 -> t1’
    Expected type: a
                   -> ((a -> t -> t) -> t -> t) -> (a -> t -> t) -> t -> t
      Actual type: a -> CList a -> (a -> t -> t) -> t -> t
    Relevant bindings include
      cFromList :: [a] -> CList a (bound at test.hs:15:5)
    In the first argument of ‘foldr’, namely ‘ccons’
    In the expression: foldr ccons cnil

Upvotes: 0

Views: 93

Answers (2)

MaiaVictor
MaiaVictor

Reputation: 52987

As pointed by @Daniel Wagner, merely using newtype instead of type solves the issue:

newtype CList a = CList { runCList :: (forall t . (a -> t -> t) -> t -> t) }

ccons :: forall h . h -> CList h -> CList h
ccons h t = CList (\ c n -> c h (runCList t c n))

cnil :: forall h . CList h
cnil = CList (\ c n -> n)

cToList :: forall a . CList a -> [a]
cToList list = runCList list (:) []

cFromList :: forall a . [a] -> CList a
cFromList list = (foldr ccons cnil list)

main = print (cToList (cFromList [1,2,3]))

Also apparently I was told this before but I really can not remember nor find the question. Sorry guys :(

Upvotes: 2

Michael
Michael

Reputation: 2909

Why are you using ccons at all? cFromList is just a flipped foldr

cFromList ::  [a] -> CList a
cFromList xs op seed = foldr op seed xs

Upvotes: 3

Related Questions