Haskell

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:

Function Function

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-in length).
  • myReverse :: [t] -> [t]
    Returns the reversed form of a list (same as built-in reverse). 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.