Haskell CheatSheet-(Modules & List intersection/List product)

Haskell Modules

A Haskell module is a collection of functions and type definitions that can be used by other Haskell programs. Most other programming languages have a similar technical concept, sometimes called a module and sometimes called a package.

import Data.List
-- can now use functions inside Data.List module

Combination ( C )

choose :: Integer -> Integer -> Integer
choose x y = product [x-y+1..x] `div` product [1..y]
-- choose 6 3 -> gives us 20 (4*5*6/1*2*3)

Importing modules

If you want to create a module that can be used outside your program, you should add some code on the top of your code.

For Example, exports the Set module:

module Set
where
-- your code goes here below

All of the definitions below this are part of a new Set module, making them available in any Haskell program which imports this Set module.

Switch back to Main.hs and add a line to import the new module now. After this, you will be able to access the module's definitions when you open up ghci.

List Intersection & product

module Set
where
-- This module implements sets as ordered lists without duplicates.
-- The implementation is mainly for instructional purposes; a better
-- set implementation (using size balanced binary trees) is available
-- through the Data.Set library.
import Data.List
data Set a = Set [a]
  deriving (Eq, Show)
-- functions for building sets
set :: Ord a => [a] -> Set a
set es
  = Set (nub (sort es))
emptyset :: Set a
emptyset
  = Set []
set_insert :: (Ord a) => a -> Set a -> Set a
set_insert x (Set es)
  = set (x:es)
set_delete :: Ord a => a -> Set a -> Set a
set_delete x (Set es)
  | x `set_elem` (Set es) = Set (delete x es)
  | otherwise             = Set es
-- functions for investigating sets
set_size :: Set a -> Int
set_size (Set es)
  = length es
set_empty :: Set a -> Bool
set_empty (Set es)
  = null es
set_elem :: (Ord a) => a -> Set a -> Bool
set_elem x (Set es)
  = elem x (takeWhile (<=x) es)
set_elements :: Ord a => Set a -> [a]
set_elements (Set es)
  = es
-- functions implementing set operations
set_subset :: (Ord a) => Set a -> Set a -> Bool
set_subset (Set es) b
  = all (`set_elem` b) es
set_union :: (Ord a) => Set a -> Set a -> Set a
set_union (Set xs) (Set ys)
  = set (xs ++ ys)

• Alphabet Soup

This example function takes two words as input and checks whether those words are spelled with the exact same set of characters.

import Set
same_letters :: String -> String -> Bool
same_letters x y = (set x)==(set y)
-- same_letters "abc" "ab" -> gives False

• List Intersection

The intersection of two sets A and B is the set containing all elements that are in both A and B.

set_intersect :: Ord a => Set a -> Set a -> Set a
-- base case
set_intersect (Set []) (Set y) = Set []
-- recursive approach, go through every element in Set x to check if -- it exists in y
set_intersect (Set (x:xs)) (Set ys)
    | set_elem x (Set ys) = set ([x] ++ set_elements (set_intersect (Set xs) (Set ys)))
    |otherwise = set_intersect (Set xs) (Set ys)
-- set_intersect (set [1,2,3,4]) (set [3,4,5,6]) -> gives [3,4]

• List Product (Cartesian Product)

The Cartesian product of two sets A and B, denoted A×B, is a set containing all possible tuples of elements with the first element drawn from A and the second element drawn from B.

For example, if A={1,2,3} and B={a,b}, then

A×B={(1,a),(1,b),(2,a),(2,b),(3,a),(3,b)}

set_product :: (Ord a) => (Ord b) => Set a -> Set b -> Set (a,b)
-- base case
set_product (Set []) (Set ys) = Set []
-- recursive approach, also use map function to iterate through the -- array
set_product (Set (x:xs)) (Set ys)
    = set ((map (helper x) ys) ++ set_elements (set_product (Set xs) (Set ys)))
-- helper function to convert a,b -> (a,b)
helper :: a -> b -> (a, b)
helper x y = (x, y)
-- set_product (set [1,2]) (set ["a", "b"]) -> gives
                       Set [(1,"a"), (1,"b"), (2,"a"), (2,"b")]