Recursion, Higher-Order Functions, Lambdas, Currying, Lists

Class: CSCE-314

Notes:

1. Recursion Patterns in Lists

Lists in Haskell are recursive: either [] or (x:xs). Functions mirror this structure: a base case for [] and a recursive step for (x:xs).

sumList :: [Int] -> Int
sumList [] = 0
sumList (x:xs) = x + sumList xs

productList :: [Int] -> Int
productList [] = 1
productList (x:xs) = x * productList xs

Recursion directly follows the shape of the data.

2. List Generation

Finite ranges:

[1..5]    -- [1,2,3,4,5]
[2,4..10] -- [2,4,6,8,10]
[1,3..20] -- odd numbers up to 20

Infinite lists (thanks to laziness):

[1..]   -- infinite naturals
[1,3..] -- infinite odds

• Why don't you run out of memory?
  • Because haskell doesn't run it until you need it.
  • The way you use it is to say, for example wanting to know the first 50 prime numbers. (a slice of what you want).

Use take to slice:

take 10 [1,3..] -- first 10 odd numbers

Haskell’s laziness makes infinite sequences practical.

3. List Comprehensions

Inspired by set notation in math.

[x*2 | x <- [1..5]]        -- [2,4,6,8,10]
[x | x <- [1..10], even x] -- [2,4,6,8,10]
[(x,y) | x <- [1..3], y <- [1..2]] -- pairs

Combine filters and nesting

[p | p <- [1..20], prime p] -- primes under 20 (if prime defined)

Comprehensions provide a declarative way to build and filter lists.

4. Higher-Order Functions (HOFs)

A higher-order function takes a function as an argument or returns a function.

map (*2) [1..5]        -- [2,4,6,8,10]
filter odd [1..10]     -- [1,3,5,7,9]
foldr (+) 0 [1..5]     -- 15
foldr (:) [] [1,2,3]   -- [1,2,3]

map, filter, foldr abstract away recursion into reusable patterns.

• map: apply function to each element
  • Each element in the list gets changed but not removed/created
• filter: keep elements matching condition
  • 0, a subset, or the whole list.
• foldr: reduce list to single value
  • Returns a single answer (i.e. sum)
  • What is the identity fold?
    • Gives you what you had
      • 1 + 0 = 1
    • Gives you back the list you had

Basically all of these are just generalized recursion.

5. Lambda Functions (Anonymous Functions)

Quick, throwaway functions without names.

• Anonymous functions (inline)

map (\x -> x * x) [1..5]              -- [1,4,9,16,25]
filter (\x -> x `mod` 3 == 0) [1..20] -- multiples of 3
(\x y -> x + y) 3 4                   -- 7

Lambdas highlight the FP idea of functions as data.

6. Currying & Partial Application

What is Currying?

• When you have a function that needs, say 3 parameters, but at the time of running your program you only have two of them.
• We can say to work with these one parameter (a partially applied function waiting for a second parameter)

In Haskell, every function takes one argument. If more are needed, it returns another function.

add :: Int -> Int -> Int
add x y = x + y

is really:

add :: Int -> (Int -> Int)

Partial application:

map (add 1) [1,2,3] -- [2,3,4]

• Currying + partial application = powerful composability.

7. Putting It All Together (with FP vs Haskell Notes)

• Recursion – General FP concept: core to FP, present in Haskell, ML, Scheme, etc.
• Ranges & Infinite Lists – Haskell-specific: [1..10] and [1,3..] are unique to Haskell’s syntax and laziness.
• List Comprehensions – FP-inspired, Haskell-specific flavor: appear in Python, F#, Scala, but Haskell’s are lazy and pure.
• Higher-Order Functions (map, filter, fold) – General FP concept: essential to all FP languages; widely adopted in modern mainstream languages.
• Lambda Functions – General FP concept: rooted in lambda calculus; appear in nearly all FP and modern multiparadigm languages.
• Currying & Partial Application – General FP concept, emphasized in Haskell: all Haskell functions are curried by default; other languages often require extra syntax.

8. Wrap-Up & Activities

Concepts covered: recursion, ranges, comprehensions, HOFs, lambdas, currying.

Activities this week:

• Wed: live coding recursion vs. folds.
• Fri: group mini-library of list functions (average, unique, mode).

Big takeaway: mastering lists = fluency in functional programming.

Readings from Learn You a Haskell:

• Chapter 5 - Recursion
  • Directly matches your section on recursive list patterns (sum, product, maximum, etc.).
• Chapter 6 - Higher Order Functions
  • Introduces functions as first-class citizens