Notes - Functional Programming MT22, Common functions

Created: May 23, 2023

Flashcards

Can you give the definition of cp (cartesian product) in Haskell (not as a fold)?

 
cp ;; [[a]] -> [[a]]
cp [] = [[]]
cp (xs:xss) = [x:ys | x <- xs, ys <- cp xss]

Can you give the definition of subsets which returns all the subsets of a given list in Haskell (not a fold)?

 
subsets ;; [a] -> [[a]]
subsets [] = [[]]
subsets (x:xs) = [zs | ys <- subsets xs, zs <- [ys, (x:ys)]]

Can you give the definition of subsetsN which returns all the subsets of a list with size exactly n in Haskell?

 
subsetsN ;; Int -> [a] -> [[a]]
subsetsN 0 _ = [[]]
subsetsN _ [] = []
subsetsN n (x:xs) =
	[ x:ys | ys <- subsetsN (n-1) xs ]
	++ subsetsN n xs

Can you give the definition of filterDups which removes all duplicate elements from a list in Haskell?

 
filterDups ;; Eq a => [a] -> [a]
filterDups xs = filterDups' xs []
    where filterDups' [] _ = []
          filterDups' (x:xs) seen
          | x `elem` seen = filterDups' xs seen
          | otherwise     = x:filterDups' xs (x:seen)

Can you give the definition of transpose which tranposes a multidimensional list in Haskell?

 
transpose ;; [[a]] -> [[a]]
transpose xss
	| all null xss = []
	| otherwise    = col xss : transpose (map tail xss)
	    where col = map head


Related posts