Set Operations in Haskell

In this topic we are going to concentrate on following things

1. Introduction to implementation of sets and Set Operations
2. Functions related to construction of sets
3. Show tree functions on sets
4. Splitting functions of sets
5. Min / Max functions on sets
6. Conversion functions on sets
7. Query functions on sets
8. Combine functions on sets

Introduction to implementation of sets and set Operations

1. The implementation of Set is based on size balanced binary trees like AVL trees.
2. To implement set operations we must know corresponding algorithm Ex: for Union, Hedge union Algorithm
3. Must know the advanced concepts of Haskell like Tip, Bin, foldr, monoid, Foldable and many more concepts.
4. All set operations already implemented. Available in “Data.Set” Container of Haskell.

Functions related to construction of sets

Syntax: fromList :: [a] -> set a
Description: Creates a set from a list of elements.

Syntax: singleton :: a -> Set a
Description: Creates a singleton set with element ‘a’.

Syntax: insert :: a -> Set a -> Set a
Description: Insert an element in a set. If the set already contains an element equal to the given value, it is replaced with the new value.

Syntax: delete :: a -> Set a -> Set a
Description: Delete an element from a set.

Exercise-1: Construct a set S = {a, b, d, c, e} and delete ‘b’ from that set and add ‘f’ to set.

Exercise-2: Construct singleton set S = {0.123}. Add 9.8 to that set and delete 0.98 from that set.

Showing Tree functions on sets

Syntax: showTree:: Set a -> String
Description: Shows the compressed tree that implements set.

Syntax: showTreeWith:: Bool -> Bool -> Set a -> String
Description: shows the tree that implements the set. If hang is true, a hanging tree is shown. If wide is true, an extra wide version of tree is shown.

Exercise-1: From set S = {a, b, e, d, c} generate a string from which we can draw corresponding balanced tree.
Note: Use putStrLn Function

Splitting functions on sets

Syntax: partition ::(a -> Bool) -> Set a -> (Set a, Set a)
Description: Partition the set into two sets, one with all elements that satisfy the predicate and one with all elements that don't satisfy the predicate.

Syntax: split :: a -> Set a -> (Set a, Set a)
Description: The expression (split x set) is a pair (set1,set2) where set1 comprises the elements of set less than x and set2 comprises the elements of set greater than x.

Syntax: splitMember :: a -> Set a -> (Set a, Bool, Set a)
Description: Performs a split but also returns whether the pivot element was found in the original set.

Exercise-1: Divide the set S = {f, h, k, l, o, a, p, r, t} into two sets S1 and S2. Set S1 with elements less than ‘m’ and set S2 with elements greater than ‘m’.

Min / Max functions on sets

Syntax: findMin :: Set a -> a
Description: Returns the minimal element of a set.

Syntax: findMax :: Set a -> a
Description: Returns the maximal element of a set.

Syntax: deleteMin :: Set a -> Set a
Description: Delete the minimal element from set.

Syntax: deleteMax :: Set a -> Set a
Description: Delete the maximal element from set.

Syntax: deleteFindMin :: Set a -> (a, Set a)
Description: Finds and deletes the minimal element of set.

Syntax: deleteFindMax :: Set a -> (a, Set a)
Description: Finds and deletes the minimal element of set.

Exercise-1: Express the deleteFindMin in terms of findMin and deleteMin and give one suitable example.

Exercise-2: Express the deleteFindMax in terms of findMax and deleteMax and give one suitable example.

Conversion functions on sets

Syntax: elems :: Set a -> [a]
Description: Convert the set to a list of elements.

Syntax: toList :: Set a -> [a]
Description: Convert the set to a list of elements.

Query functions on sets

Syntax: null :: Set a -> Bool
Description: checks for given set is null or not.

Syntax: size :: Set a -> Int
Description: Returns the number of elements in the set.

Syntax: member :: a -> Set a -> Bool
Description: Checks for the given element belongs to set or not.

Syntax: notMember :: a -> Set a -> Bool
Description: Checks given element doesn’t belongs to set or not

Syntax: isSubsetOf :: Set a -> Set a -> Bool
Description: Checks for given set is subset or not.

Syntax: isProperSubsetOf :: Set a -> Set a -> Bool
Description: Checks for given set is subset or not.

Exercise-1: Write instruction to check {0.32, 0.21, 0.10} is proper subset of {0.10, 0.32, 0.21}?

Combine functions on sets

Syntax: union :: Set a -> Set a -> Set a
Description: Performs union operation on given two sets.

Syntax: unions :: [Set a] -> Set a
Description: Performs union operation on set of sets.

Syntax: intersection :: Set a -> Set a -> Set a
Description: performs intersection operation on given two sets.

Syntax: difference :: Set a -> Set a -> Set
Description: Finds the difference of given two sets.

Exercise-1: let S = {1, 3, 4, 6, 7} and T = {2, 5, 8, 9, 0, 4, 6}.
Write instruction to find n (S U T).

Exercise-2: let P = {1, 3, 4, 6, 7}, Q = {2, 5, 8, 9, 0, 4, 6} and R
= {2, 5, 6, 1, 3}. Write instruction to find n (P U Q U R).

Introduction To Haskell

Notion of functional programming

● Definition
- Treats computation as evaluation of mathematical functions and avoids state and mutable data

● Usefulness in academics
- Widely accepted in academics

● Predictability
- Result of computation is predictable as it will not have mutable data

Functional Programming Concepts

● First-Class or Higher-Order Function
- The functions can be passed as arguments and they can be returned as result
- partial application or currying

● Pure Functions
- Have no memory or I/O side effects

● Recursion
- Function calling itself

Background Of Haskell

● In 1930s, Alonzo Church developed lambda calculus Features include definition, application and recursion of function

● In 1950s, John McCarthy developed Lisp(List processor) generally regareded as first functional programming language influenced by lambda calculus but retaining variable assignments

●In 1960s, Peter Landin developed ISWIM (”If you See What I Mean”), the first pure functional language, based strongly on lambda calculus with no assignments

● In 1970s, John Backus developed FP, the functional language that emphasizes ”Higher order functions” and ”Reasoning about programs”


● Also in 1970s, Robin Milner and others developed ML (”Meta Language”) the first of the modern functional programming languages, which introduced the idea of polymorphic types and type inference

● In the 1970s and 1980s, David Turner developed a number of lazy functional programming languages, culminating in the commercially pro-duced language Miranda(”admirable”)

● In 1987, an international committee of researchers initiated the development of Haskell (named after the logician Haskell Curry), a standard lazy functional programming language

● In 2003, the committee published the definition of Haskell 98 , a stable version of Haskell that is the culmination of fifteen years of revisions and extensions to the language by its designers

Features of Haskell

● Concise Programs
- Haskell programs are often between two and ten times shorter than programs written in other current languages.

● Powerful Type System
- The Haskell type system is also more powerful than most current languages, by allowing functions to be “polymorphic” and “overloaded”

● Recursive Functions
- Pattern matching and Guards

● Higher Order Functions
- Composing two functions

● Monadic Effects
- Allowing side effects without affecting purity of functions

● Lazy Evaluation
- No computation should be performed until its result is actually required
- Allows program to terminate whenever needed

● Reasoning About Programs
- Simple evaluational reasoning can be used to execute programs, transform programs, prove properties of programs and even to derive programs directly from specifications of their behavior

Platforms For Haskell

● Haskell Compiler
   GHC

● Haskell Interpreters
   GHCi
   HUGS

Glassgow Haskell Compiler

● GHC is a standard Haskell compiler, which compiles Haskell code either by using an intermediate C compiler (GCC) or by generating native code on some platforms.

Command to compile Haskell program using GHC
# ghc -- make Simple.hs -o Simple

Where ”-- make” is an option informing GHC that ”Simple.hs” is a program to be compiled ”-o” specifies the output file as ”Simple”

The above output file can be executed as follows
#./Simple

Glassgow Haskell Compiler Interactive

● “GHCi” is an acronym for “Glasgow Haskell Compiler
Interactive”

● GHCi comes along with GHC. It is an powerful interpreter which get loaded with default standard Haskell script ”Prelude.hs”

● This script contains definitions of many useful basic functions.

● GHCi can be launched by issuing following command on the system which has GHC platform installed
# ghci

● When ghci starts it loads default package Prelude.hs and displayed the following prompt
Prelude>

Haskell User's Gofer System

● HUGS is a byte code interpreter for the functional programming
language Haskell.

● It offers fast compilation of programs and reasonable execution speed.

● It is the most portable and lightweight of the Haskell implementations.

●  It can be launched by issuing following command on the system
on which HUGS is installed
# hugs

● As in case with ghci when hugs system starts it also loads default
package ”Prelude.hs” and displays following prompt
Hugs>

Some useful commands for Interpreter

● In follwing cases ”>” indicates interpreter prompt
> :? ------------ Help command

> :load File.hs ------------ This command will load a Haskell script file with name ”File.hs” and will execute it. It's alternative is ”:l File.hs”

>:reload [File.hs] ------------- This command will reload a Haskell script file with name ”File.hs” and will execute it. It's alternative is ”:r File.hs”. Here file name is optional. If file name is not specified then previously loaded file will be reloaded

>:type ----------- This will return the type of the expression specified as . It's alternative is ”:t ”
 
>:quit -------------- This is used to quit from the Haskell prompt  

● Hugs system as calculator
 
- As mentioned previously when hugs system starts it displays following prompt.
 
Hugs>
 
Above prompt can be used as calculator as follows
 
Hugs> 4*2 + 5 ^ 2 – 8 / 2
29
 
Here ”^” is exponentiation operator
 
The expression is evaluated according to precedence ^, *,/,+,-
 
Where ^ has higher precedence and – has lowest.
 
Here ”29” is the output of the expression evaluation.
Hugs System
 
● Try out following commands at the Hugs interpreter prompt
and state what the function is doing by analyzing the output
 
Hugs> length [1..5]
Hugs> length []
Hugs> sum [1,2,3,4,6,8]
Hugs> product [1..5]
Hugs> [1,2,3,4,5] ++ [1..5]
Hugs> div 1 5
Hugs> 1 `div` 0
 
Haskell script Structure
 
● Following is the layout of the Haskell script presented in square box.
   -- module <Module Name>
   -- where
   -- Variable assignments
   -- Function definition
 
In above layout each line is started with -- to indicate the
comment line.

The first part of the script is module declaration which is declared using ”module ” clause
 
Module declaration is followed by where clause which indicate the start of usable contents of the scrips such as variable and function definition

Next part of the script is variable definition which is specified as
follows
var_name =

Last part is function definition whose structure and syntax will be explained later.
 
The script should be saved with .hs extension.
 
All parts are optional.
 
Naming Conventions in the Haskell

● Naming conventions for the functions and variables are same. The function or variable name must begin with a lower-case letter, but can then be followed by zero or more letters (both lower and upper-case), digits, underscores, and forward single quotes. For example, the following are all valid names: 
 myFun, fun1, arg2, x'
 
● The following list of keywords have a special meaning in the language, and cannot be used as the names of functions or their arguments: 
case class data default deriving do else if import in infix infixl infixr instance let module newtype of then type where
 
Comments In Haskell
 
● Single line comment 
'--' This is the single line comment
 
● Multi-line or Nested comment
{-
This is a multi-line comment
This comment can be nested
-}
 
Function Definition and application
 
● function definition and function application is base of the functional programming
 
● Layout of a function in Haskell
    
   <Function type Declaration>
  
   <Function Definition>

Examples :
fun :: Int -> Int
fun x = x
 

Function Type Specification

● Function is a mapping from input to output

● The input may have some type and output also

● Function type specification in Haskell

● Syntax :
    fun_name ::<INPUT1> -> .. -><INPUTn> -> <OUTPUT>

 

Here INPUT1 to INPUTn are types of arguments to function OUTPUT is the type of result from the function

Example :
compare :: Int -> Int -> Bool
 

Function Definition

● Function definition – behavior of function

● Arguments passing

● Syntax :
    fun_name ... = {-
                                Body of function
                             -}

Example :
                    compare a b = if (a > b)
                                             then a
                                             else b
 

Basic Operators

● Conditional operators
     == Equality operator
     /=  Non equality operator
     >=  Greater than or equal to operator
     <=  Less than or equal to operator 

     >  Greater than operator
     <  Less than operator

●

Assignment operator
    = Assignment operator

Haskell in Logic Programming
 

The following logical operations are implemented in Haskell

● not Operation
● and Operation
● or Operation
● implication Operation
● equivalence Operation
● Combination of all logical operation