2

I am trying to create a function applications that will, when given a term N and a list of terms (X1,...,Xn) return N(X1,...,Xn)

But when I run my code, it shows the following error:

    * Couldn't match type `Term' with `[Char]'
      Expected type: Var
        Actual type: Term
    * In the first argument of `Lambda', namely `x'
      In the expression: Lambda x (applications v xs)
      In an equation for `applications':
          applications v (x : xs)
            | x == [] = Lambda x v
            | otherwise = Lambda x (applications v xs)
    |
147 |     |otherwise = Lambda x (applications v xs)

But for some reason my applications function causes this error, even though it seems similar to my working abstractions.

applications :: Term -> [Term] -> Term
applications v [] = v
applications v (x:xs)
    |x == [] = Lambda x v
    |otherwise = Lambda x (applications v xs)

I would appreciate any help as I am new to this!

Improve this question
6
  • Well in your applications you pass a list of Terms, your Lambda likely expects a Var as item in the head? Furthermore it should be null xs instead of x == [] I guess, although that is likely not the "core problem". Commented May 2, 2020 at 10:40
  • applications is also the opposite of abstractions based on the description here. Here you should basically pattern match on Lambda, and then replace the variable in the head of the lambda in the body of the lambda with the term. Commented May 2, 2020 at 10:43
  • @WillemVanOnsem that has helped. My code now reads: |null xs = Lambda x v Although I am now getting an error on the line : |otherwise = Lambda x (applications v xs) Commented May 2, 2020 at 10:46
  • yes, because as said, you can not use a Term as variable in your Lambda. Furthermore applications should do the opposite of abstractions. Commented May 2, 2020 at 10:50
  • You don't want to use Lambda to build an application. There are no lambdas in your description of what you want to do: "given a term N and a list of terms (X1,...,Xn) return N(X1,...,Xn)". Usually there's a Term constructor for application. Commented May 2, 2020 at 13:44

1 Answer 1

Reset to default
3

I assume your type Term is defined as follows:

type Var  = String
data Term = Var Var | Lambda Var Term | App Term Term deriving Show

That is, that application is captured by a binary data constructor App.

Now, note that your definition of abstractions can be simplified by dropping the case distinction from the second clause (the case for an empty tail is caught by the first clause already):

abstractions :: Term -> [Var] -> Term
abstractions t []       = t
abstractions t (x : xs) = Lambda x (abstractions t xs)

Where lambda-abstractions typically extend as far to the right as possible, i.e., lambda x1. lambda x2. t = lambda x1. (lambda x2. t), function application typically associates to the left, i.e., t u1 u2 = (t u1) u2. Hence, a straightforward application of your function applications could be:

applications :: Term -> [Term] -> Term
applications t []       = t
applications t (u : us) = applications (App t u) us

For example:

> applications (Var "x") [Var "y", Var "z"]
App (App (Var "x") (Var "y")) (Var "z")

Now, finally, abstractions and applications follow familiar patterns. abstractions can be written as a right-fold over a list of variables to abstract over and applications can be written as a left-fold over a list of terms to apply to:

abstractions = foldr Lambda
applications = foldl App
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

This was a brilliant help. Getting the hang of it more now. Thanks.