Lists, Higher-Order Functions & Laziness

List Operations

Lists are linked lists: [] is empty, (x:xs) is head:tail. Prelude functions: head, tail, init, last, length, reverse, take, drop, zip, unzip, concat, concatMap, elem, null, filter, map. List comprehensions: [x*2 | x <- [1..10], x `mod` 2 == 0] generates doubled even numbers. Ranges: [1..10], [1,3..10] (step), ['a'..'z'].

Higher-Order Functions

map f xs applies f to every element. filter p xs keeps elements satisfying predicate p. foldr f z xs reduces right-to-left: foldr (+) 0 [1,2,3] = 1+(2+(3+0)) = 6. foldl is left-to-fold; foldl' (strict) avoids stack overflow on large lists. Function composition: (f . g) x = f (g x). Partial application: map (*2) [1..5] — (*2) is a partially applied section.

Lazy Evaluation and Infinite Lists

Haskell only evaluates expressions when their values are needed. This enables infinite lists: [1..] is an infinite list of naturals. 'take 10 [1..]' evaluates only the first 10 elements. Infinite lists: repeat x (infinite xs), cycle xs (repeating cycle), iterate f x ([x, f x, f(f x), ...]). Fibonacci: 'fibs = 0 : 1 : zipWith (+) fibs (tail fibs)' — an infinite list defined recursively.

-- Higher-order functions
doubles :: [Int] -> [Int]
doubles = map (*2)

evens :: [Int] -> [Int]
evens = filter even

sumSquares :: [Int] -> Int
sumSquares = foldl' (+) 0 . map (^2)
  where foldl' = foldl seq `seq` foldl
-- Better: import Data.List (foldl')

-- List comprehension: Pythagorean triples
pyTriples :: Int -> [(Int,Int,Int)]
pyTriples n = [(a,b,c) | c <- [1..n],
                          b <- [1..c],
                          a <- [1..b],
                          a^2 + b^2 == c^2]

-- Infinite Fibonacci list
fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

-- First 15 Fibonacci numbers
first15 :: [Integer]
first15 = take 15 fibs  -- [0,1,1,2,3,5,8,13,21,34,55,89,144,233,377]