Haskell Problems Solved..

APIIT Haskell Prolog Exam, APLC exam, questions and answers

2009-06-11T12:33:00.000-07:00

Compare and contrast functional and imperative programming languages ( 10 marks)

Functional programming works by evaluating expressions, its stateless and deals with immutable data. In contrast imperative works with statements, which when executed alters its global state. Functional programming requires the functions to be treated more or less like any other value, that can be passed or returned from a function, this concept is also regarded as functions being first-class. Further more this allows functions to be nested in code blocks called closures, these functions are as easy called or manipulated as any other function. Imperative languages like C/C++ lacks this capability.

example of an expression
project x (a,b,c) = (a, x,(projectDataColumns x (a,b,c)))
example of an statement
p += 15;
example of a closure in haskell
f x = (\y -> x + y)

Imperative languages has no implementation of referential transparency, i.e the output of an expression might be different based on the state of execution, resulting in side effects. Functional languages has its roots in Lambda Calculus, i.e the functions implementations mimic that of mathematical function notations. This ensures that calling a function say 'f' and passing it the value x once or multiple times will always result in the same answer f(x), eliminating side effects. Functions without side effects make code easy to understand and less prone to error.

Iterations are handled very differently in functional and imperative languages. Imperative languages use the more traditional approach, which utilizes the use of loops (for, while, do, etc), whereas in functional languages iteration is carried out via the use of tail recursions or list comprehensions. To illustrate this principle lets look at a nest for loop.

Imperative approach

for($i=1;$i<=12;$i++)
{
for($j=1;$j<=12;$j++)
{
$string .= $i*$j;
}
}

The above code calculates the answer to the multiplication table from 1 to 12. In Haskell this code can be implemented using list comprehensions illustrated below.

[x*y|x<-[1..12],y<-[1..12]]

Functional Programming offers more support to create structured programming than imperative languages, which is essential for abstractions and creating of components, facilitating code reuse. For example its easy to abstract out a recursive bit of code in a high order function which will make the code more declarative and comprehensive.

Functional programming languages like Haskell has automatic garbage collection, imperative languages like C/C++ doesn't have this feature. Having manual memory management means the code will be prone to memory leaks, this pitfall is avoided in functional languages, therefor the program is less likely to crash because of memory leaks.

5 concepts of functional programming languages (10 marks)

Higher Order Functions, when functions return other functions or accept other functions as arguments these are called higher order functions. For example, given a function to double an integer.

Double::Int->Int
Double x = x* 2

The prelude function Map. can take this function as a parameter as illustrated below

xs = [ 1,3,5,6]

doubleList xs = map double xs

This applies the double function to each element of the list xs. The function Map takes function Double as a parameter.

Pure Functions, these functions are functions that have no side effects, i.e they will only return values not yield other actions.(modify state).

for example a function a function that changes degree Celsius to degree Fahrenheit is a pure function, and conversion of exchange rate, MYR to USD is an impure function, it depends on a lot of external factors, i.e, the answer can be different time to time.

Lazy Evaluation, evaluation takes place only when required. It will only evaluate an argument to a function if that's arguments value is needed to compute the overall result. If the argument is structured, i.e if its a tuple or a list, it will only evaluate those parts that are needed.

an example of lazy evaluation is illustrated below.

x = fst ( sqrt(16), sqrt(9)

here the only the first part sqrt(16) get evaluated, the other part is ignored.

Currying, This is transforming a function that takes multiple arguments in such a way that it can be called with a chain of functions each with a single argument. An non-curried function's arguments would probably contain tuples.

an example of an curried function is illustrated below.

Multiply m n = m*n

non - curried version of this would look like this.

Mutilply (m,n) = m*n

The curried version can accept one argument and return a function. this function is a higher order function.

Referential Transparency, this means the function always evaluates the same no matter what the context is. There are no side-effects and it does not depend on the state.
for example the mathematical function sin(x) is transparent, i.e it returns the same value for sin(x) no matter what the context is. however the expression x++; ( x = x+1) is not transparent because it alters the value in variable x.

Explain The term Tuple in context of functional Programming paradigm, Give 3 examples? (5 marks)

Tuples is a way to storing multiple values in a single value. But it requires you to know exactly how many values are to be stored in the tuple. In functional programming languages tuples are useful when we want to return multiple values from a function, or it a can even be used as a primitive data type.

example 1: tuples can be used in a function to return cordinates.

Cordinates :: Int->Int->(Int,Int)
Cordinates x y = (x,y)

example 2: Returning compound result, min and max from 2 Ints

minAndMax :: Int -> Int -> (Int, Int)
minAndMax x y
| x >= y = (y, x)
| otherwise = (x, y)

example 3: Functions over tuples, for pattern matching.

addPair :: (Int, Int)-> Int
addPair (x,y) = x+y

Critically access any 3 Characteristics of procedural Programming Languages and include 2 possible benefits.( 16 marks)

Procedural languages are based on procedures (also known as routines or subroutines),
consisting of a series of computational steps to be carried out. It evaluates the code sequentially ( one way) and is a combination of variables, loops and functions.

Characteristics.

Modularity, Procedural languages allows the code to be modular, a function that is used to perform a certain task can be used over and over again with out repeating the code. Modules ensure separation of concerns, this improves maintainability and future expansion.

Having the codes in modules makes it really easy to manage, and encourages code reuse, same code can be implemented in multiple projects via libraries.

Scoping , in specially large systems, involving a lot of variables being passed around in functions, scoping can be very helpful, in ensures that the variables used in function stays within that function. procedures cant use variable from other procedures or another instance of the same procedure without explicit permission.

example to illustrate basic scoping in procedural languages.

//code

var variable1

function A{

var variabe2;

function C{}
}

function B {

}

In the code illustrated above, variable1 is a global variable accessible to all functions, bu variable2 can only be accessed by function A and C. Similarly function C is not available to function B.

Incremental State, most procedural languages have incremental state as a function of time, i.e the state alters as the program is executed and as the user interacts with it.

Benefits

Simplicity , Procedural languages are simple compared to declarative, they offer a clear and concise solution, specially when considering simple tasks, it doesn't force you to create objects or classes to do a simple task ( as some object oriented languages like java do).

Efficiency, procedural languages are more efficiently translated into machine language, and they run more efficiently because the level of abstraction is low, in other programming paradigms like declarative the level of abstraction is very high, its more similar to a natural language which translates less efficiently into machine code.

Critically access any 3 characteristics of declarative programming languages ? ( 9 marks)

Dynamically typed, declarative programming languages are dynamically typed, i.e variable types and function types are accessed only at run time, therefore some type checks are left for run time. This can be a good thing and a bad thing depending on ones point of view.

Bad, because it offers comparatively less documentation, specially if its a large project. This can also help catch errors at compile time.

Good, because very frequently in a statically typed language to do computations manual type casting is required this brings, and often it makes it prone compiler errors. Dynamically typed languages eliminate this pitfall.

Minimize side effects, a declarative language tries to minimize or eliminate side effects completely, it accomplishes it by describing what to do, instead on describing how to go about doing this task, which is what an imperative language would do by implementing a detail description of the algorithm.

Single Assignment, in declarative languages variables can only have one value assigned to them and this cannot be altered during program execution. This is called non-destructive assignment. This encourages the use of recursive techniques.

Program flow, the flow of the program is not determined by control structures, it is left to the language it self. This minimizes logic errors that may occur if a programmer decided to implement this. This is true for other programming paradigms like imperative languages. Further more order of how execution of code is irrelevant.

Critically assess the current use of prolog lanaugage, identify 5 areas where the prolog language plays an important role. (10 marks)

Expert Systems, prolog is used in expert systems, for example it can be used to study and monitor traffic. and provide intelligent traffic control systems, controlling traffic light times and synchronizations based on statistical data collected overtime. Another example would be a medial expert system.

Natural Language Processing, Prolog is very suitable to parse and do natural language processing. It is used to create spelling correctors or applications that seek out grammetical errors.

Robotics, prolog is used in robotics to write create AI programs.

Intelligent Systems.

Knowledge representation and reasoning,

Pattern matching,

Planning and Search. i.e. Prolog is good at Symbolic AI

Function to the exponent of a value. ( 25 marks )

Power :: Float->Float->Float // function definition
Power m n //function declaration, m^n, where n is exponent
| n == 0 = 1 //any integer to the power of 0 is 1
| m == 0 = 0 //0 to the power any integer is 0
| n > 0 = m * power m (n-1) //positive powers
| otherwise = (1 /m) * power m(n+1) //negative powers

Finding out weather a number is odd or even (25 marks)

oddEven :: Int -> String //function definition
oddEven m //function declaration, m is the input
| m == 0 = "Even" // 0 is even
| (mod m 2) == 0 = "Even" // even numbers are divisible by 2
| otherwise = "Odd" //if its not an even number thats make it odd.

Using if and else construct a recursive function to compare y = x ^ n, where n > 0 and is out type integer ? ( 10 marks )

toPower :: Float -> Float -> Float
toPower m n =
if (n > 0)
then
m * power m (n-1)
else
1

APIIT haskell Assignment in 16 lines of code

2009-06-11T12:28:00.000-07:00

1 >type Table = ( String, [String], [[String]])
2 >top10 = ("LargestCountries",[ "Rank","Country", "Area"],[ [ "1", "Russia", "17075400"] , [ "2", "Canada", "9976140"] , [ "3", "United States", "9629091"] , [ "4", "China", "9596960"] , [ "5", "Brazil", "8511965"] , [ "6", "Australia", "7686850"] , [ "7", "India", "3287590"] , [ "8", "Argentina", "2776890"] , [ "9", "Kazakhstan", "2717306"] , [ "10", "Sudan", "2505810"]] )
3 formatSingleRow [][] = "|"
4 formatSingleRow (x:xs) (y:ys) = "| " ++ addSpace y x ++ formatSingleRow xs ys where addSpace a b | length b > a = b | otherwise = addSpace (a-1) b ++ " "
5 formatValues [] _ = "\n"
6 >formatValues ((x:xs)) (y:ys) = formatSingleRow x (y:ys) ++ "\n" ++ formatValues xs (y:ys)
7 >writeTable (x,y,z) = x ++ "\n\n" ++ formatHeader y ([ a+10|(a)<-(map length y)]) ++ formatValues z ([ a+10|(a)<-(map length y)]) where formatHeader x y = formatSingleRow x y ++ "\n" ++ addLine ((length y)*18) "-" ++ "\n" where addLine a b | length b == a = b |otherwise = b ++ addLine (a - 1) b
--the prgram logic
8 >printTable = putStr.writeTable
9 >filterByIndex [] _ = []
10 >filterByIndex (x:xs) y = [[value]|(value,ind)<-(zip x [0..]),ind==y] ++ filterByIndex xs y
11 >addListofLists x [] = x
12 >addListofLists (x:xs) (y:ys) = [[ a |a<-x] ++ [ b |b<-y ]] ++ addListofLists xs ys
13 >filterListofLists [] _ = []
14 >filterListofLists (x:xs) (a,b,c) = addListofLists (filterByIndex c (idx x b)) (filterListofLists xs (a,b,c)) where idx x y = [ind|(value,ind)<-(zip y [0..]),value==x]!!0 --gets index of list
15 >project x (a,b,c) = (a, x,(filterListofLists x (a,b,c)))
16 >select feild condition (a,b,c) = (a,b,((filter (\x -> condition (x!!(idx feild b))))c)) where idx x y = [ind|(value,ind)<-(zip y [0..]),value==x]!!0 -- gets index of list

APIIT haskell Assignment

2009-06-11T12:26:00.000-07:00

type Table = ( String, [String], [[String]])
top10:: Table
top10 = ("LargestCountries",[ "Rank","Country", "Area"],[ [ "1", "Russia", "17075400"] , [ "2", "Canada", "9976140"] , [ "3", "United States", "9629091"] , [ "4", "China", "9596960"] , [ "5", "Brazil", "8511965"] , [ "6", "Australia", "7686850"] , [ "7", "India", "3287590"] , [ "8", "Argentina", "2776890"] , [ "9", "Kazakhstan", "2717306"] , [ "10", "Sudan", "2505810"]] )

-- DYNAMIC FORMATING

formatSingleRow :: [String] -> [Int] -> String -- formats a single row
formatSingleRow [][] = "|"
formatSingleRow (x:xs) (y:ys) = "| " ++ addSpace y x ++ formatSingleRow xs ys
where addSpace a b | length b > a = b | otherwise = addSpace (a-1) b ++ " " --adds white space based on the length of the string in the data feild

formatValues :: [[String]] -> [Int] -> String --formats records via formatsingrow function
formatValues [] _ = "\n"
formatValues ((x:xs)) (y:ys) = formatSingleRow x (y:ys) ++ "\n" ++ formatValues xs (y:ys)

writeTable :: Table -> String -- converts the table to a string
writeTable (x,y,z) = x ++ "\n\n" ++ formatHeader y ([ a+10|(a)<-(map length y)]) ++ formatValues z ([ a+10|(a)<-(map length y)]) --format column names and calls the formatValues function to format data
where formatHeader x y = formatSingleRow x y ++ "\n" ++ addLine ((length y)*18) "-" ++ "\n" -- header is formated using formatSingleRows function then a line is added underneath it
where addLine a b | length b == a = b |otherwise = b ++ addLine (a - 1) b -- calulates the length on this line. this can be different depending on how many columns are printed
-- END FORMATING

printTable::Table->IO() -- prints table
printTable = putStr.writeTable

--SELECTION OF COLUMNS

--filters a list of lists (i.e the data portion of the Table to output a single column based on index of the list
--using primitve recursions over lists.
--this function using the zip function to make tupes to identify the index of the list

filterByIndex::[[String]]->Int->[[String]]
filterByIndex [] _ = []
filterByIndex (x:xs) y = [[value]|(value,ind)<-(zip x [0..]),ind==y] ++ filterByIndex xs y

--adds a lists of lists to another list of lists , i.e adds to columns such as "Rank" and "Country"
--the tradition "++" function will not add it correctly it will just append one list to another
--this function mimics the Zip functions fuctionality but it stead of tupes it returns a list of lists
--with in the list comprehension, an attemp was made first to use "++", wh but it causes winHugs to crash after a few
--adds white space based on the length of the string in the data feild runs, so current method was implemented.
--the cause of this error is not know, possibly a bug in the compliler.

addListofLists::[[String]]->[[String]]->[[String]]
addListofLists x [] = x
addListofLists (x:xs) (y:ys) = [[ a |a<-x] ++ [ b |b<-y ]] ++ addListofLists xs ys

-- filters list based on given field names eg ["Rank","Country"], given table name
-- this function can take any number of feilds to filter, it can have dulplicate feilds too.
-- it then filters the data with a help "idx"
-- the purpose of "idx" is to get the index of the columns that need to be filtered
-- this index values will match those of the data fields. which then are selected
-- "idx" using zip function from the prelude library to create tuples for the indexing process
-- multiple columns are achieved with the help of primitive recursion over lists
-- feild names should match that of the table, eg:- if "Rank" was renamed to "id" in table schema
-- then that change should be reflected when calling the function, ["id","Country"]

projectDataColumns :: [String] -> Table -> [[String]]
projectDataColumns [] _ = []
projectDataColumns (x:xs) (a,b,c) = addListofLists (filterByIndex c (idx x b)) (projectDataColumns xs (a,b,c))
where idx x y = [ind|(value,ind)<-(zip y [0..]),value==x]!!0

-- this is the function that acutally prints outs the columns,
-- function definition would match that of the assignment question
-- it takes in feild names and table name as parameters
-- pattern matching is used to split the table in to a,b,c
-- of which "b" is replaced by the feilds requested byt he user, which is input X
-- "c" is the data portion which is filtered based on X using the previously defined functions
-- to test this function use any of the following lines of code
-- printTable.project["Rank", "Country"]$top10
-- printTable.project["Rank", "Country", "Area"]$top10
-- printTable.project["Rank", "Area", "Country", "Area"]$top10

project::[String]->Table->Table
project x (a,b,c) = (a, x,(projectDataColumns x (a,b,c)))

--SELECTION OF ROWS

-- this function filters the data rows based on a user defined predicate
-- (String->Bool) , it uses the "idx" function that was used in the
-- project data columns function
-- it uses the lambda notation to filter rows based on the user given
-- predicate, it can take in any feild name to fitler the data
-- eg, "Rank", "Country", "Area"
-- this fucntion uses a combination of prelude funtions such as zip, filter,!!
-- and pattern matching to accomplish its goal.
-- to test the function the folling code can be tried on winHugs
-- printTable.select "Rank" p $ top10 where p x = read x < (6::Int)
-- filters less than 6 on rank field
-- printTable.select "Rank" p $ top10
-- where p x = ( read x < (6::Int) && read x > (2::Int) )
-- filters countires with rank between 2 and 6, not inclusive
-- printTable.select "Rank" p $ top10 where p x = read x == (7::Int)
-- gets country with rank 7
-- printTable.select "Country" p $ top10 where p x = x == "Australia"
-- gets row for Australia
-- printTable.select "Area" p $ top10 where p x = read x < (10000000::Int)
-- gets countries with Area less than 10000000

select::String->(String->Bool)->Table->Table
select feild condition (a,b,c) = (a,b,((filter (\x -> condition (x!!(idx feild b))))c))
where idx x y = [ind|(value,ind)<-(zip y [0..]),value==x]!!0

Raising a number to the power of another number. exponent. in haskell

2009-02-28T07:19:00.000-08:00

power :: Float -> Float -> Float

power m n

| n == 0 = 1

| n > 0 = m* power m (n-1)

| otherwise = (1 / m)* power m (n+1)

finding the highest common factor/divisor for two integers in haskell

2009-02-27T10:16:00.000-08:00

hcf :: Int -> Int -> Int

--handles all cases of zero

hcf 0 0 = undefined

hcf m 0 = abs m

hcf 0 n = abs n

hcf m n

| m == n = m

| m > n = hcf n (rem m n)

| otherwise = hcf n m

fibonacci sequence in haskell : not very efficient

2009-02-27T09:42:00.000-08:00

fib :: Int -> Int

fib n

| n == 0 = 0

| n == 1 = 1

| n > 1 = fib (n - 2) + fib (n - 1)

Integer square root of a positive integer in haskell

2009-02-27T09:38:00.000-08:00

squareRoot :: Int -> Int

squareRoot n

| n == 1 = 1

| otherwise = div (k + ( div n k)) 2

where k = squareRoot(n-1)

Using recursive addition to multiply in haskell

2009-02-27T09:35:00.000-08:00

multiply :: Int -> Int -> Int

multiply m n

| n >= 1 = m + multiply (n-1) m

| otherwise = 0

Finding the factorial in haskell.

2009-02-27T09:33:00.000-08:00

rangeProduct :: Float -> Float -> Float

rangeProduct m n

| m>n = 0

| m==n = m

| otherwise = m * rangeProduct (m+1) n

--4.6 Factorial

factorial :: Float -> Float

factorial n

| n == 0 = 1

| otherwise = rangeProduct 1 n

finding out how many are equal amongst three numnbers in haskell

2009-02-27T08:57:00.000-08:00

howManyEqual :: Int -> Int -> Int -> Int

howManyEqual x y z

|((equal x y) + (equal y z) + (equal x z)) == 1 = 2

| otherwise = (equal x y) + (equal y z) + (equal x z)

equal :: Int -> Int -> Int

equal x y

| x == y = 1

| otherwise = 0

Finding max of two, three or four in haskell

2009-02-27T08:56:00.000-08:00

maxTwo :: Int -> Int -> Int

maxTwo x y

| x>y = x

| otherwise = y

maxThree :: Int -> Int -> Int -> Int

maxThree x y z

|maxTwo x y > z = maxTwo x y

|otherwise = z

maxFour :: Int -> Int -> Int -> Int -> Int

maxFour v x y z

| maxThree v x y > z = maxThree v x y

| otherwise = z

Finding the number of roots in a quadratic equation in haskell

2009-02-27T08:52:00.000-08:00

rootFunction :: Float -> Float -> Float -> Int

rootFunction a b c

| a == 0 = dRoots a b c

| otherwise = numberNDroots a b c

numberNDroots :: Float -> Float -> Float -> Int

numberNDroots a b c

| b^2 > (4.0*a*c) = 2

| b^2 == (4.0*a*c) = 1

| b^2 < (4.0*a*c) = 0

dRoots :: Float -> Float -> Float -> Int

dRoots a b c

| b /= 0 = 1

| b == 0 && c /= 0 = 0

| b == 0 && c == 0 = 3

Finding the average of three numbers in haskell

2009-02-27T08:46:00.000-08:00

averageThree :: Float -> Float -> Float -> Float

averageThree a b c = (a + (b + c))/3.0

isAbove :: Float -> Float -> Int

isAbove a avg

| a > avg = 1

| otherwise = 0

numAbove :: Float -> Float -> Float -> Int

numAbove a b c = (isAbove a avg) + (isAbove b avg) + (isAbove c avg)

where

avg = averageThree a b c