List of Useful Haskell Functions and their Python counterparts

haskellFunctions.hs

-- General purpose Haskell functions to remember (Note I have ommited the typeclasses here for simplicity)
-- Bryan O'Sullivan, Don Stewart, and John Goerzen. Real World Haskell, O'Reilly Media, 2008

-- Length of list
-- O(n)
-- ✅(empty list) -> total / safe
-- Python: len(list)
length :: [a] -> Int

-- Tells if a list is empty
-- O(1)
-- ✅(empty list) -> total / safe
-- Python: list == []
null :: [a] -> Bool

-- Get the first element of the list
-- O(1)
-- ❌(empty list) -> partial / unsafe
-- Python: list[0]
head :: [a] -> a

-- Safe version
safeHead :: [a] -> Maybe a
safeHead [] = Nothing
safeHead xs = Just (head xs)

-- Get everything but the head of the list
-- O(1)
-- ❌(empty list) -> partial / unsafe
-- Python: list[1:]
tail :: [a] -> [a]

-- Safe version
safeTail :: [a] -> Maybe a
safeTail [] = Nothing
safeTail xs = Just (tail xs)

-- Get the last element of the list
-- O(n)
-- ❌(empty list) -> partial / unsafe
-- Python: list[-1]
last :: [a] -> a

-- Safe version
safeLast :: [a] -> Maybe a
safeLast [] = Nothing
safeLast xs = Just (last xs)

-- Get everything but the last element of the list
-- O(n)
-- ❌(empty list) -> partial / unsafe
-- Python: list[:-1]
init :: [a] -> [a]

-- Safe version
safeInit :: [a] -> Maybe a
safeInit [] = Nothing
safeInit xs = Just (init xs)

-- concatenate two lists
-- O(n) where n is the length of the first list
-- ✅(empty list) -> total / safe
-- Python: list1 + list2
(++) :: [a] -> [a] -> [a]

-- Concatenates or flattens a list of lists into a single list. It removes one level of nesting
-- O(mn) where m is the length of the outer list and n is the length of the inner list
-- ✅(empty list) -> total / safe
-- Python: sum(list_of_lists, [])
concat :: [[a]] -> [a]

-- Reverses the elements of the list
-- O(n)
-- ✅(empty list) -> total / safe
-- Python: list[::-1]
reverse :: [a] -> [a]

-- Generalize (&&) to list of Bools
-- O(n)
-- ✅(empty list) -> total / safe
-- Python: all(list_of_bools)
and :: [Bool] -> Bool

-- Generalize (||) to list of Bools
-- O(n)
-- ✅(empty list) -> total / safe
-- Python: any(list_of_bools)
or :: [Bool] -> Bool

-- Maps list to list of bools and then applies and i.e. and (map func list)
-- O(n)
-- ✅(empty list) -> total / safe
-- Python: all([func(x) for x in list]) # where func returns a boolean
all :: (a -> Bool) -> [a] -> Bool

-- Maps list to list of bools and then applies or i.e. or (map func list)
-- O(n)
-- ✅(empty list) -> total / safe
-- Python: any([func(x) for x in list]) # where func returns a boolean
any :: (a -> Bool) -> [a] -> Bool

-- Returns the first k elements of the list
-- O(k)
-- ✅(empty list) -> total / safe
-- Python: list[:k]
take :: Int -> [a] -> [a]

-- Returns everything but the first k elements of the list
-- O(k)
-- ✅(empty list) -> total / safe
-- Python: list[k:]
drop :: Int -> [a] -> [a]

-- Splits list up based on index
-- O(k)
-- ✅(empty list) -> total / safe
-- Python: (list[:k], list[k:])
splitAt :: Int -> [a] -> ([a], [a])

-- Returns elements from the list while the predicate remains True
-- O(n)
-- ✅(empty list) -> total / safe
-- Python: (Note: in python we usually use list comprehensions and filter instead)
-- newlist = []
-- for x in list:
--   if not predicate(x):
--     break
--   newlist.append(x)
takeWhile :: (a -> Bool) -> [a] -> [a]

-- Returns elements from the list after the predicate remains becomes False
-- O(n)
-- ✅(empty list) -> total / safe
-- Python: (Note: in python we usually use list comprehensions and filter instead)
-- newlist = []
-- for x in list:
--   if predicate(x):
--     continue
--   newlist.append(x)
dropWhile :: (a -> Bool) -> [a] -> [a]

-- Splits a list into two parts based on where the predicate first becomes False (tuple of takeWhile)
-- O(n)
-- ✅(empty list) -> total / safe
-- Python:
-- newlists = ([],[])
-- for i, x in enumerate(list):
--   if not predicate(x):
--     newlists[1] = list[i:]
--   newlists[0].append(x)
span :: (a -> Bool) -> [a] -> ([a], [a])

-- Splits a list into two parts based on where the predicate first becomes True (tuple of dropWhile)
-- O(n)
-- ✅(empty list) -> total / safe
-- Python: (Note python does have a str.split() function that does something similar but across the entire string)
-- newlists = ([],[])
-- for i, x in enumerate(list):
--   if predicate(x):
--     newlists[1] = list[i:]
--   newlists[0].append(x)
break :: (a -> Bool) -> [a] -> ([a], [a])

-- Check if an element is a member of the list
-- O(n)
-- ✅(empty list) -> total / safe
-- Python: elem in list
elem :: a -> [a] -> Bool

-- Check if an element is not a member of the list
-- O(n)
-- ✅(empty list) -> total / safe
-- Python: elem not in list
notElem :: a -> [a] -> Bool

-- Go through every element in the list, if the predicate for the element is False, drop it from the list
-- O(n)
-- ✅(empty list) -> total / safe
-- Python: [x for x in list if predicate(x)]
filter :: (a -> Bool) -> [a] -> [a]

-- Checks if the first list is a prefix of the second list
-- O(n) where n is the length of the first list
-- ✅(empty list) -> total / safe
-- Python: second.startwith(first) # works for strings
isPrefixOf :: [a] -> [a] -> Bool

-- Checks if the first list is a suffix of the second list
-- O(n) where n is the length of the second list
-- ✅(empty list) -> total / safe
-- Python: second.endswith(first) # works for strings
isSuffixOf :: [a] -> [a] -> Bool

-- Checks if the first list is a sublist (substring for lists) of the second list
-- O(n) where n is the length of the second list
-- ✅(empty list) -> total / safe
-- Python: first in second # works for strings
isInfixOf :: [a] -> [a] -> Bool

-- Zips up the two lists into a list of 2-tuples with the length of the shortest list
-- O(n) where n is the length of the shortest list
-- ✅(empty list) -> total / safe
-- Python: zip(list1, list2)
zip :: [a] -> [b] -> [(a, b)]

-- Zips up the two lists but applies the function to the elements of the 2-tuple
-- O(n) where n is the length of the shortest list
-- ✅(empty list) -> total / safe
-- Python: [func(a,b) for a,b in zip(list1, list2)]
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

-- Zip up the k lists into a list of k-tuples with the length of the shortest list. Note k = [3..7]
-- O(n) where n is the length of the shortest list
-- ✅(empty list) -> total / safe
-- Python: zip(list1, list2, ..., listk)
zip3 :: [a] -> [b] -> [c] -> [(a, b, c)]
zip4 :: [a] -> [b] -> [c] -> [d] -> [(a,b,c,d)]
-- ...
zip7 :: [a] -> [b] -> [c] -> [d] -> [e] -> [f] -> [g] ->[(a, b, c, d, e, f, g)]

-- Zip up the k lists but apply the function to the elements of the k-tuple
-- O(n) where n is the length of the shortest list
-- ✅(empty list) -> total / safe
-- Python: [func(*x) for x in zip(list1, list2, ..., listk)]
zipWith3 :: (a -> b -> c -> d) -> [a] -> [b] -> [c] -> [d]
zipWith4 :: (a -> b -> c -> d -> e) -> [a] -> [b] -> [c] -> [d] -> [e]
-- ...
zipWith7 :: (a -> b -> c -> d -> e -> f -> g -> h) -> [a] -> [b] -> [c] -> [d] -> [e] -> [f] -> [g] ->[h]

-- Splits a string into a list of strings on the newline character '\n'
-- O(n)
-- ✅(empty list) -> total / safe
-- Python: str.split('\n')
lines :: String -> [String]

-- Returns a string with a newline character '\n' after every string in the list
-- O(nm) where n is the length of the list and m is the length of the strings in the list
-- ✅(empty list) -> total / safe
-- Python: '\n'.join(list_of_strings) + '\n
unlines :: [String] -> String

-- Splits a string into a list of strings on any whitespace character
-- O(n)
-- ✅(empty list) -> total / safe
-- Python: str.split()
words :: String -> [String]

-- Returns a string with a single space ' ' after every string in the list
-- O(nm) where n is the length of the list and m is the length of the strings in the list
-- ✅(empty list) -> total / safe
-- Python: ' '.join(list_of_strings)
unwords :: [String] -> String


-- Splits a string into a list of strings based on the predicate
-- O(n)
-- ✅(empty list) -> total / safe
-- Python:
-- newlist = []
-- for elem in list:
--     if predicate(elem):
--         if len(newlist[-1]) > 0:
--             newlist.append([])
--         continue
--     newlist[-1].append(elem)
splitWith :: (a -> Bool) -> [a] -> [[a]]
splitWith _ [] = []
splitWith f xs = [first] ++ splitWith f (dropWhile f second) 
    where 
        (first, second) = break f (dropWhile f xs)