Haskell Intro Lab
Introduction
The purpose of this lab is to gain experience programming in Haskell. Unlike other assignments in this class, it is ok to work on the code for this lab in teams or groups.
Haskell is a functional language, which means that the fundamental computational paradigm consists of functions that provide mappings from inputs to outputs:
Functional programs consist of many smaller functions that are chained or composed. Iteration is accomplished using recursion. To effectively use Haskell, you must shift away from thinking about how the machine should solve your problem (as you had to with procedural programming) and focus on defining the solution to the problem in a mathematically rigorous way.
In Haskell, variable bindings are permanent and all types are statically bound at compile time. Haskell programs are stateless, and I/O is accomplished using special wrappers to encapsulate the side effects. Functions are evaluated using lazy (or non-strict) evaluation.
In this lab, we will use ghci
, which is an interactive
interpreter for Haskell (similar to irb
for Ruby). Because of the
lack of traditional procedural I/O in Haskell, we will concentrate on writing
functions rather than programs.
Part 1
Open a terminal window, navigate to a working directory, and run
ghci
. Follow along as we experiment with basic Haskell constructs.
Exercises:
- Write a list comprehension that produces all the numbers between 1 and 100 that are multiples of 2, 3, and 5.
- Write a list comprehension to generate all the pairs of numbers between 1 and 20 that add up to 20.
Part 2
Create a file called intro.hs
and run ghci
in the
same folder. You can load the file into ghci
using the following
command:
:load intro.hs
Open the file in a text editor of your choice (I recommend nano or vim).
Thereafter, you can re-load the file after you edit it using the :r
command.
Write Haskell functions inside intro.hs
that fit the following
specifications:
square :: Num a => a -> a
Returns the mathematical square of the input.sumOfFirstN :: Num a => a -> a
Returns the sum of the first n natural numbers.oddsUpTo :: Integral t => t -> [t]
Returns all positive odd numbers up to (and possibly including) all positive odd numbers up to (and possibly including) n.factorial :: Num a => a -> a
Returns n!.myLength :: Num a => [t] -> a
Returns the length of a list (same as built-inlength
).myReverse :: [t] -> [t]
Returns the reversed form of a list (same as built-inreverse
). Try implementing this with a fold.fib :: Num a => a -> a
Returns the nth Fibonacci number. Write this function the simple way first, using the definition of Fibonacci numbers. Then write an accumulator-based version, which should be significantly faster.indexOf :: (Num a, Eq b) => b -> [b] -> a
Returns the first index of a value in a list (or -1 if it is not present). For example,indexOf 'o' "helloworld"
is 4.eachIndexOf :: (Num a, Eq b) => b -> [b] -> [a]
Returns a list of all indices of a value in a list (or [] if it is not present). For example,eachIndexOf 'o' "helloworld"
is [4,6].myReplicate :: Int -> a -> a
Takes a count and an element, and returns a list that consists of the given element repeated the specified number of times. For example,myReplicate 5 'a'
is "aaaaa".myZip :: [a] -> [b] -> [(a,b)]
Takes two lists and "zips" them together into pairs of corresponding elements. For example,myZip [1,2,3] "abc"
is [(1,'a'), (2,'b'), (3,'c')]. If either of the lists is shorter than the other, the remaining items from the longer list should be discarded. For example,myZip [1,2] "abc"
is [(1,'a'), (2,'b')].qsort :: Ord t => [t] -> [t]
Returns a sorted version of the given list, using the standard quicksort definition. Hint: use the first element of the list as the pivot, and use list comprehensions to separate all of the remaining items into two lists: lesser items and greater items. Then recurse on each list separately and re-combine the results using the "++" operator.coord :: a -> b -> c -> (a, b, c)
Takes three parameters x, y, and z, and returns a tuple representing a coordinate in 3d space.double :: Int -> Int
Returns double the value of its parameter.doubleList :: [Int] -> [Int]
Returns a list with the double of every value from the given list.applyToList :: (a -> a) -> [a] -> [b]
Applies the given function to every element in the given list and returns a list of all the results.longestStr :: [String] -> String
Returns the longest string from a list of strings. Try using a fold to implement this.
While working on the PAs, you may wish to look over a reference to the Haskell Prelude module.
Submission
Submit your completed intro.hs
script on Canvas. Please
include a comment at the top with your name. If you worked in a group with
others, make sure that everyone's name is listed in the file and that everyone
gets a copy to submit on Canvas.