Programming in haskell - Ch1

Programming in haskell - Ch1 - Introduction

by @ardumont on 23 Dec 2012

It has been some time now (almost 2 years during my free time) that I:

renewed with Functional Programming.
learn clojure (I do not know all of it yet but i know enough to say, this is the way!)
discovered the wonders of the Lisp family (i did learn some common-lisp through the Land of Lisp and some emacs-lisp through Emacs's most amazing setup power)

Now, for the time being, I'd like to go and see what Haskell is all about. So here it is. I began reading Programming in haskell.

Here are my solutions to the exercises. I did not yet confront them.

Calculation

Give another possible calculation for the result of double (double 2).

double (double 2) = (double 2) + (double 2)
                  = (double 2) + (2 + 2)
                  = (double 2) + 4
                  = (2 + 2) + 4
                  = 4 + 4
                  = 8

Proof

Show that sum [x] = x for any number x.

sum :: Num a => [a] -> a
sum [] = 0
sum (x:xs) = x + sum xs

Given the definition of the sum function:

sum [x] = x + sum []
        = x + 0
        = x

Product

Define a function product that produces the product of a list of numbers, and show using your definition that product [2, 3, 4] = 24.

product:

pdt :: Num a => [a] -> a
pdt [] = 1
pdt (x:xs) = x * pdt xs

product [2,3,4] = 24?

pdt [2,3,4] = 2 * pdt [3,4]
            = 2 * 3 * pdt [4]
            = 2 * 3 * 4 * pdt []
            = 2 * 3 * 4 * 1
            = 24

Quicksort

How should the definition of the function qsort be modified so that it produces a reverse sorted version of a list?

Given the following quicksort definition:

qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort smaller ++ [x] ++ qsort larger
               where
                 smaller = filter (<= x) xs
                 larger  = filter (> x) xs

We want to modify such quicksort definition to reverse the output. So from qsort [4 6 2] => [2 4 6] into qsort [4 6 2] => 6 4 2.

qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort larger ++ [x] ++ qsort smaller
               where
                 smaller = filter (<= x) xs
                 larger  = filter (> x) xs

Note ++ is the concatenation

To simplify the next proofs, we will prove that: for any x, qsort [x] = [x]

qsort [x] = qsort [] ++ [x] ++ qsort []
          = [] ++ [x] ++ []
          = [x]

case made.

Now solving the question:

qsort [4,6,2] = qsort [6] ++ [4] ++ qsort [2]
              = [6] ++ [4] ++ [2]
              = [6,4,2]

Quicksort 2/2

What would be the effect of replacing <= by < in the original definition of qsort ? Hint: consider the example qsort [2, 2, 3, 1, 1].

Given:

qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort smaller ++ [x] ++ qsort larger
               where
                 smaller = filter (< x) xs
                 larger  = filter (> x) xs

This will filter out the duplicated entries.

Here is the solved example:

qsort [2,2,3,1,1] = qsort [1] ++ [2] ++ qsort [3]
                  = [1] ++ [2] ++ [3]
                  = [1,2,3]

Source

ch1.hs