Lecture 04.5 (Discussion 2)

2022-10-05 | Week 2 | edited by Boyan Ding

(originally written 2022-10-05 by Boyan Ding)

These are the lecture notes from the Fall 2022 version of this class, completely unedited. It covers content that was covered in Week 2 discussion; we’re leaving this up for you to get more notes!

Table of Contents

• Currying (continued)
• Partial Function Application
• Algebraic Data Types
  • Syntax
  • Pattern Matching with ADT
  • Creating Trees with ADT
  • Influencer Alert: Immutability
• Summary

Currying (continued)

A pseudocode that represent the logic of currying can be written as:

Curry(Function f)
  e = The expression/body of function f
  For each parameter p from right to left:
    f_temp = Define a new lambda function with:
      1. p as its only parameter
      2. e as its (expression)
    e = f_temp
return f_temp

Let’s use the procedure above to curry the function mult3 x y z = x*y*z

• At first, e is equal to x*y*z
• Then we enter the for loop
  • In the first iteration, z is the parameter to be handled. f_temp = \z -> x*y*z
  • Next, we handle y and f_temp = \y -> (\z -> x*y*z)
  • Finally, we handle y and we get f_temp = \x -> (\y -> (\z -> x*y*z))

Thus, the curried version mult3c = \x -> (\y -> (\z -> x*y*z)).

Let’s see how we call our curried function with x=2, y=3 and z=5!

ghci> mult3c = \x -> (\y -> (\z -> x*y*z))
ghci> f1 = mult3c 2
ghci> f2 = f1 3
ghci> result = f2 5
30

So, what actually are f1 and f2?

f1 is obtained by calling the lambda of mult3c with x=2. Thus we replace the occurrences of x inside the lambda function with 2 and remove the \x -> at the beginning. f1 is: \y -> (\z -> 2*y*z).

When a inner lambda has the same parameter name as the outer one. The inner one takes precedence and shadows the outer one. In this case, the shadowed parameter will not get replaced. For example, when we evaluate (\x -> ((\x -> x) (x + 1))) 3, we will get ((\x -> x) (3 + 1)).

Once again, when we repeat the process, we can get f2 = \z -> (2*3*z), and finally result = 2*3*5, thus 30.

In fact, every time you define a function of more than parameter in Haskell, Haskell automatically and invisibly curries it for you.

This is evidenced by the fact that even if you replace the mult3c above with the “normal” mult3 x y z = x*y*z, you will get the same result. You can also legally execute (((mult3 2) 3) 5) in Haskell and get 30.

Surprising fact: Our usual way of calling functions mult3 2 3 5 looks like a single call with three arguments, but it’s really three calls to three different functions! What happen’s is exactly identical to (((mult3 2) 3) 5), thus we know function invocation is left associative.

Also, now we can reveal the fact about Haskell function type signatures:

Remember those ugly (and maybe confusing) Haskell type signatures?

mult3 :: Double -> Double -> Double -> Double
mult3 x y z = x * y * z

Well, here’s what they should really look like given that all functions are curried (thus mult3 is a three-level nested function that returns a function at each outer level):

mult3 :: Double -> (Double -> (Double -> Double))
mult3 x y z = x * y * z

Although the latter form looks more fundamental, it is even uglier. That’s why we used smore syntactic sugar to remove the parentheses. (We can regard the -> “operator” in type signatures as right-associative)

People may ask, why does Haskell curry function? We think there are two primary reasons:

• First, it enables partial function application (which we we’ll see more below)
• But mostly it appears to be motivated by theorists! It can facilitate program analysis and other stuff and it is consistent with the lambda calculus, the mathematical foundation of functional programming.

Partial Function Application

When you call a function with less than the full number of arguments this is called “Partial Function Application” or “Partial Application.”

Formally speaking, partial function application is an operation where we define a new function g by combining:

• An existing function f that takes one or more arguments, with
• Default values for one or more of those arguments

The new function g is a specialization of f, with hard-coded values for some of f’s parameters.

Once defined, we can then call g with those arguments that have not yet been hard-coded.

Partial function application is deeply related with currying we have just learned. In fact, when we used ((mult3 2) 3) 5 earlier, we are implicitly doing partial function application. But let’s see more examples:

ghci> mult3 x y z = x*y*z
ghci> partial = mult3 2
ghci> partial 3 5
30
ghci> multby10_20 = mult3 10 20
ghci> multby10_20 3

Here, we are creating two specialized functions partial y z = 2*y*z and multby10_20 z = 10*20*z with partial application.

Partial function applications can be useful when combined with pre-existing functions and operators. Let’s see the following examples:

ghci> add5 = (+) 5
ghci> add5 100
105

All of Haskell’s operators are just functions! So the + sign is basically a function of two arguments.

Surrounding an infix operator with a pair of parentheses converts it to the prefix form which gives you identical behavior to a normal function.

ghci> map (/ 10) [100,200,300]
[10.0,20.0,30.0]
ghci> map (10 /) [100,200,300]
[0.1,5.0e-2,3.333333333333333e-2]

Haskell also allows you to apply partial application to either operands of infix operators. The function produced by the first line is equivalent to \x -> x / 10, while the second line produces \x -> 10 / x. You can see the behavior by reading the result returned by the map function.

Here are more examples:

ghci> filter (>= 6) [2,4,6,8,10,3]
[6,8,10]
ghci> map (++ " is LIT!") ["CS32","CS131"]
["CS32 is LIT!","CS131 is LIT!"]
ghci> filter (`elem` ['A'..'Z']) "Not Every Resistor Drives current"
"NERD"

In the last example, the pair of backticks turns a function with two arguments into an infix operator so that you can supply the second argument with partial application.

We can even use partial function application to define a partially-specified mapper function:

ghci> cuber = map (\x -> x^3)
ghci> cuber [2,3,5]
[8,27,125]

As you can see, with partial function applications often we don’t have to define a full function or lambda to do complex processing!

Algebraic Data Types

Algebraic Data Type (ADT) is the term we use in functional programming to describe a user-defined data type that can have multiple fields.

The closest thing to algebraic data types would be C++ structs and enumerated types. We use algebraic data types to create complex data structures like trees.

In Haskell, we use keyword “data” to define algebraic data types.

The simplest algebraic data types are just like C++ enums:

• The pipe (

  ) character means “OR”

• Each choice for a given type is called a “variant” or a “kind”

data Drink = Water | Coke | Sprite | Redbull
data Veggie = Broccoli | Lettuce | Tomato
data Protein = Eggs | Beef | Chicken | Beans

For the Protein type, its equivalent in C++ would be:

enum Protein { Eggs, beef, chicken, Beans };

We can also define more complex ADTs where each variant also has one or more fields (like C++ struct).

data Meal =
 Breakfast Drink Protein |
 Lunch Drink Protein Veggie |
 Dinner Drink Protein Protein Veggie |
 Fasting

The definition of first variant Breakfast means that it is comprised of Drink and Protein fields. Its equivalent in C++ would be:

struct Breakfast {
  Drink d;
  Protein p;
}

The only difference is, the fields in Haskell does not have a name, and they are distuished by the order they appear in the definition.

Note that the variants with and without fields can coexist within a single ADT, the Fasting above is just an example.

Here are some examples to define variables with ADT:

careys_meal = Breakfast Redbull Eggs
pauls_meal = Lunch Water Chicken Broccoli
davids_meal = Fasting

Syntax

We use another example to introduce the syntax of Algebraic Data Types

-- algebraic.hs
data Color = Red | Green | Blue

data Shape =
  Circle
   Float Float -- x, y
   Float       -- radius
   Color |
  Rectangle
   Float Float -- x1, y1
   Float Float -- x2, y2
   Color

• To define a new ADT, we use the data keyword
• The syntax can be represented as data TypeName = Variant1 | Variant2 | ... | VariantN
• The initial of type names should be capitalized (to differentiate with type variables)
• The initial of variant names should be capitalized as well.
• The general syntax for defining a variant that has fields is: VariantName Type1 Type2 ... TypeN

Each time you define a variant with fields, Haskell implicitly creats a “constructor” that can be used to create a new variable. For example, the code above a Circle constructor with four parameters (three Floats and a Color) to create a new Circle.

We can add the keywords deriving Show at the end of a definition to enable us to print out variable values in GHCi. This is simply a hack that makes our life easier when debugging in GHCi.

If we added deriving Show to both Color and Shape, we can test with the types in GHCi:

ghci> :load algebraic
[1 of 1] Compiling Main             ( lambda.hs, interpreted )
ghci> c = Circle 5 6 10 Red
ghci> c
Circle 5.0 6.0 10.0 Red
ghci> r = Rectangle 0 0 5 6 Blue
ghci> r
Rectangle 0.0 0.0 5.0 6.0 Blue
ghci> :t r
r :: Shape
ghci> colors = [Red, Red, Blue]
ghci> colors
[Red,Red,Blue]

Note that the fields of a variant have no names! That means we must use their order/position to identify them.

Pattern Matching with ADT

In functional languages, we use pattern matching to process algebraic variables.

Let’s see an example with our shapes. We first update our Shape algebraic type a bit and add a new “Shapeless” type of shape.

-- shapes.hs

data Shape =
   Shapeless
 | Circle
    -- x      y    rad
    Double Double Double
 | Rectangle
    -- x1    y1     x2     y2
    Double Double Double Double
 deriving Show

getArea :: Shape -> Double
getArea Shapeless = 0
getArea (Circle _ _ r) = pi * r^2
getArea (Rectangle x1 y1 x2 y2) =
  (abs (x2-x1)) * (abs (y2-y1))

We focus on the getArea function:

• The first line is the type signature. As this functions operates on various types of Shape, this definition makes sense.
• Then follows the actual pattern matching
  • The first line means: “If the user passes in a Shapeless variable, then always return zero”.
  • The second line handles the Circle case. It gets the third field (radius), placing it into variable r and computes the area.
  • The last line handles Rectangle. It extracts the fields from the data structure and computes the area according to the width and height.

We can combine pattern matching on ADT with lists and tuples to create complex patterns. For example, the following function counts the occurrences of Circle within a list of Shape without using map, filter or foldl.

count_circle :: [Shape] -> Integer
count_circle [] = 0
count_circle ((Circle _ _ _):xs) = 1 + count_circle xs
count_circle (_:xs) = count_circle xs

Exercise: Implement count_circle with map, filter and foldl respectively.

Creating Trees with ADT

Let’s examine a more interesting use of ADTs – creating a binary search tree.

We’ll start by looking at the definition of a tree node ADT.

-- bst.hs
data Tree =
  Nil |
  Node String Tree Tree

A tree data type has two possible variants:

• An empty variant indicating that there is no node, like a nullptr
• A node variant representing actual nodes.

In this definition, each Node holds a String value, and two other tree data items that can be either Nil or Node. The first one is the left child of the node, and the second one is the right child. So this is a binary tree.

ghci> :load bst
[1 of 1] Compiling Main             ( bst.hs, interpreted )
ghci> empty_tree = Nil
ghci> one_node = Node "Lit" Nil Nil
ghci> r = Rectangle 0 0 5 6 Blue
ghci> left_child = Node "Boomer" Nil Nil
ghci> right_child = Node "Zoomer" Nil Nil
ghci> root = Node "Cheugy" left_child right_child
ghci> root
Node "Cheugy" (Node "Boomer" Nil Nil) (Node "Zoomer" Nil Nil)

In the end of the code above, we created a tree with three nodes.

With this tree structure, we can implement search algorithm on this BST.

We’ll use a classic recursive search function and pattern matching.

search Nil val = False
search (Node curval left right) val
 | val == curval = True
 | val < curval = search left val
 | otherwise = search right val

Ok, now let’s see how to create a function that adds a new node to a tree.

But this isn’t so easy, because in functional languages, we can’t modify existing values/variables. Suppose we create a node N and we want to make it the child of existing node M. So we can’t just find a node M and change its left or right child to point to the new N!

The strategy is, we want to create a new node M’, let it point to N and replace the node M we need to change.

But wait… Now the new node M is not part of the tree either. But we can just carry it on to create a new node to replace M’s parent. Eventually we can do this all the way to the root, and at that point, we can forget about the old tree.

The following Haskell code implements the logic:

insert Nil val =
  Node val Nil Nil

insert (Node curval left right) val
  | val == curval =
      Node curval left right
  | val < curval =
      Node curval (insert left val) right
  | val > curval =
      Node curval left (insert right val)

This method sounds a little bit wasteful, because we need to create new nodes all the way up. However, if we think carefully about the process, we’ll find that to add a new node, we just need to generate replacement nodes for the nodes between our new node and the root. Then if a tree is balanced with n nodes, we need to create just log2(n) new nodes!

Meanwhile, with the creation of the new node, the old nodes will no longer be used. This is where “Garbage Collection” comes in.

Garbage Collection is a language feature that automatically reclaims unused variables, and all functional languages have built-in Garbage Collection.

We’ll learn more about GC later in the course, but the important thing is that GC doesn’t impact Big-O!

Although here we see that immutable tree is efficient (in the sense it does not change the Big-O bound of operations). It does not apply to all data structures.

For example, if hash tables are implemented as immutable, the insertion will be inefficient because you must regenerate the full array of n buckets every time you add a new item.

Influencer Alert: Immutability

Many languages now provide immutable data structures – it helps simplify code, reduce bugs, and ease multi-processing.

Examples include Google’s Guava library for Java, and immutable.js for JavaScript.

// Java Guava immutability example
Set<Integer> oldSet = ImmutableSet.of(1,2,3,4);

// Generate a whole new set, with 5 added to it
Set<Integer> newSet = new ImmutableSet.Builder<Integer>().addAll(oldSet)
                               .add(5)
                               .build();

// JavaScript immutable.js example

// Create a new immutable set of 1-4
const oldSet = Immutable.Set([1,2,3,4]);

// add returns a new set & doesn't change orig.
const newSet = oldSet.add(5)

Summary

In summary, here are what we have learned about functional programming

• Every function must take an argument.
• Every function must return a value.
• Functions are “pure” and have no side effects
• Calling the same function with the same input always returns the same result.
• All variables are “immutable” and can never be modified!
• Functions are just like any other data and can be stored in variables and passed as arguments.

And as we have seen along the way, while there are no purely functional languages in mainstream use, the paradigm has influenced every major language.

This concludes our introduction to Haskell and functional programming. Hope you had fun!