## An Introduction to Functional ProgrammingThis is a thorough introduction to the fundamental concepts of functional programming.The book clearly expounds the construction of functional programming as a process of mathematical calculation, but restricts itself to the mathematics relevant to actual program construction. It covers simple and abstract datatypes, numbers, lists, examples, trees, and efficiency. It includes a simple, yet coherent treatment of the Haskell class; a calculus of time complexity; and new coverage of monadic input-output. |

### From inside the book

Results 1-3 of 17

Page 235

The second useful measure on trees is the notion of

tree is defined as follows:

...

The second useful measure on trees is the notion of

**depth**. The**depth**of a finitetree is defined as follows:

**depth**(Tip x) = 0**depth**(Bin tl t2) = 1 + (**depth**tl ) max (**depth**t2) In words, the**depth**of a tree consisting of a single tip is 0; otherwise it is...

Page 236

Assume, by way of induction, that: size tl < 2 ~

let: We now have: d = (

size.2) < 2~ (

...

Assume, by way of induction, that: size tl < 2 ~

**depth**tl size t2 < 2 ~**depth**t2 andlet: We now have: d = (

**depth**tl ) max (**depth**t2) size (Bin tl t2) = size tl + size t2 (size.2) < 2~ (

**depth**tl) + 2~ (**depth**t2) (hypothesis) < 2~<f + 2~d (given) = 2~(l + d)...

Page 256

9.4.1 Analysis of

and

a balanced tree of

9.4.1 Analysis of

**depth**Finally, let us determine the relationship between sizeand

**depth**in a balanced tree. The idea is to construct, for each natural number d,a balanced tree of

**depth**d with the minimum possible size. Call this size S(d).### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Common terms and phrases

abstr aexp algorithm apply argument arithmetic bigit binary search trees binary tree bool btree Chapter char characters compute concat concatenation consider constructors curry define a function delete denotes depth efficient Eight Queens problem element empty equation evaluation example Exercises expression False filter finite foldl foldr Functional composition functional programming given graph reduction implementation induction infinite list init insert insertion sort integers iterate labels t2 list comprehension list xs lookup map f mapbtree mathematical merge sort minimax mkarray natural numbers Node non-empty list notation operations otherwise outermost reduction pair position problem proof prove queens quicksort recursive definition reduction steps representation represented result returns reverse xs sequence sneeuq solution square string structural induction subtree Succ Suppose synthesise Tagb takewhile term tl t2 True unlines variable words write xs H xs ys Zero