Getting an error: parse error on input ‘Just’

Question

data Type = Nat | Bool | App Type Type | Var String 
     deriving (Eq, Show)

type Substitution = [(String, Type)]

apply :: Substitution -> Type -> Type
apply s Nat = Nat
apply s Bool = Bool
apply s Var c = case (lookup s c) of 
                Nothing -> (Var c)
                Just v  ->  v

But the compilers give me the error "error: parse error on input ‘Just’ "

What am I doing wrong?

Answer 1

I can not reproduce the error locally, so my guess is that you used tabs an spaces, if you however copy paste your code into the editor, it should "work". In that case we however receive another error:

GHCi, version 8.0.2: http://www.haskell.org/ghc/  :? for help
[1 of 1] Compiling Main             ( tmp.hs, interpreted )

tmp.hs:7:1: error:
    Equations for ‘apply’ have different numbers of arguments
      tmp.hs:7:1-17
      tmp.hs:(9,1)-(11,29)
Failed, modules loaded: none.

This is due to the fact that you write:

apply s Var c = -- ...

and Haskell assumes that you here wrote three parameters: s, Var, and c, but the c of course belongs to the Var data constructor. We can fix this with a pair of brackets. Furthermore you call lookup in the wrong way: lookup has type lookup :: Eq a => a -> [(a, b)] -> Maybe b, so the first argument is the key (here c), and the second argument is the lookup table s. So we can fix this with:

apply :: Substitution -> Type -> Type
apply s Nat = Nat
apply s Bool = Bool
apply s (Var c) = case (lookup c s) of 
    Nothing -> (Var c)
    Just v  ->  v

Note that you can get rid of the case pattern matching, and use for instance fromMaybe :: a -> Maybe a -> a instead:

import Data.Maybe(fromMaybe)

apply :: Substitution -> Type -> Type
apply s Nat = Nat
apply s Bool = Bool
apply s d@(Var c) = fromMaybe d (lookup c s)

We can furthermore group the Nat and Bool case together:

import Data.Maybe(fromMaybe)

apply :: Substitution -> Type -> Type
apply s d@(Var c) = fromMaybe d (lookup c s)
apply s t = t

This given of course that in case the Type is not a Var c pattern, we should return that Type.

Perhaps you need to call apply recursively as well, since the substitution can result into another Var (and thus you have to do extra lookups). This will however change the function semantically (!), so I am not sure if that is a requirement.