# 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¶

## The function count¶

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


# Recursive operations on lists¶

## The function totalSum¶

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


## 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)


# 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)

## 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

## 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)


## 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


## 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