Search code examples
haskelllambdafunctional-programminglambda-calculus

Haskell Lambda help - Creating a applications function

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!

Solution

  • 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