HASKELL LAMBDA CALCULUS

REVISED: Saturday, February 10, 2024

Haskell Lambda Calculus.

I.  HASKELL LAMBDA CALCULUS

Introduced by Alonzo Church in the 1930s, Lambda Calculus, consisting of a single transformation rule and function definition scheme, is the world's smallest programming language. Any computable function can be expressed and evaluated using Lambda Calculus.

A. LAMBDA CALCULUS WITH ONE VALUE

λx.x*x

Rewriting the above Lambda Calculus equation into a Haskell anonymous function only requires three steps.

Firstly, give the equation a name followed by an = sign.

Secondly, replace the λ with a backslash \. λ pronounced lambda, is supposed to resemble the Greek λ lambda without the hook.

Thirdly, replace the . with an arrow ->.

As shown below, λx.x*x becomes square = \x -> x*x:

module Square where                       -- "File, Save As" Square.hs

square :: Num a => a -> a                  -- Type signature.

square = \x -> x*x                             

"Copy, Paste" the Square module shown above into your text editor and "File, Save As" Square.hs in your working directory.

An explicitly declared type, as shown above for square, is called a type signature. The type signature says square is a function which, for some type a which is an instance of Num, takes a value of type a and gives back a value of type a.

Load the module Square into GHCi.

Prelude> :load Square                              -- GHCi interpreter.
[1 of 1] Compiling Square           ( Square.hs, interpreted )
Ok, modules loaded: Square.

Use GHC to compile Square.

Prelude> :! ghc --make "*Square"     -- GHC compiler.
[1 of 1] Compiling Square           ( Square.hs, Square.o )

Call the square function.

Prelude> square 5                               -- Use lower case s for square.

25

it :: Num a => a
Prelude>  

To use the Lambda Calculus anonymous function in the GHCi interactive shell requires enclosing the anonymous function with parentheses as shown below:

Prelude> (\x -> x*x) 5                     
25
it :: Num a => a
Prelude>  

B. LAMBDA CALCULUS WITH TWO VALUES

Shown below is a Lambda Calculus function that takes two numbers, triples the first number and adds the result to the square of the second number.

λxλy.3*x+y*y 

Rewriting the above Lambda Calculus equation into Haskell  is shown below:

module Twoval where                         -- File "Save As" Twoval.hs

twoval = \x y -> 3*x + y*y

"Copy, Paste" the Twoval module shown above into your text editor and "File, Save As" Twoval.hs in your working directory.

Load the module Twoval into GHCi as shown below:

Prelude> :load Twoval                        -- GHCi interpreter.
[1 of 1] Compiling Twoval           ( Twoval.hs, interpreted )
Ok, modules loaded: Twoval.

Use GHC to compile Twoval.

Prelude> :! ghc --make "*Twoval"     -- GHC compiler.
[1 of 1] Compiling Twoval           ( Twoval.hs, Twoval.o )

Call the twoval function.

Prelude> twoval 2 3                       -- Use lower case t for twoval. (3*2) + (3*3) = 6 + 9 = 15.

15

it :: Integer
Prelude>  

Notice calling the Haskell anonymous function takes less work as shown below:

Prelude> (\x y -> 3*x + y*y) 2 3      -- (Parentheses required) then variables.

15

it :: Num a => a
Prelude>  

II. HASKELL LAMBDA CALCULUS ANONYMOUS FUNCTIONS

Anonymous functions are normally used to make functions that are only used once or passed to other functions.

In pure lambda calculus there are no constants. A Haskell lambda can only have a single clause in its definition.

(λxλy.6*x+y*y*y)5 2

λ notation allows us to create anonymous functions without names. Notice λ is a backward slash \ and not a forward slash / as used in division or negate.

Instead of using function names to define functions, we define them anonymously via a lambda abstraction.

Prelude> (\x y -> 6*x + y*y*y) 5 2   -- (6*5) + (2*2*2) = 30 + 8
38
it :: Num a => a
Prelude> 

Prelude> map (\ar -> ar + 3) [10,20,30,40]  -- lambda abstraction is (\ar -> ar + 3)

[13,23,33,43]

Prelude>

III.  CONCLUSION

In this tutorial, you have received an introduction to Haskell Lambda Calculus.

IV. REFERENCES

Bird, R. (2015). Thinking Functionally with Haskell. Cambridge, England: Cambridge University Press.

Davie, A. (1992). Introduction to Functional Programming Systems Using Haskell. Cambridge, England: Cambridge University Press.

Goerzen, J. & O'Sullivan, B. &  Stewart, D. (2008). Real World Haskell. Sebastopol, CA: O'Reilly Media, Inc.

Hutton, G. (2007). Programming in Haskell. New York: Cambridge University Press.

Lipovača, M. (2011). Learn You a Haskell for Great Good!: A Beginner's Guide. San Francisco, CA: No Starch Press, Inc.

Thompson, S. (2011). The Craft of Functional Programming. Edinburgh Gate, Harlow, England: Pearson Education Limited.