Recursive operations on lists

Task: Calculate the arithmetic mean of a list of numbers

$$ \bar{x} = \frac{1}{n}\left (\sum_{i=1}^n{x_i}\right ) = \frac{x_1+x_2+\cdots +x_n}{n} $$

The mean function

In [ ]:
mean list = totalSum list / count list

[Now implement count and totalSum]{.fragment}


Recursive operations on lists

Task: Calculate the number of elements in a list

The function count

In [ ]:
count list =
  if null list
    then 0
    else 1 + count (tail list)

Recursive operations on lists

Task: Calculate the sum of elements in a list of numbers

The function totalSum

In [ ]:
totalSum list =
  if null list 
    then 0
    else head list + totalSum (tail list)

Haskell implementation

Naive but straight forward

In [ ]:
fibN n =
  if n == 0
    then 0
    else if n == 1
           then 1
           else fibN (n - 1) + fibN (n - 2)

Problems of this implementation?


Guard blocks

Guard syntax

In [ ]:
fibG n
  | n == 0 = 0
  | n == 1 = 1
  | otherwise = fibG (n - 1) + fibG (n - 2)

Multiple function definitions

  • Different implementations
  • Selection based on parameter values
  • Guard blocks are conditional expressions of the parameter values
  • (otherwise is just a global binding for the value True)

Fibonacci Haskell implementation

Naive with pattern matching

In [ ]:
fibP 0 = 0
fibP 1 = 1
fibP n = fibP (n - 1) + fibP (n - 2)

But still $\cal O(\mathrm{fib}\ n)$

  • Very inefficient
  • Useless for $F_{30}$ or bigger

Solution?

  • Calculate $F_{n-1}$ and $F_{n-2}$ beforehand
  • Pass to fib function as arguments

Fibonacci Haskell implementation

With accumulator parameters f2 and f1

In [ ]:
fibF n = fibF' n 0 1

fibF' 0 f2 f1 = f2
fibF' n f2 f1 = fibF' (n-1) f1 (f1+f2)

Top-level scope in Haskell

Declarations at file-level

  • Names bound at the top-level have file scope
  • They can be used in every expression in that file
  • The binding order does not matter

Example file Triple.hs

In [ ]:
module Triple where

main = print (triple seven)

seven = 7

triple x = x + x + x

Expression scope in Haskell

let expression

{.haskell}
let name = value
    name' = value' 
 in expression
  • Binds value to name
  • Binding is valid in the expression
  • Scope is limited to expression
  • Multiple name value pairs are possible

Example

In [ ]:
module Crew where

main = print bridgeCrew

officers = ["Picard", "Ryker"]

bridgeCrew =
  let officers = ["Kirk", "Spock"]
      others = ["Uhura", "Sulu", "Checkov"]
   in officers ++ others