CodeToLive

Functions & Recursion in Haskell

Functions are the building blocks of Haskell programs. Since Haskell is a purely functional language, functions are first-class citizens that can be passed as arguments, returned as results, and composed together.

Function Definition

Functions in Haskell are defined with a name, parameters, and an expression:

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

-- Function with type signature
square :: Int -> Int
square x = x * x
      

Pattern Matching

Haskell allows pattern matching in function definitions:

-- Factorial with pattern matching
factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n - 1)

-- Fibonacci sequence
fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)
      

Guards

Guards provide an alternative way to express conditional logic:

-- Absolute value with guards
absolute :: Int -> Int
absolute x
  | x >= 0    = x
  | otherwise = -x

-- Grade classifier
grade :: Int -> String
grade score
  | score >= 90 = "A"
  | score >= 80 = "B"
  | score >= 70 = "C"
  | score >= 60 = "D"
  | otherwise   = "F"
      

Lambda Functions

Anonymous functions can be created with lambda expressions:

-- Lambda function example
squareAll :: [Int] -> [Int]
squareAll xs = map (\x -> x * x) xs

-- Using lambda with filter
evens :: [Int] -> [Int]
evens xs = filter (\x -> x `mod` 2 == 0) xs
      

Higher-Order Functions

Functions that take other functions as arguments or return functions:

-- Function composition
compose :: (b -> c) -> (a -> b) -> a -> c
compose f g x = f (g x)

-- Applying a function twice
applyTwice :: (a -> a) -> a -> a
applyTwice f x = f (f x)
      

Recursion

Since Haskell doesn't have traditional loops, recursion is fundamental:

-- Sum of a list
sumList :: [Int] -> Int
sumList [] = 0
sumList (x:xs) = x + sumList xs

-- Length of a list
length' :: [a] -> Int
length' [] = 0
length' (_:xs) = 1 + length' xs

-- QuickSort implementation
quickSort :: Ord a => [a] -> [a]
quickSort [] = []
quickSort (x:xs) = 
  quickSort [y | y <- xs, y <= x] 
  ++ [x] ++ 
  quickSort [y | y <- xs, y > x]
      

Tail Recursion

Tail-recursive functions are more efficient as they can be optimized:

-- Tail-recursive factorial
factorial :: Integer -> Integer
factorial n = helper n 1
  where
    helper 0 acc = acc
    helper n acc = helper (n - 1) (acc * n)

-- Tail-recursive sum
sumList :: [Int] -> Int
sumList xs = helper xs 0
  where
    helper [] acc     = acc
    helper (x:xs) acc = helper xs (acc + x)
      

Function Composition

Functions can be composed using the (.) operator:

-- Composing functions
squareAndIncrement :: Int -> Int
squareAndIncrement = (+1) . (^2)

-- Multiple composition
processString :: String -> String
processString = reverse . map toUpper . filter (/= ' ')