Haskell Snippets

2023-05-03

haskell

I will be explaining some haskell snippets in this post. While doing that I will try to show beauty of haskell and how we can use it to write concise and elegant code.

Fibonacci

Fibonacci is a sequence of numbers where each number is the sum of the two preceding ones, starting from 0 and 1.

We can write a function to generate the nth fibonacci number in haskell in many ways. Lets see some of them.

Basic

fibo :: Integer -> Integer
fibo 0 = 0
fibo 1 = 1
fibo n = fibo (n - 1) + fibo (n - 2)

In the code above, we are using pattern matching to match the first two numbers of the fibonacci sequence which are base cases and then we are using recursion to calculate the nth fibonacci number.

Using zipWith

fibo :: Int -> Integer
fibo n = fibs !! n
    where fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

In the code above, we are using builtin zipWith function to calculate the nth fibonacci number. zipWith takes a function and two lists and applies the function to each pair of elements from the lists. But this is not the actual magic, we are using the fibs itself in the definition of fibs. This is possible because of lazy evaluation in haskell. Expressions are only evaluated when they are needed. So at the start we have

  • fibs as [0, 1, ...]
  • tail fibs as [1, ...]
  • zipWith (+) fibs (tail fibs) as [1, 2, ...]

So we are using the first two elements of the list to calculate the third element and so on. Note that fibs is a infinite list and we are only evaluating the elements only when we need them.

Using foldl

fibo :: Int -> Integer
fibo n = fst $ foldl (\(a, b) _ -> (b, a + b)) (0, 1) [1..n]

In the code above, we are using foldl method to calculate the nth fibonacci number. foldl takes a function, an initial value and a list and applies the function to each element of the list and the accumulator. Here the list is [1..n] which is used to iterate n times. The (0, 1) value is the initial value which is the accumulator. The function is ((a, b) _ -> (b, a + b)) which takes the accumulator and the current element and returns the new accumulator. So we are using the accumulator to store the last two fibonacci numbers and then we are calculating the next fibonacci number using the accumulator.

Prime Numbers

A prime number is a number that is divisible only by itself and 1.

We can write a function to check if a number is prime or not in haskell in many ways. Lets see some of them.

6k ± 1

isPrime :: Integer -> Bool
isPrime n
    | n < 2          = False
    | n `mod` 2 == 0 = n == 2
    | n `mod` 3 == 0 = n == 3
    | otherwise      = not $ any (\x -> n `mod` x-1 == 0 || n `mod` x+1 == 0) [6, 12 ..(floor $ sqrt $ fromIntegral n)]

In the code above, we are using pattern matching to match the numbers less than 2 which are not prime. Then we are checking if the number is even or not. If it is even then it is not prime. Then we are checking if the number is divisible by 3 or not. If it is divisible by 3 then it is not prime. Then we are using any function to check if any of the numbers in the list are divisible by n. (Note that we are negating the result because it returns true if any of the numbers are divisible by n and we want to return true if none of the numbers are divisible by n) Because Haskell is lazy, it will only check the numbers until it finds a number which is divisible by n.