Haskell Snippets

A series of helpful Haskell functions and implementations for beginners. Note that these implementations emphasize understanding rather than conciseness.

Contents

• Sorting Algorithms
  • Quicksort
  • Insertion Sort
  • Selection Sort
• List Functions
  • Safetail
  • Reverse
  • Length
  • Sum
  • Palindrome
  • Check Sorted
  • Duplicate Each Element
• Miscellaneous
  • Fibonacci
  • Factorial
  • Absolute Value
• Practice Problems
  1. Implement map with foldr
  2. Implement filter with foldr
• Contributing
• Motivation

Sorting Algorithms

Quicksort (Gist) (Wiki)

Complexity

Case	Complexity
Worst	O(n^2)
Average	O(nlogn)

Implementation (List Comprehension)

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

Implementation

Credit @aadithpm

quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) = (quicksort small) ++ [x] ++ (quicksort big)
where
        small  = filter (< x) xs
        big = filter (>= x) xs

Insertion Sort (Gist) (Wiki)

Complexity

Case	Complexity
Worst	O(n^2)
Average	O(n^2)

Implementation (Using Insert)

Note: this implementation depends on the function insert from the module Data.List. See the gist for an example on importing this module selectively with hiding.

insertsort :: Ord a => [a] -> [a]
insertsort  =  foldr insert []

Selection Sort (Gist) (Wiki)

Complexity

Case	Complexity
Worst	O(n^2)
Average	O(n^2)

Implementation

selSort :: (Ord a) => [a] -> [a]
selSort [] = []
selSort xs = let x = maximum xs in selSort (remove x xs) ++ [x] 
  where remove _ [] = []
        remove a (x:xs)
          | x == a = xs
          | otherwise = x : remove a xs

List Functions

Safetail (Gist)

A tail function with accommodations for the empty list.

Implementation (Conditional)

safetail :: Eq a => [a] -> [a]
safetail xs = if xs == [] then [] else tail xs

Implementation (Guarded)

safetail :: Eq a => [a] -> [a]
safetail xs
  | xs == []  = []
  | otherwise = tail xs

List Reverse (Gist)

Reverse a list using pattern matching.

Implementation

reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]

List Length (Gist)

Implementation (Recursive Strategy)

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

List Sum (Gist)

Implementation

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

Check Palindrome (Gist)

Implementation (With Prelude Functions)

Note that the prelude function init returns a list without its last element, while the function tail returns the list without its first element. The composition of the functions (explicity using the $ operator) results in a list without its first and last elements.

palindrome :: Eq a => [a] -> Bool
palindrome []  = True
palindrome [_] = True
palindrome xs  = (head xs) == (last xs) && (palindrome $ init $ tail xs)

Check Sorted (Gist)

Check if list is sorted in ascending order (smallest to largest values).

Implementation

sorted :: (Ord a) => [a] -> Bool
sorted [] = True
sorted [x] = True
sorted (x:y:xs) = if x <= y then sorted (y:xs) else False

Duplicate Each Element (Gist)

Repeat each element in a list twice ([a,b,c] -> [a,a,b,b,c,c])

duplicate :: [a] -> [a]
duplicate []     = []
duplicate (x:xs) = [x, x] ++ duplicate xs

Miscellaneous

Fibonacci Sequence (Gist)

Implementation

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

Factorial (Gist)

Compute the factorial of n recursively.

factorial :: Int -> Int
factorial 0 = 1
factorial n = n * factorial (n-1)

Absolute Value (Gist)

Compute the absolute value of an integer n.

absoluteValue :: Int -> Int
absoluteValue n | n >= 0 = n
                | otherwise  = -n

Practice Problems

Implement map with foldr (Gist)

Write a function map' that mimics the functionality of map from the standard prelude, making use of foldr

Solution

map'            :: (a -> b) -> [a] -> [b]
map' f []       = []
map' f (x:xs)   = foldr (\y ys -> (f y):ys) [] xs

Explanation

Coming soon...

Implement filter with foldr (Gist)

Write a function filter' that mimics the functionality of filter from the standard prelude, making use of foldr

Solution

filter' p = foldr (\x xs -> if p x then x : xs else xs) []

Explanation

Coming soon...

Contributing

Contributions are encouraged and welcome! The motivation of this repository is to collect enlightening Haskell code and to teach by example. Open a pull request after you have done the following:

• Compile code in GHC and verify correctness
• Added code snippet to README.md
• Added necessary Table of Content entries
• Added necessary explanation and/or links

Feel free to @mention yourself to credit your contributions!

Motivation

This repository is both a exercise in Haskell and a resource for beginners in search of transparent, clear examples of common implementations in the Haskell language. Focusing on typical programming problems allows us to juxtapose the thought patterns of this functional language against imperative languages normal to a Computer Science undergraduate program.